Core Insight Keep only items whose matching decision has not been made yet.
Common Pitfall Check that the stack is non-empty before reading its top.
Description
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(n)
Tags
arraymathstack
Implementation Plan Translate the invariant into these small, testable moves.
- Read one item at a time.
- Push unresolved work.
- Match or remove work when its partner arrives.
- Validate the final stack state.
def evalRPN(tokens):
stack = []
for c in tokens:
if c == "+":
stack.append(stack.pop() + stack.pop())
elif c == "-":
a, b = stack.pop(), stack.pop()
stack.append(b - a)
elif c == "*":
stack.append(stack.pop() * stack.pop())
elif c == "/":
a, b = stack.pop(), stack.pop()
stack.append(int(float(b) / a))
else:
stack.append(int(c))
return stack[0]