Java Reference
In-Depth Information
΢΢΢Project 15.3. Implement the following algorithm for the evaluation of
arithmetic expressions.
Each operator has a precedence. The + and Ċ operators have the
lowest precedence, * and / have a higher (and equal) precedence, and ɶ
(which denotes Ȓraising to a powerȓ in this exercise) has the highest. For
example,
3 * 4 ^ 2 + 5
should mean the same as
(3 * (4 ^ 2)) + 5
with a value of 53.
In your algorithm, use two stacks. One stack holds numbers, the other
holds operators. When you encounter a number, push it on the number
stack. When you encounter an operator, push it on the operator stack if it
has higher precedence than the operator on the top of the stack.
Otherwise, pop an operator off the operator stack, pop two numbers off
the number stack, and push the result of the computation on the number
stack. Repeat until the top of the operator stack has lower precedence. At
the end of the expression, clear the stack in the same way. For example,
here is how the expression 3 * 4 ɶ 2+5 is evaluated:
Search WWH ::




Custom Search