Implement the following algorithm for the evaluation of arithmetic expressions. Each operator has a precedence. The + and - operators have the lowest precedence, * and / have higher (and equal) precedence, and ^ (which denotes "raising to a power" in this excercise) has the highest. For example,
3 * 4 ^ 2 + 5
should mean the same thing 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 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.