CS140 -- Lab A

Wed Nov 10 07:58:44 EST 2004
This lab consists of two programs: rptoparen and bs_scoreproc.


Rptoparen takes no command line arguments. It reads lines from standard input. If a line is blank, it does nothing. Otherwise, it assumes that the line is a reverse Polish mathematical expression. Each input word in a reverse Polish expression is one of three things: a literal, a variable, or an operator. The operators that we support are: +, -, *, / and %. Literals are floating point numbers. Variables are any word that starts with a letter, that is composed of letters, numbers and the underscore character.

Rptoparen maintains a stack (that you may implement either with the Stack data structure, or with a Dllist). On the stack are expressions, (which you will represent with a tree). Whenever it encounters a literal or variable, it turns that into an expression, and pushes it onto the stack. Whenever it encounters an operator, it pops the top two expressions off the stack. Call them top and second. It then turns them into one expression which is ( second operator top ). It pushes this new expression onto the stack.

After reading a line of standard input and turning it into a stack of expressions, rptoparen prints out all expressions on the stack. If an expression is a literal or variable, you simply print out the literal value (padded to three decimal places) or variable name to print out the expression. If an expression is an operator acting on two subexpressions, you print out a left paren, a space, the first subexpression, a space, the operator, a space, the second subexpression, a space, and a right paren. If there are multiple expressions on the stack, they should be separated by a newline.

Some examples:

UNIX> rptoparen
a 5
a 5 +
( a + 5.000 )
a 5 + 6 - 8 9 * * 
( ( ( a + 5.000 ) - 6.000 ) * ( 8.000 * 9.000 ) )
a b + c d + * e f + g h + * - 
( ( ( a + b ) * ( c + d ) ) - ( ( e + f ) * ( g + h ) ) )
a +
Error: Operator + acting on a stack with < 2 elements
UNIX> rptoparen
Error -- non-literal, variable or operator: $
UNIX> rptoparen
a b + c-d
Error -- non-literal, variable or operator: c-d
If you'd like the hint, here's a nice typedef for an expression:

typedef struct expression {
  int type;                  /* 'L' for literal, 'V' for variable, 'O' for operator */
  double literal;            /* only used if type == 'L' */
  char *variable;            /* only used if type == 'V' */
  int operator;              /* only used if type == 'O' */
  struct expression *first;  /* only used if type == 'O' */
  struct expression *second; /* only used if type == 'O' */
} Expression;


Rewrite scoreproc from lab 8 so that it uses the bstree binary search tree routines described in the binary search tree lecture. You are not allowed to use any linked lists in your program -- read everything into a big binary search tree keyed on the names.

Differences from the Hashing Version of Scoreproc

The output of your bs_scoreproc program will differ in a number of ways from the hashing version of your scoreproc program:

  1. You will need to print the number of unique names in the score files.
  2. You will need to print the max/min average scores and print the names associated with these values. You should be able to do this by traversing the tree in the appropriate way. There may be multiple minimum or maximum average scores so you must take care to print all of the names associated with them. Since the binary tree is organized by name and not by score, you will need to traverse the entire tree. You should also print the names in alphabetical order. The alphabetical order will be based on the alphabetical order of the first names, not the last names (e.g., Phil Mickelson would appear before Phil Adelson but after Brad Vander Zanden).
  3. You do not have to print out the contents of the hash table for this lab because you are not using a hash table.
Consult the executable to see the format for printing the number of unique names and the average minimum/maximum scores and names, as well as any other questions you might have.