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>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; |
The output of your bs_scoreproc program will differ in a number of ways from the hashing version of your scoreproc program: