Medium Stack Eval Stacks & Queues
In plain English: Evaluate a math expression written in postfix notation using a stack.
Push numbers onto the stack. When you hit an operator, pop two operands, apply the operator, and push the result. The stack naturally handles operator precedence and nesting.
Prompt
Evaluate an expression in Reverse Polish Notation (postfix). Valid operators are +, -, *, /. Each operand is an integer.
Try to write it from scratch before scrolling down.
Solution
def eval_rpn(tokens):
stack = []
ops = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: int(a / b), # truncate toward zero
}
for t in tokens:
if t in ops:
b, a = stack.pop(), stack.pop()
stack.append(ops[t](a, b))
else:
stack.append(int(t))
return stack[0]
# Test: eval_rpn(["2","1","+","3","*"]) == 9 ((2+1)*3)
# Test: eval_rpn(["4","13","5","/","+"]) == 6 (4+(13/5))