NEETCODE - Stack: Evaluate Reverse Polish Notation

1. Problem Statement

You are given an array of strings tokens that represents a valid arithmetic expression in Reverse Polish Notation (RPN).

Return the integer that represents the evaluation of the expression.

Rules

• The operands may be integers or the results of other operations
• The operators include '+', '-', '*', and '/'
• Assume that division between integers always truncates toward zero

Example 1

Input:

tokens = ["1", "2", "+", "3", "*", "4", "-"]

Output:

5

Explanation:

((1 + 2) * 3) - 4 = 5

Example 2

Input:

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

Output:

22

Constraints

• 1 <= tokens.length <= 1000
• tokens[i] is "+", "-", "*", or "/", or a string representing an integer in the range [-100, 100]`

2. Your Solution Review & Feedback

What You Implemented

You wrote two implementations of this problem:

First attempt:

class Solution:
    def __init__(self):
        self.stack = []

def push(self, value):
        self.stack.append(value)

def pop(self):
        return self.stack.pop()

def is_number(self, character: str) -> bool:
        try:
            int(character)
            return True
        except:
            return False

def evalRPN(self, tokens: List[str]) -> int:
        for character in tokens:
            if self.is_number(character):
                character_int = int(character)
                self.push(character_int)
            else:
                second_addend = self.pop()
                first_addend = self.pop()

if character == "+":
                    self.push(first_addend + second_addend)
                elif character == "-":
                    self.push(first_addend - second_addend)
                elif character == "*":
                    self.push(first_addend * second_addend)
                elif character == "/":
                    self.push(int(first_addend / second_addend))

return self.stack[0]

Second attempt:

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

for token in tokens:
            if token.strip("-").isdigit():
                stack.append(int(token))
            elif token == "+":
                a = stack.pop()
                b = stack.pop()
                stack.append(a + b)
            elif token == "-":
                a = stack.pop()
                b = stack.pop()
                stack.append(b - a)
            elif token == "*":
                a = stack.pop()
                b = stack.pop()
                stack.append(a * b)
            elif token == "/":
                a = stack.pop()
                b = stack.pop()
                stack.append(int(b / a))

return stack.pop()

What Worked Well

✅ Core algorithm is perfect: Both solutions correctly use a stack to evaluate RPN expressions.

✅ Correct operand order in second solution: In your second attempt, you correctly handle b - a and b / a (not a - b or a / b). This is crucial because subtraction and division are not commutative.

✅ Good progression: You showed improvement from first to second attempt, making the code cleaner.

✅ Handles negative numbers: Your second solution uses strip("-").isdigit() to handle negative numbers correctly.

Issues Identified

❌ Incorrect operand order in first solution:

When you pop from a stack, the order matters for non-commutative operations!

Overcomplicated number detection in first solution:

This works, but using bare except is bad practice. Should catch specific exception.

Your second solution uses a better approach: tokens[i].strip("-").isdigit().

Learning Points

1. Order matters for non-commutative operations: When popping two values from a stack for subtraction or division, remember that the first popped value is the second operand in the original expression.

2. Local variables > instance variables for stateless functions: Your second solution is better because it doesn't maintain state between calls.

3. Clear variable names matter: first_addend is confusing when it's actually the value that was pushed second. Generic names like a/b or right/left are clearer.

4. Python division quirks: int(a / b) truncates toward zero (correct for this problem).

Recommended Improvements

1. Iterate directly over tokens instead of using indices:

for token in tokens:
   if token.strip("-").isdigit():

2. Consider using a dictionary for operators to avoid the long elif chain:

ops = {
  "+": lambda a, b: b + a,
  "-": lambda a, b: b - a,
  "*": lambda a, b: b * a,
  "/": lambda a, b: int(b / a),
}
if token in ops:
   a = stack.pop()
   b = stack.pop()
   stack.append(ops[token](a, b))

Approach 1: Recursion (Not Optimal)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        def evaluate(index):
            token = tokens[index]

if token in "+-*/":  
                right, right_index = evaluate(index - 1)
                left, left_index = evaluate(right_index - 1)
                
                if token == "+":
                    result = left + right
                elif token == "-":
                    result = left - right
                elif token == "*":
                    result = left * right
                elif token == "/":
                    result = int(left / right)

return result, left_index
            else:
                return int(token), index - 1
        result, _ = evaluate(len(tokens) - 1)
        return result

Time Complexity: O(n) - visit each token once

Space Complexity: O(n) - recursion call stack depth

Why this doesn't work well:

• Overly complex for this problem
• Hard to understand and debug

Approach 2: Stack (Optimal)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        operand_stack = []

for current_token in tokens:
            if current_token in ["+", "-", "*", "/"]:
                right_operand = operand_stack.pop()
                left_operand = operand_stack.pop()
                if current_token == "+":
                    result = left_operand + right_operand
                elif current_token == "-":
                    result = left_operand - right_operand
                elif current_token == "*":
                    result = left_operand * right_operand
                elif current_token == "/":
                    result = int(left_operand / right_operand)
                operand_stack.append(result)
            else:
                operand_stack.append(int(current_token))
        return operand_stack[0]

Key insight: RPN eliminates the need for parentheses by using postfix notation. The stack naturally handles operator precedence because operators are applied immediately to their operands.

Common Mistakes

1. Wrong operand order for non-commutative operations:

result = left - right  # First popped is right operand

2. Using floor division for truncation:

result = int(left / right)  # Truncates toward zero

3. Not handling negative numbers in input:

if token not in operators:
    stack.append(int(token))  # int() handles negatives

4. Returning wrong result:

return stack[0]  # or stack.pop()

Interview Tips

Do's

• Clarify input format: "Are all tokens already split into a list?"
• Explain RPN concept: "In RPN, operators come after operands, so 3 + 4 becomes 3 4 +"
• Walk through an example: Draw the stack state after each token

Don'ts

• Don't confuse RPN with infix notation:
• Don't use // for division:
• Don't forget operand order:

12. Complexity Summary Table

Optimal Solution: Stack with O(n) time and O(n) space.