Evaluate reverse Polish notation
We'll cover the following
Evaluate an expression where the operator comes after its two numbers, like "2 1 + 3 *".
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
push50
11
22
+3
44
*5
+6
37
-8
29
310
*11
+12
5 is a number. Push it.
stack [5]
1 / 14
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(n) | One pass over the tokens; the stack holds pending operands. |
In Python
def eval_rpn(tokens):
st = []
for t in tokens:
if t in '+-*/':
b, a = st.pop(), st.pop()
st.append(a + b if t == '+' else a - b if t == '-'
else a * b if t == '*' else int(a / b))
else:
st.append(int(t))
return st[0]Summary: say it in the interview
- Push numbers. When an operator shows up, pop two numbers, apply it, and push the result. The stack holds exactly the values that are still waiting for an operator.
- Time O(n), space O(n). One pass over the tokens; the stack holds pending operands.