Java Reference
In-Depth Information
Given the postfix form of an expression, it can be evaluated as follows:
initialize a stack, S, to empty
while we have not reached the end of the expression
get the next item, x, from the expression
if x is an operand, push it onto S
if x is an operator, pop its operands from S, apply the operator and
push the result onto S
endwhile
pop S; // this is the value of the expression
Consider the expression (7 + 3) * 4 whose postfix form is 7 3 + 4 * . It is evaluated by traversing from left to right.
1.
The next item is 7 ; push 7 onto S ; S contains 7 .
2.
The next item is 3 ; push 3 onto S ; S contains 7 3 (the top is on the right).
3.
The next item is + ; pop 3 and 7 from S ; apply + to 7 and 3 , giving 10 ; push 10 onto S ;
S contains 10 .
4.
The next item is 4 ; push 4 onto S ; S contains 10 4 .
5.
The next item is * ; pop 4 and 10 from S ; apply * to 10 and 4 , giving 40 ; push 40 onto S ;
S contains 40 .
6.
We have reached the end of the expression; we pop S , getting 40 —the result of the
expression.
Note that when operands are popped from the stack, the first one popped is the second operand, and the second
one popped is the first operand. This does not matter for addition and multiplication but would be important for
subtraction and division. As an exercise, convert the following to postfix form and step through its evaluation using
the algorithm above: (7 - 3) * (9 - 8 / 4) .
The big question, of course, is how do we get the computer to convert an infix expression to postfix? Before
presenting the algorithm, we observe that it will use an operator stack . We will also need a precedence table that gives
the relative precedence of the operators. Given any two operators, the table will tell us whether they have the same
precedence (like + and - ) and, if not, which has greater precedence.
As the algorithm proceeds, it will output the postfix form of the given expression.
Here is the algorithm:
Initialize a stack of operators, S , to empty.
1.
Get the next item, x , from the infix expression; if none, go to step 8 ( x is either an operand,
a left bracket, a right bracket, or an operator).
2.
If x is an operand, output x .
3.
If x is a left bracket, push it onto S .
4.
If x is a right bracket, pop items off S and output popped items until a left bracket appears
on top of S ; pop the left bracket and discard.
5.
If x is an operator, then do the following:
6.
while (S is not empty) and (a left bracket is not on top of S) and
(an operator of equal or higher precedence than x is on top of S)
pop S and output popped item
push x onto S
 
Search WWH ::




Custom Search