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

figure 11.11
Steps in the
evaluation of a postfix
expression

Postfix Expression: 1 2 - 4 5 ^ 3 * 6 * 7 2 2 ^ ^ / -

5
4
-1
5

2
1
2

4
-1
4

-1
-

1
1

3
1024
-1
3

6
3072
-1
6

7
18432
-1
7

1024
-1
^

3072
-1
*

18432
-1
*

2
2
7
18432
-1
2

2
7
18432
-1
2

4
7
18432
-1
^

2401
18432
-1
^

7
-1
/

-8
-

8 operators, there are 17 steps and 17 pushes. Clearly, the time required to evalu-
ate a postfix expression is linear.
The remaining task is to write an algorithm to convert from infix notation
to postfix notation. Once we have it, we also have an algorithm that evaluates
an infix expression.

11.2.2 infix to postfix conversion

The basic principle involved in the operator precedence parsing algorithm,
which converts an infix expression to a postfix expression, is the following.
When an operand is seen, we can immediately output it. However, when we
see an operator, we can never output it because we must wait to see the second
operand, so we must save it. In an expression such as

The operator pre-
cedence parsing
algorithm converts
an infix expression
to a postfix expres-
sion, so we can
evaluate the infix
expression.

1 + 2 * 3 ^ 4

which in postfix form is

1 2 3 4 ^ * +

a postfix expression in some cases has operators in the reverse order than
they appear in an infix expression. Of course, this order can occur only if the