LeetCode 150: Evaluate Reverse Polish Notation Solution in Python Explained

Problem Statement

In LeetCode 150, you’re given an array tokens representing an arithmetic expression in Reverse Polish Notation (postfix notation), where operands precede operators (e.g., "2 3 +" instead of "2 + 3"). Your task is to evaluate the expression and return the integer result, handling addition, subtraction, multiplication, and division. This differs from geometric problems like LeetCode 149: Max Points on a Line, focusing on expression evaluation rather than point alignment.

Constraints

• 1 <= tokens.length <= 10^4
• tokens[i] is a number ("-200" to "200") or an operator ("+", "-", "*", "/")
• The expression is valid and evaluates to an integer in [-2^31, 2^31 - 1]
• Division truncates toward zero

Example

Let’s see some cases:

Copy codeInput: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
<ul>
<li>"2 1 +" → 3</li>
<li>"3 3 *" → 9</li>
</ul>

Copy codeInput: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6
<ul>
<li>"13 5 /" → 2 (truncated)</li>
<li>"4 2 +" → 6</li>
</ul>

Copy codeInput: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22
<ul>
<li>Step-by-step: 12, -11, -132, 6, 0, 17, 22</li>
</ul>

These examples show we’re evaluating RPN expressions.

Understanding the Problem

How do you solve LeetCode 150: Evaluate Reverse Polish Notation in Python? Take tokens = ["2","1","+","3","*"]. In RPN, "2 1 +" evaluates to 3, then "3 3 " becomes 9—result is 9. For ["4","13","5","/","+"], "13 5 /" is 2, then "4 2 +" is 6. This isn’t a list sorting problem like LeetCode 148: Sort List; it’s about stack-based expression evaluation. We’ll use: 1. Stack-Based Evaluation: O(n) time, O(n) space—our best solution. 2. Recursive Evaluation*: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Stack-Based Evaluation Approach

Explanation

Stack-Based Evaluation uses a stack to process RPN tokens:

• Push numbers onto the stack.
• For operators, pop two operands, apply the operation, and push the result.
• Continue until all tokens are processed, with the final result on the stack.

This is the best solution due to its O(n) time complexity, O(n) space (stack size), and straightforward iterative approach, aligning perfectly with RPN’s postfix nature for efficient evaluation.

For ["2","1","+","3","*"]:

• Push 2, 1 → [2,1].
• "+" → Pop 1, 2, push 3 → [3].
• Push 3 → [3,3].
• "*" → Pop 3, 3, push 9 → [9].
• Result: 9.

Step-by-Step Example

Example 1: tokens = ["2","1","+","3","*"]

Goal: Return 9.

• Start: stack = [].
• Step 1: Token "2", push 2, stack = [2].
• Step 2: Token "1", push 1, stack = [2,1].
• Step 3: Token "+".
• Pop 1, 2, 2+1 = 3, push 3, stack = [3].
• Step 4: Token "3", push 3, stack = [3,3].
• Step 5: Token "*".
• Pop 3, 3, 3*3 = 9, push 9, stack = [9].
• Finish: Return 9.

Example 2: tokens = ["4","13","5","/","+"]

Goal: Return 6.

• Start: stack = [].
• Step 1: Push 4, stack = [4].
• Step 2: Push 13, stack = [4,13].
• Step 3: Push 5, stack = [4,13,5].
• Step 4: "/".
• Pop 5, 13, 13//5 = 2 (truncate), push 2, stack = [4,2].
• Step 5: "+".
• Pop 2, 4, 4+2 = 6, push 6, stack = [6].
• Finish: Return 6.

Example 3: tokens = ["10","6","9","3","+","-11","","/","","17","+","5","+"]

Goal: Return 22.

• Start: stack = [].
• Steps: Process tokens:
• Push 10, 6, 9, 3 → [10,6,9,3].
• "+" → 9+3=12, [10,6,12].
• Push -11 → [10,6,12,-11].
• "*" → 12*-11=-132, [10,6,-132].
• "/" → 6//-132=0, [10,0].
• "*" → 10*0=0, [0].
• Push 17 → [0,17].
• "+" → 0+17=17, [17].
• Push 5 → [17,5].
• "+" → 17+5=22, [22].
• Finish: Return 22.

