Java Reference
In-Depth Information
Evaluate an infix expression that uses the operators
+
,
-
,
*
,
/
, and
^
to indicate addition, subtrac-
tion, multiplication, division, and exponentiation.
5.19
Using the two algorithms in Segments 5.16 and 5.18, we could evaluate an infix expression by con-
verting it to an equivalent postfix expression and then evaluating it. We can save some intermediate
work, however, by combining the two algorithms into one that evaluates an infix expression
directly by using two stacks. This combined algorithm maintains a stack of operators according to
the algorithm that converts an infix expression to postfix form. But instead of appending operands
to the end of an expression, the new algorithm pushes the value of an operand onto a second stack
according to the algorithm that evaluates a postfix expression.
5.20
Example.
Consider the infix expression
a
+
b
*
c
. When
a
is 2,
b
is 3, and
c
is 4, the expression's
value is 14. To compute this result, we push the value of the variable
a
onto a stack of values, push
the
+
onto a stack of operators, and push the value of
b
onto the stack of values. Since
*
has a higher
precedence than the
+
at the top of the operator stack, we push it onto the stack. Finally, we push the
value of
c
onto the stack of values. Figure 5-12a shows the state of the two stacks at this point.
FIGURE 5-12
Two stacks during the evaluation of
a
+
b
*
c
when
a
is 2,
b
is 3,
and
c
is 4:
(a) after reaching the end of the expression;
(b) while performing the multiplication;
(c) while performing the addition
(a)
4
*
3
2
(b)
3 * 4
3 * 4
4
3
3
3
12
*
2
2
2
(c)
12
14
2
2
