Work out an expression written with operators after their numbers. Push each number on a stack; each operator pops two and pushes the result.
▼The problem
LeetCode 150 (Medium). Given an array of string tokens in Reverse Polish (postfix) Notation, with the operators +, -, * and /, return the value of the expression. Division between two integers truncates toward zero; the input is always valid and never divides by zero.
Examples (LeetCode's): ["2","1","+","3","*"] → 9 ((2 + 1) × 3), ["4","13","5","/","+"] → 6 (4 + 13 / 5) and ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] → 22.
The solution
def evalRPN(tokens):
stack = []
for tok in tokens:
if tok in "+-*/":
b = stack.pop()
a = stack.pop()
if tok == "+": stack.append(a + b)
elif tok == "-": stack.append(a - b)
elif tok == "*": stack.append(a * b)
else: stack.append(int(a / b))
else:
stack.append(int(tok))
return stack[0]Transcript
Evaluate Reverse Polish Notation. Each operator follows its two numbers, so two, one, plus means two plus one. Given the tokens, return the value. Division truncates toward zero.
Take two, one, plus, three, times. Two plus one is three, times three is nine. Or four, thirteen, five, divide, plus. Thirteen over five is two, plus four is six.
The slow way: scan for two numbers followed by an operator, collapse them into one, then scan again from the start. Up to n passes over n tokens, so that's order n squared.
The trick is one stack. Picture a pancake griddle. Every number is a pancake flipped onto the plate. Every operator is a chef who lifts the top two, b on top, then a, and presses them into one: a operator b. Order matters for minus and divide.
In code, for each token: if it's an operator, pop b, then a, and push a op b, dividing with int of a over b. Otherwise, push the number. Return the last value.
Now the big one. Ten, six, nine, three land. Plus: nine plus three is twelve. Minus eleven lands. Times: twelve times minus eleven is minus one hundred thirty-two. Divide: six over minus one hundred thirty-two is zero, truncated toward zero. Floor division would give minus one. Times: ten times zero, zero. Seventeen, plus: seventeen. Five, plus: twenty-two.
Each token means one push, and each operator two pops, so it's order n time. The plate holds at most n pancakes: order n space.
Push, pop, combine. That's Evaluate Reverse Polish Notation.