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

An operator stack is
used to store oper-
ators that have
been seen but not
yet output.

precedence of the involved operators is increasing as we go from left to right.
Even so, this condition suggests that a stack is appropriate for storing opera-
tors. Following this logic, then, when we read an operator it must somehow
be placed on a stack. Consequently, at some point the operator must get off
the stack. The rest of the algorithm involves deciding when operators go on
and come off the stack.
In another simple infix expression

2 ^ 5 - 1

when we reach the - operator, 2 and 5 have been output and ^ is on the stack.
Because - has lower precedence than ^ , the ^ needs to be applied to 2 and 5 .
Thus we must pop the ^ and any other operands of higher precedence than -
from the stack. After doing so, we push the - . The resulting postfix expression
is

When an operator
is seen on the
input, operators of
higher priority (or
left-associative
operators of equal
priority) are
removed from the
stack, signaling that
they should be
applied. The input
operator is then
placed on the
stack.

2 5 ^ 1 -

In general, when we are processing an operator from input, we output those
operators from the stack that the precedence (and associativity) rules tell us
need to be processed.
A second example is the infix expression

3 * 2 ^ 5 - 1

When we reach the ^ operator, 3 and 2 have been output and * is on the stack.
As ^ has higher precedence than * , nothing is popped and ^ goes on the stack.
The 5 is output immediately. Then we encounter a - operator. Precedence
rules tell us that ^ is popped, followed by the * . At this point, nothing is left to
pop, we are done popping, and - goes onto the stack. We then output 1 . When
we reach the end of the infix expression, we can pop the remaining operators
from the stack. The resulting postfix expression is

3 2 5 ^ * 1 -

A left parenthesis is
treated as a high-
precedence opera-
tor when it is an
input symbol but as
a low-precedence
operator when it is
on the stack. A left
parenthesis is
removed only by a
right parenthesis.

Before the summarizing algorithm, we need to answer a few questions.
First, if the current symbol is a + and the top of the stack is a + , should the + on
the stack be popped or should it stay? The answer is determined by deciding
whether the input + implies that the stack + has been completed. Because +
associates from left to right, the answer is yes. However, if we are talking
about the ^ operator, which associates from right to left, the answer is no.
Therefore, when examining two operators of equal precedence, we look at the
associativity to decide, as shown in Figure 11.12.
What about parentheses? A left parenthesis can be considered a high-
precedence operator when it is an input symbol, a low-precedence operator