⚡Flashcard Drill➔
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

  1. Push operands onto a stack; on an operator, pop two operands, apply the operator, and push the result.
  2. Order matters for non-commutative operators: the first pop is the right operand and the second is the left.
  3. Integer division must truncate toward zero, which differs from Python's floor division for negative operands.
  4. 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 - b and a / b are not commutative; the first pop is b.
  • Using a // b: Python's floor division rounds toward negative infinity, so -7 // 2 == -4 while the expected answer is -3. Use int(a / b).
  • Assuming operands are always multi-digit: single characters are tokens, so int(tok) works, but the in ("+", "-", "*", "/") 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems