CIT 594 Expression Evaluator
Spring 2012, David Matuszek
The following applet uses two stacks to evaluate simple arithmetic expressions. All numbers are treated as floating point. You can add, subtract, multiply, divide, use parentheses, assign to simple variables, and use those variables again in later expressions.
In addition to the five arithmetic operators (+
, 
, *
, /
, =
),
the program uses the following "fake" operators:
$
To mark
the end of the arithmetic expression, so we don't have to repeatedly ask "Is
there another token?
_
To mark the
bottom of the operator stack, so we don't have to repeatedly ask "Is there anything in the stack?"
~
To represent unary minus, because it's a different operation than subtraction
Here's the basic algorithm:
add a '$' to the end of the expression (the program, not the user, does this) push a '_' onto the operator stack while there are tokens remaining in the input string  get the next token  depending on the token, take one of the following actions:   if the token is a number, push it onto the operand stack   else if the token is a variable name, push it onto the operand stack   else if the token is a '(', push it onto the operator stack   else if the token is a ')'    while the top operator in the operator stack is not an '('     pop an operator from the operator stack     pop two values from the operand stack     apply the operator to the two values to compute a new value    __ push the new value onto the operand stack    pop the '(' from the operator stack   else if the token is an operator (+, , *, /, =, $)    while the priority of the new token is less than or equal to     that of the top operator in the operator stack,     pop an operator from the operator stack,     pop two values from the operand stack     apply the operator to the two values to compute a new value    __ put the new value onto the operand stack __ __ __ push the new token onto the operator stack

The above depends on precedence: Higher precedence operators should be applied before lower precedence operators. Here is the table of precedence that is used. 
Unary plus and minus have to be distinguished from the corresponding binary operators. A '+
' or '
' is unary
if and only if:
'('
), or'='
).In all other cases,
the operator is binary. Hence,
an expression such as
is illegal,
but
is legal.Unary '+
' doesn't do anything, so it is just discarded. The program replaces unary '
' by the '~
' symbol, and evaluates it correctly.