MediumNeetCode150ArrayStackMath
Evaluate Reverse Polish Notation
Evaluate arithmetic expression in Reverse Polish Notation.
Examples
Input
tokens = ["2","1","+","3","*"]
Output
9
(2+1)*3=9
Constraints
- •
1 <= tokens.length <= 10^4 - •
tokens[i] is operator or integer
Approaches
Push numbers, pop on operator.
CodeT: O(n) | S: O(n) stack
def evalRPN(tokens):
stack=[]
for t in tokens:
if t in '+-*/':
b,a=stack.pop(),stack.pop()
if t=='+': stack.append(a+b)
elif t=='-': stack.append(a-b)
elif t=='*': stack.append(a*b)
else: stack.append(int(a/b))
else: stack.append(int(t))
return stack[0]Same approach.
CodeT: O(n) | S: O(n)
def evalRPN(tokens):
stack=[]
for t in tokens:
if t in '+-*/':
b,a=stack.pop(),stack.pop()
stack.append({'+':a+b,'-':a-b,'*':a*b,'/':int(a/b)}[t])
else: stack.append(int(t))
return stack[0]Same approach.
Diagram
Use dict for operator->function mapping
CodeT: O(n) | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Stack | O(n) | O(n) stack | Push numbers, pop on operator. |
| Stack - Optimized | O(n) | O(n) | Same approach. |
| Stack - Dictionary Lookup | O(n) | O(n) | Same approach. |
Stack
T: O(n)S: O(n) stack
Push numbers, pop on operator.
Stack - Optimized
T: O(n)S: O(n)
Same approach.
Stack - Dictionary Lookup
T: O(n)S: O(n)
Same approach.
Common Mistakes
Not handling negative division
Off-by-one in pop order
Integer division