Data Structures
We’ll process our expression from left to right. We could use any kind of list and keep track of where we are in it, but to make this easier, we’ll pop off things as we work with them (this way, we don’t have to keep track of the next token — it will always be the start of the list).
Since popping from the left end of a list is O(n), we’ll use a data atructure that is better for this. This could be any kind of queue structure. In our case, we’ll use the deque provided by Python:
from collections import deque
We’ll write a simple function that turns our string into a deque of tokens:
def calc(s):
"""Simple infix calculator."""
# START SOLUTION
tokens = deque(s.split())
return calc_expression(tokens)
And then a recursive function, calc_expression, which processes a list of tokens.
At the point that it hits an (, it will call itself, so it can resolve this
inner expression:
def calc_expression(tokens):
"""Calculate a list like [1, +, 2] or [1, +, (, 2, *, 3, )]"""
lhs = tokens.popleft()
if lhs == "(":
lhs = calc_expression(tokens)
else:
lhs = int(lhs)
operator = tokens.popleft()
rhs = tokens.popleft()
if rhs == "(":
rhs = calc_expression(tokens)
else:
rhs = int(rhs)
# We should be at the end of an expression, so there should be
# either nothing left in the list, or just a closing parenthesis
if tokens:
assert tokens.popleft() == ")", \
"bad expression, expected closing-paren"
# Do the math
if operator == "+":
result = lhs + rhs
elif operator == "-":
result = lhs - rhs
elif operator == "*":
result = lhs * rhs
elif operator == "/":
result = lhs / rhs
else:
raise Exception("bad operator")
return result