Stacks
Consider an expression like:
- 9 * 2 3
We want to multiple the 2 and 3, then subtract that from 9.
We’ll scan the string, keeping separate stacks of operators and numbers. Then, as a special case, we’ll pop the last number off, so we have a number to start with. Then, we’ll pop off number and operators, performing the expression backwards.
For our example:
Make an operators stack of [-, *].
Make a numbers stack of [9, 2, 3].
Pop the last number, 3, off.
Our loop:
Pop off the last number, 2, and the last operator, *.
Multiply 2 * 3 = 6
Pop off the last number, 9, and the last operator, -.
Subtract 9 - 6 = 3
Return 3
def calc(s):
"""Evaluate expression."""
# START SOLUTION
# Convert to list of tokens
#
# For example: "+ 1 2" -> ["+", "1", "2"]
tokens = s.split()
# Start with right-most number (in a well-formed polish notation
# expression, it must ALWAYS end with a number)
operand2 = int(tokens.pop())
while tokens:
# Grab the right-most number
operand1 = int(tokens.pop())
# Grab the right-most operand
operator = tokens.pop()
# Do the math and use the result as our "right-hand" value
# for the next time we do math
if operator == "+":
operand2 = operand1 + operand2
elif operator == "-":
operand2 = operand1 - operand2
elif operator == "*":
operand2 = operand1 * operand2
elif operator == "/":
operand2 = operand1 // operand2
# The final result is the result of the most recent operation
return operand2