Evaluate Reverse Polish Notation

Problem

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

Evaluate the expression and return an integer that represents the value of the expression.

Note:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in RPN.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 22

Constraints:

1 <= tokens.length <= 10^4
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Solution

Approach: Stack-Based Evaluation

The key insight is that RPN is naturally suited for stack-based evaluation. When we encounter a number, we push it. When we encounter an operator, we pop two operands, apply the operation, and push the result back.

Algorithm:

Iterate through each token
If it’s a number, push onto the stack
If it’s an operator, pop two operands, apply the operation, and push the result
The final answer is the only element left on the stack

Implementation

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operators = {'+', '-', '*', '/'}

        for token in tokens:
            if token in operators:
                # Pop two operands (order matters for - and /)
                b = stack.pop()
                a = stack.pop()

                if token == '+':
                    result = a + b
                elif token == '-':
                    result = a - b
                elif token == '*':
                    result = a * b
                else:  # token == '/'
                    # Truncate toward zero
                    result = int(a / b)

                stack.append(result)
            else:
                # It's a number
                stack.append(int(token))

        return stack[0]

Alternative (Using Dictionary for Operations):

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

        operations = {
            '+': lambda a, b: a + b,
            '-': lambda a, b: a - b,
            '*': lambda a, b: a * b,
            '/': lambda a, b: int(a / b)
        }

        for token in tokens:
            if token in operations:
                b = stack.pop()
                a = stack.pop()
                stack.append(operations[token](a, b))
            else:
                stack.append(int(token))

        return stack[0]

Complexity Analysis

Time Complexity: O(n), where n is the number of tokens. We process each token exactly once.
Space Complexity: O(n) in the worst case, when all tokens are numbers and we push them all onto the stack.

Key Insights

RPN and Stacks: Reverse Polish Notation is designed for stack-based evaluation. Numbers are pushed, operators consume operands from the stack.
Operand Order: When popping operands for non-commutative operations (subtraction and division), the order matters. The second pop is the first operand: a = pop(), b = pop() means we compute b op a.
Truncation Toward Zero: Python’s / operator returns a float, and int() truncates toward zero (e.g., int(-3/2) = int(-1.5) = -1). This differs from // which floors (would give -2).
Valid Expression Guarantee: Since the input is guaranteed to be valid, we don’t need to check for stack underflow or invalid operators. The final stack will have exactly one element.