Arithmetic Evaluator 
12 points
Implement the following algorithm for the evaluation of arithmetic expressions.
Each operator has a precedence. The + and  operators have the lowest (and equal) 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:
Expression: 3 * 4 ^ 2 + 5  
1  Remaining expression: * 4 ^ 2 + 5 
Number stack 3 
Operator stack

2  Remaining expression: 4 ^ 2 + 5 
Number stack 3 
Operator stack * 
3  Remaining expression: ^ 2 + 5 
Number stack 4 3 
Operator stack * 
4  Remaining expression: 2 + 5 
Number stack 4 3 
Operator stack ^ * 
5  Remaining expression: + 5 
Number stack 2 4 3 
Operator stack ^ * 
6  Remaining expression: + 5 
Number stack 16 3 
Operator stack * 
7  Remaining expression: 5  Number stack 48 
Operator stack + 
8  Remaining expression:  Number stack 5 48 
Operator stack + 
9  Remaining expression:  Number stack 53 
Operator stack 
The program does not handle negative numbers. It cannot distinguish between "" as an operator, and the "" that makes a number negative.
This is Project 15.3 from p. 696 of Java Concepts for AP Computer Science.
Test your program by running these test cases:
#
Test Case
Result
1
9  6 / 3
7
2
8  6 + 3
5
3
9 + 3 * 2  8 / 4
13
4
4 * 3  6 / 2
9
5
9 / 3 * 2 / 4 * 2
3
6
7  6 + 5  4 + 3
5
7
8 + 4  3 / 3 * 2
10
3 points
Enable your program to work with numbers other than the integers from 0 to 9. Some guidance on this is given in Arithmetic.java.
Test your program by running these test cases:
#
Test Case
Result
1
12 / 3  10 * 2
16
2
15  12 + 9  6 + 3
9
3
12 + 10 / 5  12 / 6
12
4
12 + 24 / 3 / 4  3
11
5
15  2 * 11 * 3 + 17
34
4 points
Enable your program to handle parentheses. Some guidance on this is given in Arithmetic.java.
Test your program by running these test cases:
#
Test Case
Result
1
(4 + 6  2) / (7  3 + 4)
1
2
9  (3 + 4) / 7
8
3
9  (3 + 4)  (2  5)
5
4
(6  2) * 3  2 * (3  5)
16
5
(6 + 2) / 4  9 / (2 + 1)
1
If you did both extracredits, test your program by running these test cases:
#  Test Case  Result 
1  (322  111  43) / (21  4  3)  12 
2  132  (21 + 15) / 12  129 
3  270 / (9 * 5) / 2 + (42 + 43) * 12 * 2  2043 
4  (119 + 1) / (21  13)  (211  36) / (19 + 6)  8 
5  (53 + 45) / 7 + (6  4) * 2  18 
Documentation for this program is available here.
Starting Point
You can download Arithmetic.java to use as a starting point in writing your program. Instructions for writing the program are given in the .java file. You'll also need the Stack interface (Stack.java) and the ArrayStack.java file you wrote for a previous program.
You can download Arithmetic.jar, which will show you how this program can function when you've completed it. Doubleclick on the JAR file to get the program to run.