Domain 2MediumCORE

Evaluate Reverse Polish Notation

We need to evaluate a mathematical expression given in Reverse Polish Notation (RPN), also known as postfix notation. In this format, the operator follows its operands (e.g., 2 1 + means 2 + 1). The input is an array of strings where each string represents either an integer or one of four operators: +, -, *, /.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Stack

150. Evaluate Reverse Polish Notation

Model: qwen3.5:9b
Topics: Stack
FAANG asked: 1
Acceptance rate: 38.2%


Problem Breakdown

We need to evaluate a mathematical expression given in Reverse Polish Notation (RPN), also known as postfix notation. In this format, the operator follows its operands (e.g., 2 1 + means 2 + 1). The input is an array of strings where each string represents either an integer or one of four operators: +, -, *, /.

Inputs: A list of tokens (tokens) representing numbers and operators. Outputs: An integer result after evaluating the expression. Constraints & Edge Cases:

  1. Division Truncation: The problem specifies division truncates toward zero (e.g., -3 / 2 should be -1, not -2). Python’s // operator floors towards negative infinity, so we must handle this carefully using standard float division cast to int or math.trunc.
  2. Negative Numbers: Tokens can represent negative integers (e.g., " -5 "). We need to ensure our parsing logic distinguishes between a unary minus in the token and binary subtraction operators correctly based on context, though RPN validity guarantees we won’t see an operator without two preceding operands.
  3. Stack Depth: The maximum stack depth corresponds to the number of consecutive operands before any operation occurs.

Intuition

If I try to evaluate this recursively or by parsing it as infix notation first, that adds unnecessary complexity and overhead (converting RPN to Infix is non-trivial).

The core property of Reverse Polish Notation is that you never need parentheses because the order of operations is implicit in the sequence. When we encounter a number, we store it for later use. When we encounter an operator, we know exactly which two numbers to operate on: they are the most recently pushed values onto our memory structure.

This “Last In First Out” requirement screams Stack.

A brute-force approach might try all permutations or recursive parsing without state management, leading to O(N!)O(N!) complexity in worst cases for invalid inputs (though input is guaranteed valid here). The stack-based linear scan ensures we process each token exactly once with constant time operations per token.

Approach

  1. Initialize an empty list stack to act as our data structure.
  2. Iterate through every token in the input array:
    • Check if Operator: If the token is one of {+, -, *, /}, we know it’s time to perform a calculation. We pop the top two elements from the stack (let’s call them b and then a, since the first popped element was pushed after the second). Compute op(a, b). Push the result back onto the stack.
    • Check if Operand: If it is not an operator, convert to integer and push directly onto the stack. Note: We must check for operators explicitly because a token like " -5 " starts with -, which looks like subtraction but represents a negative number operand in RPN context (though typically parsed as string first).
  3. After iterating through all tokens, there will be exactly one value left on the stack—the final result. Return it.

Complexity Analysis

  • Time Complexity: O(N)O(N) where NN is tokens.length. We iterate through the list once. Stack push and pop operations are amortized O(1)O(1). Total work per token is constant time arithmetic or string conversion.
  • Space Complexity: O(N)O(N) for the stack in the worst case (e.g., a sequence of operands followed by one operator). In practice, this could be less depending on expression structure, but we must allocate space proportional to input size.

Solution

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        
        # Define operators for quick lookup
        ops = {"+", "-", "*", "/"}
        
        for token in tokens:
            if token not in ops:
                # It's an operand (number)
                stack.append(int(token))
            else:
                # It's an operator, pop two operands
                b = stack.pop()
                a = stack.pop()
                
                if token == "+":
                    res = a + b
                elif token == "-":
                    res = a - b
                elif token == "*":
                    res = a * b
                else: # division "/"
                    # Python's // floors towards negative infinity. 
                    # Problem requires truncation toward zero (e.g., int(-3/2) -> -1).
                    # Using float division then casting to int handles this correctly.
                    res = int(a / b)
                
                stack.append(res)
        
        return stack[0]

Edge Cases Handled

  • Negative Operands: The code treats " -5 " as a string that converts directly via int(), distinguishing it from the operator logic. Since RPN is valid, we won’t encounter an operator without sufficient operands on the stack to handle unary negation if necessary (though standard binary operators are used here).
  • Division Truncation: Explicitly using int(a / b) ensures -3/2 becomes -1, matching C++ behavior and problem constraints rather than Python’s default floor division.
  • Single Result Guarantee: The loop processes all tokens, leaving exactly one integer on the stack at termination due to valid RPN guarantees (no leftover operators).