NeetCode #351LC-150MediumStackNC 150NC 250
← Back to All Problems#351 · #150 · Evaluate Reverse Polish Notation(逆波兰表达式求值)
📌 Problem Statement & Constraints
You are given an array of strings
tokens representing an arithmetic expression in Reverse Polish Notation. Evaluate it and return the integer result. Valid operators are +, -, * and /, and division truncates toward zero. Constraints: 1 <= tokens.length <= 10^4; the expression is always valid.💡 Core Algorithmic Approaches
- Push operands onto a stack; on an operator, pop two operands, apply the operator, and push the result.
- Order matters for non-commutative operators: the first pop is the right operand and the second is the left.
- Integer division must truncate toward zero, which differs from Python's floor division for negative operands.
- At the end the stack holds exactly one value, the answer.
💻 Benchmark Python3 Implementation
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
st = []
for tok in tokens:
if tok in ("+", "-", "*", "/"):
b = st.pop() # right operand
a = st.pop() # left operand
if tok == "+":
st.append(a + b)
elif tok == "-":
st.append(a - b)
elif tok == "*":
st.append(a * b)
else:
# truncate toward zero, not floor
st.append(int(a / b))
else:
st.append(int(tok))
return st[0]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each token is processed once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Swapping the operand order:
a - banda / bare not commutative; the first pop isb. - Using
a // b: Python's floor division rounds toward negative infinity, so-7 // 2 == -4while the expected answer is -3. Useint(a / b). - Assuming operands are always multi-digit: single characters are tokens, so
int(tok)works, but thein ("+", "-", "*", "/")test avoids misclassifying a negative number. - Trying to parse the expression left to right without a stack: RPN is designed for stack evaluation.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.