Stacks
In this exercise, you’ll build a “polish notation calculator”.
Polish notation is a different way to write an artithmetic expression. For example, instead of writing 1 + 2 * 3, as we would in normal (“infix”) style, we could write it with the operators to the left of their arguments. This expression would become + 1 * 2 3. You can read a polish notation expression backwards to see exactly what it does — in this case, multiply 2 times 3, and add that result to 1.
Let’s try this out:
>>> calc("+ 1 2") # 1 + 2
3
>>> calc("* 2 + 1 2") # 2 * (1 + 2)
6
>>> calc("+ 9 * 2 3") # 9 + (2 * 3)
15
Let’s make sure we have non-commutative operators (subtraction and division) working:
>>> calc("- 1 2") # 1 - 2
-1
>>> calc("- 9 * 2 3") # 9 - (2 * 3)
3
>>> calc("/ 6 - 4 2") # 6 / (4 - 2)
3
We’ve given you a file, calculator.py, with a stub function:
def calc(s):
"""Evaluate expression."""
Implement this.
Hint
Data Structure
You’ll want to turn the expression into a string and work through it backwards. Do this by hand and see how it feels.