Stacks and compilers - Data Structures and Problem Solving Using Java - page 456

Although the parentheses make the order of evaluations unambiguous, they do not
necessarily make the mechanism for evaluation any clearer. A different expression
form, called a postfix expression, which can be evaluated by a postfix machine
without using any precedence rules, provides a direct mechanism for evaluation.
In the next several sections we explain how it works. First, we examine the postfix
expression form and show how expressions can be evaluated in a simple left-to-
right scan. Next, we show algorithmically how the previous expressions, which
are presented as infix expressions, can be converted to postfix. Finally, we give a
Java program that evaluates infix expressions containing additive, multiplicative,
and exponentiation operators—as well as overriding parentheses. We use an algo-
rithm called operator precedence parsing to convert an infix expression to a post-
fix expression in order to evaluate the infix expression.

A postfix expression
can be evaluated as
follows. Operands
are pushed onto a
single stack. An
operator pops its
operands and then
pushes the result.
At the end of the
evaluation, the stack
should contain only
one element, which
represents the
result.

11.2.1 postfix machines

A postfix expression is a series of operators and operands. A postfix machine is
used to evaluate a postfix expression as follows. When an operand is seen, it is
pushed onto a stack. When an operator is seen, the appropriate number of operands
are popped from the stack, the operator is evaluated, and the result is pushed back
onto the stack. For binary operators, which are the most common, two operands are
popped. When the complete postfix expression is evaluated, the result should be a
single item on the stack that represents the answer. The postfix form represents a
natural way to evaluate expressions because precedence rules are not required.
A simple example is the postfix expression

1 2 3 * +

The evaluation proceeds as follows: 1 , then 2 , and then 3 are each pushed onto the
stack. To process * , we pop the top two items on the stack: 3 and then 2 . Note that
the first item popped becomes the rhs parameter to the binary operator and that
the second item popped is the lhs parameter; thus parameters are popped in
reverse order. For multiplication, the order does not matter, but for subtraction and
division, it does. The result of the multiplication is 6 , and that is pushed back onto
the stack. At this point, the top of the stack is 6 ; below it is 1 . To process the + , the
6 and 1 are popped, and their sum, 7 , is pushed. At this point, the expression has
been read and the stack has only one item. Thus the final answer is 7 .
Every valid infix expression can be converted to postfix form. For exam-
ple, the earlier long infix expression can be written in postfix notation as

1 2 - 4 5 ^ 3 * 6 * 7 2 2 ^^ / -

Figure 11.11 shows the steps used by the postfix machine to evaluate this expres-
sion. Each step involves a single push. Consequently, as there are 9 operands and

Evaluation of a
postfix expression
takes linear time.