How the Code Works (Stack-Based Evaluation) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef evalRPN(tokens: list[str]) -> int:
    # Line 1: Initialize stack
    stack = []
    # Stores operands (e.g., initially [])

    # Line 2: Define operators set
    operators = {'+', '-', '*', '/'{
    # Set for O(1) lookup (e.g., {"+","-","*","/"{)

    # Line 3: Process each token
    for token in tokens:
        # token = current element (e.g., "2", "+", "3")

        # Line 4: Check if token is an operator
        if token in operators:
            # If operator (e.g., "+")

            # Line 5: Pop operands in reverse order
            b = stack.pop()
            # Second operand (e.g., 1)
            a = stack.pop()
            # First operand (e.g., 2)

            # Line 6: Evaluate based on operator
            if token == '+':
                stack.append(a + b)
                # e.g., 2+1=3
            elif token == '-':
                stack.append(a - b)
                # e.g., 4-2=2
            elif token == '*':
                stack.append(a * b)
                # e.g., 3*3=9
            else:  # "/"
                # Handle division with truncation
                stack.append(int(a / b))
                # e.g., 13/5=2 (truncates toward zero)
        else:
            # Line 7: Push number
            stack.append(int(token))
            # Convert string to int (e.g., "2"→2)
            # e.g., stack=[2,1]

    # Line 8: Return final result
    return stack[0]
    # Single value left (e.g., 9)

This detailed breakdown clarifies how stack-based evaluation efficiently computes the RPN result.

Alternative: Recursive Evaluation Approach

Explanation

Recursive Evaluation processes the RPN expression by recursively evaluating subexpressions from the end, popping tokens and applying operators to operands. It’s a practical alternative, also O(n) time with O(n) space (recursion stack), but less intuitive and potentially less efficient due to recursion overhead.

For ["2","1","+","3","*"]:

• Recurse: "3 *" on [3], then "+ 3" on [2,1], result = 9.

Step-by-Step Example (Alternative)

For ["2","1","+","3","*"]:

• Start: evaluate(tokens).
• Step 1: Token "*" → Pop "3", evaluate "+" → Pop "1", "2", 2+1=3, 3*3=9.
• Finish: Return 9.

How the Code Works (Recursive)

Copy codedef evalRPNRecursive(tokens: list[str]) -> int:
    def evaluate(tokens):
        token = tokens.pop()
        if token in {'+', '-', '*', '/'{:
            b = evaluate(tokens)
            a = evaluate(tokens)
            if token == '+':
                return a + b
            elif token == '-':
                return a - b
            elif token == '*':
                return a * b
            else:
                return int(a / b)
        return int(token)

    return evaluate(tokens[:])  # Copy to avoid modifying input

Complexity

• Stack-Based Evaluation:
• Time: O(n) – single pass.
• Space: O(n) – stack size.
• Recursive Evaluation:
• Time: O(n) – processes each token.
• Space: O(n) – recursion stack.

Efficiency Notes

Stack-Based Evaluation is the best solution with O(n) time and O(n) space, offering simplicity and iterative efficiency—Recursive Evaluation matches complexity but incurs recursion overhead, making it a clear but less preferred alternative.

Key Insights

• RPN: Postfix eliminates parentheses.
• Stack: Natural for postfix.
• Recursion: Top-down evaluation.

Additional Example

For tokens = ["3","4","*"]:

• Goal: 12.
• Stack: Push 3, 4, 3*4=12.

Edge Cases

• Single Number: ["5"] → 5.
• Negative: ["-1","2","+"] → 1.
• Division: ["10","3","/"] → 3.

Both solutions handle these well.

Final Thoughts

LeetCode 150: Evaluate Reverse Polish Notation in Python is a delightful evaluation challenge. The Stack-Based Evaluation solution excels with its efficiency and clarity, while Recursive Evaluation offers a recursive perspective. Want more? Try LeetCode 148: Sort List for list sorting or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 150 on LeetCode with ["2","1","+","3","*"], aiming for 9—test your skills now!