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```
Operator   Precedence
` * / `
`6`
`+ - `
`5`
`=`
`4`
`\$`
`3`
`(`
`2`
`)`
`1`
`_`
`0`
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:

• It is the very first symbol of an expression, or
• It immediately follows an opening parenthesis (`'('`), or
• It immediately follows an assignment operator (`'='`).

In all other cases, the operator is binary. Hence, an expression such as `2 + -3` is illegal, but `2 + (-3)` is legal.Unary '`+`' doesn't do anything, so it is just discarded. The program replaces unary '`-`' by the '`~`' symbol, and evaluates it correctly.