Java Reference
In-Depth Information
You can interpret these sequences as instructions for a stack-based calculator. A
number means:
ȗ Push the number on the stack.
An operator means:
ȗ Pop the top two numbers off the stack.
ȗ Apply the operator to these two numbers.
ȗ Push the result back on the stack.
Figure 15
shows the computation sequences for the two expressions.
Postorder traversal of an expression tree yields the instructions for evaluating the
expression on a stack-based calculator.
This observation yields an algorithm for evaluating arithmetic expres
sions. First, turn
the expression into a tree. Then carry out a postorder traversal of the
expression tree
and apply the operations in the given order. The result is the value of the expression.
733
734
Figure 15
A Stack-Based Calculator
S
ELF
C
HECK
11.
What are the inorder traversals of the two trees in
Figure 14
?
