CS140 -- Lab A

• CS140 -- Data Structures
• Fall-2004
• James S. Plank
• This file: http://web.eecs.utk.edu/~jplank/plank/classes/cs140/Fall-2004/labs/laba/
• Hints for bs_scoreproc.

rptoparen

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
5
5.000
a
a
a 5
5.000
a
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
UNIX> 

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;

bs_scoreproc

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.