The objectives for this assignment are to use queues and stacks to translate an infix expression into a postfix expression, and to then evaluate the postfix expression. An infix expression is one where the operator is placed in between the operands. A postfix expression is one in which the operands come first and the operator follows. Both the translation phase and the evaluation phase require a stack. Postfix expressions are quite easy to evaluate using a stack.
As this is a new assignment, it would not be surprising if it contained some errors. Let me know if you find any errors so I can correct them. I will also be available to check out your code as it develops to help debug it and get it running. Remember to run tests on your program to make sure it works. Note: To make life simpler for you, this evaluation routine does not check for division by 0. Your program should give the result: Infinity.
You will use your code from the infix translator as the starting point for this assignment. The infixQueue that was the end result of the infix assignment is the input for this assignment, so you'll just use your previous code and add to it.
Rename your program Postfix.java. The code you have to write has two parts. The first part is the translation from infix to postfix. The second part is the evaluation of the postfix expression. Both chunks of code should be placed in sequential order just before the end of your main while loop in "public static void main(String[] args)".
while (true)
if the stack is empty, then push itm onto the stack and exit the loop
otherwise
get the precedence of the top item on the stack
if itm's precedence is greater than the precedence of the top item on the stack
or if the precedence's are equal and itm is NOT leftToRightAssociative then
push itm onto the stack and exit the loop
otherwise pop the top Token from the stack and add it to the end of the postfixQueuewhile (true) {
pop the top Token from the stack and hold onto it
if that Token has a type of Token.OPENPAREN, then exit this loop
otherwise add the Token to the end of the postfixQueueif (DEBUG) {
System.out.println("Postfix queue:");
for (int i=0; i<postfixQueue.size(); i++) System.out.printf("%2d: %s\n", (i+1), postfixQueue.get(i));
}pop the top value from the evaluation stack and store it in x2 pop the top value from the evaluation stack and store it in x1 if item's data is "+" then push x1 + x2 onto the evaluation stack otherwise, if item's data is "-" then push x1 - x2 onto the evaluation stack otherwise, if item's data is "*" then push x1 * x2 onto the evaluation stack otherwise, if item's data is "/" then push x1 / x2 onto the evaluation stack otherwise, if item's data is "%" then push x1 % x2 onto the evaluation stack otherwise, if item's data is "^" then push Math.pow(x1, x2) onto the evaluation stack
Enter an expression to evaluate (or QUIT to exit)
Program is in DEBUG mode
Enter expression: (5+2) * (.3 - -3.3)
Infix queue:
1: open parenthesis
2: operand (5)
3: oper (+), 1, true
4: operand (2)
5: close parenthesis
6: oper (*), 2, true
7: open parenthesis
8: operand (.3)
9: oper (-), 1, true
10: operand (-3.3)
11: close parenthesis
Postfix queue:
1: operand (5)
2: operand (2)
3: oper (+), 1, true
4: operand (.3)
5: operand (-3.3)
6: oper (-), 1, true
7: oper (*), 2, true
Result: 25.199999999999996
Enter expression: ( 6 + 2.3) ) -1
Error: ( 6 + 2.3) ) -1
^
Enter expression: ( 6 + 2.3) -1
Infix queue:
1: open parenthesis
2: operand (6)
3: oper (+), 1, true
4: operand (2.3)
5: close parenthesis
6: oper (-), 1, true
7: operand (1)
Postfix queue:
1: operand (6)
2: operand (2.3)
3: oper (+), 1, true
4: operand (1)
5: oper (-), 1, true
Result: 7.300000000000001
Enter expression: 3 +-.78*((2++14.9 * 3.)^(3+(2*5)))
Infix queue:
1: operand (3)
2: oper (+), 1, true
3: operand (-.78)
4: oper (*), 2, true
5: open parenthesis
6: open parenthesis
7: operand (2)
8: oper (+), 1, true
9: operand (+14.9)
10: oper (*), 2, true
11: operand (3.)
12: close parenthesis
13: oper (^), 3, false
14: open parenthesis
15: operand (3)
16: oper (+), 1, true
17: open parenthesis
18: operand (2)
19: oper (*), 2, true
20: operand (5)
21: close parenthesis
22: close parenthesis
23: close parenthesis
Postfix queue:
1: operand (3)
2: operand (-.78)
3: operand (2)
4: operand (+14.9)
5: operand (3.)
6: oper (*), 2, true
7: oper (+), 1, true
8: operand (3)
9: operand (2)
10: operand (5)
11: oper (*), 2, true
12: oper (+), 1, true
13: oper (^), 3, false
14: oper (*), 2, true
15: oper (+), 1, true
Result: -3.9193500190982847E21
Enter expression: 7.8 + -3.0001
Infix queue:
1: operand (7.8)
2: oper (+), 1, true
3: operand (-3.0001)
Postfix queue:
1: operand (7.8)
2: operand (-3.0001)
3: oper (+), 1, true
Result: 4.799899999999999
Enter expression: (5 + 3.4) * 2
Infix queue:
1: open parenthesis
2: operand (5)
3: oper (+), 1, true
4: operand (3.4)
5: close parenthesis
6: oper (*), 2, true
7: operand (2)
Postfix queue:
1: operand (5)
2: operand (3.4)
3: oper (+), 1, true
4: operand (2)
5: oper (*), 2, true
Result: 16.8
Enter expression: * * 7)
Error: * * 7)
^
Enter expression: 8 * 7)
Error: 8 * 7)
^
Enter expression: (3 + 2
Error: (3 + 2
^
Enter expression: 9 ---7
Error: 9 ---7
^
Enter expression: 9--7
Infix queue:
1: operand (9)
2: oper (-), 1, true
3: operand (-7)
Postfix queue:
1: operand (9)
2: operand (-7)
3: oper (-), 1, true
Result: 16.0
Enter expression: 2^3^3
Infix queue:
1: operand (2)
2: oper (^), 3, false
3: operand (3)
4: oper (^), 3, false
5: operand (3)
Postfix queue:
1: operand (2)
2: operand (3)
3: operand (3)
4: oper (^), 3, false
5: oper (^), 3, false
Result: 1.34217728E8
Enter expression: 5 / 0
Infix queue:
1: operand (5)
2: oper (/), 2, true
3: operand (0)
Postfix queue:
1: operand (5)
2: operand (0)
3: oper (/), 2, true
Result: Infinity
Enter expression: quit