People write 3 + 4 * 2; a stack machine prefers the postfix form 3 4 2 * +, which needs no parentheses and no priority rules. Write InfixToPostfix, which reads one expression per line (non-negative integers, + − * / %, parentheses, optional spaces) and prints its postfix form and its value (integer arithmetic).
Conversion with a stack of operators (the shunting-yard algorithm):
- a number goes straight to the output;
(is pushed;)pops operators to the output until the matching(;- an operator first pops to the output every operator on top of the stack with higher or equal priority (stopping at a
(), then is pushed; - at the end, the remaining operators are popped.
Report unmatched (, unmatched ), an unexpected character or a division by zero as error: …. For the input
3 + 4 * 2
(3 + 4) * 2
8 - 3 - 2
100 / (2 + 3) % 7
2 * (3 + (4 - 1)) * 5
(1 + 2
7 / (4 - 4)
the program prints
3 + 4 * 2 -> 3 4 2 * + = 11
(3 + 4) * 2 -> 3 4 + 2 * = 14
8 - 3 - 2 -> 8 3 - 2 - = 3
100 / (2 + 3) % 7 -> 100 2 3 + / 7 % = 6
2 * (3 + (4 - 1)) * 5 -> 2 3 4 1 - + * 5 * = 60
(1 + 2 -> error: unmatched (
7 / (4 - 4) -> error: / by zero