Evaluate Reverse Polish Notation

Reverse Polish Notation is built so the last token is always the root operator of the whole expression, and its two operands are whatever comes immediately before it, recursively. That means we can evaluate it by popping tokens off the end: if the last token is a number, that is the answer; if it is an operator, recursively evaluate its right operand, then its left operand, and combine them. The recursion’s call stack is doing exactly the same job an explicit stack would.

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

        def helper() -> int:
            token = tokens.pop()
            if token not in ops:
                return int(token)
            right = helper()
            left = helper()
            if token == '+':
                return left + right
            if token == '-':
                return left - right
            if token == '*':
                return left * right
            return int(left / right)

        return helper()

This works and is O(n) time, O(n) space (recursion depth plus mutating the input list), but relying on an implicit call stack — and destructively popping the input — is fragile and harder to reason about than making the stack explicit.

Scan tokens left to right with a stack. Every number gets pushed. Every operator pops its two operands — the second-to-top is the left operand, the top is the right operand, since RPN lists operands before the operator that combines them — computes the result, and pushes it back. By the time we reach the end, the stack holds exactly one value: the answer.

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack = []
        ops = {'+', '-', '*', '/'}
        for token in tokens:
            if token in ops:
                b = stack.pop()
                a = stack.pop()
                if token == '+':
                    result = a + b
                elif token == '-':
                    result = a - b
                elif token == '*':
                    result = a * b
                else:
                    result = int(a / b)  # truncate toward zero
                stack.append(result)
            else:
                stack.append(int(token))
        return stack[0]

Tracing tokens = ["2","1","+","3","*"] (trace data lives in this problem folder’s data.ts):

The final and only element left on the stack, 9, is the answer. Note int(a / b) (not Python’s floor division //) to truncate toward zero, matching the constraint — this matters for negative operands, e.g. -7 / 2 must give -3, not -4. Complexity: each token is processed once with O(1) work → O(n) time; the stack holds at most O(n) values.