| | |
In infix arithmetic expressions, operators are placed between two operands -- as shown in the examples below:
$$2+3 \quad \quad \textrm{or} \quad \quad 1 + (2 + 3) * (4 * 5)$$A fully parenthesized infix arithmetic expression is an infix arithmetic expression where every operator and its arguments are contained in parentheses, as seen in following: $$(2+3) \quad \quad \textrm{or} \quad \quad (1+((2+3)*(4*5)))$$
Suppose we wish to evaluate such an expression...
First, we note that a fully parenthesized expression explicitly details the order in which the operators are to be applied. Consequently, in the evaluation of such expressions, operator precedence and associativity don't really matter at all.
Freed from precedence and associativity considerations, we can evaluate a fully parenthesized expression with a simple two-stack algorithm developed by E.W. Dijkstra:
Starting with two empty stacks, called the operand stack and the operator stack, we read the elements of the expression in question from left to right. For each element encountered in turn, we do the action specified by the following table:
| Element Seen | Action Taken |
| operand (e.g., a value) | push it onto the operand stack |
| operator | push it onto the operator stack |
| left parenthesis | do nothing |
| right parenthesis | we pop the operator from the top of the operator stack, and however many operands it requires from the operand stack, and then push the result of applying that operator to those operands to the operand stack |
The following details the state of the operator and operand stacks in the evaluation of an example expression. (Note: that the top of each stack shown is its right-most element, while the bottom is its left-most element.)
( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) evaluates to 101, given:
Element Operator Stack Operand Stack
1 (
2 1 1
3 + + 1
4 ( + 1
5 ( + 1
6 2 + 1 2
7 + + + 1 2
8 3 + + 1 2 3
9 ) + 1 5
10 * + * 1 5
11 ( + * 1 5
12 4 + * 1 5 4
13 * + * * 1 5 4
14 5 + * * 1 5 4 5
15 ) + * 1 5 20
16 ) + 1 100
17 ) 101 <-- The expression, evaluated