Java Reference
In-Depth Information
at the end of the expression, and one value, 2, is in the stack. This value is the value of the expres-
sion. Figure 5-11 traces the evaluation of this postfix expression.
FIGURE 5-11
The stack during the evaluation of the postfix expression
a
b
+
c
/
when
a
is 2,
b
is 4, and
c
is 3
c
a
b
2
4
2
4
/
/
3
3
4
4
2
4
3
2
2
6
6
2
2
2
6
6
6
2
5.18
The evaluation algorithm follows directly from these examples:
Algorithm
evaluatePostfix(postfix)
//
Evaluates a postfix expression.
valueStack =
a new empty stack
while
(postfix
has characters left to parse
)
{
nextCharacter =
next nonblank character of
postfix
switch
(nextCharacter)
{
case
variable
:
valueStack.push(
value of the variable
nextCharacter)
break
case
'+' :
case
'-' :
case
'*' :
case
'/' :
case
'^' :
operandTwo = valueStack.pop()
operandOne = valueStack.pop()
result =
the result of the operation in
nextCharacter
and its operands
operandOne
and
operandTwo
valueStack.push(result)
break
default
:
break
}
}
return
valueStack.peek()
We can implement this algorithm and the algorithm
convertToPostfix
given in Segment 5.16
as static methods of a class
Postfix.
The implementations are left as an exercise.
Question 7
Using the previous algorithm, evaluate each of the following postfix expres-
sions. Assume that a = 2, b = 3, c = 4, d = 5, and e = 6.
a.
a
e
+
b d
-
/
b.
a
b
c
*
d
*
-
c.
a b c
-
/
d
*
d.
e b c a
^
*
+
d
-
