150. Evaluate Reverse Polish Notation (Medium)

Problem

Evaluate an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand can be an integer or another expression. Division between two integers truncates toward zero.

Example

• tokens = ["2","1","+","3","*"] → 9 (≡ (2 + 1) * 3)
• tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] → 22

LeetCode 150 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Stack with explicit if/elif branching

Standard RPN evaluation: push operands; on operator, pop two and apply.

Python

def eval_rpn(tokens: list[str]) -> int:
    stack = []                                    # L1: O(1)
    for tok in tokens:                            # L2: n iterations
        if tok in ("+", "-", "*", "/"):           # L3: O(1) check
            b = stack.pop()                       # L4: O(1) pop
            a = stack.pop()                       # L5: O(1) pop
            if tok == "+":                        # L6: O(1)
                stack.append(a + b)               # L7: O(1)
            elif tok == "-":
                stack.append(a - b)               # L8: O(1)
            elif tok == "*":
                stack.append(a * b)               # L9: O(1)
            else:
                stack.append(int(a / b))          # L10: O(1) truncate toward zero
        else:
            stack.append(int(tok))                # L11: O(1) parse + push
    return stack[0]                               # L12: O(1)

TypeScript

function evalRpn(tokens: string[]): number {
    const stack: number[] = [];                          // L1: O(1)
    for (const tok of tokens) {                          // L2: n iterations
        if (['+', '-', '*', '/'].includes(tok)) {        // L3: O(1) check
            const b = stack.pop()!;                      // L4: O(1) pop
            const a = stack.pop()!;                      // L5: O(1) pop
            if (tok === '+') stack.push(a + b);          // L6-L7: O(1)
            else if (tok === '-') stack.push(a - b);     // L8: O(1)
            else if (tok === '*') stack.push(a * b);     // L9: O(1)
            else stack.push(Math.trunc(a / b));          // L10: O(1) truncate toward zero
        } else {
            stack.push(Number(tok));                     // L11: O(1) parse + push
        }
    }
    return stack[0];                                     // L12: O(1)
}

Go

func evalRPN(tokens []string) int {
    stack := []int{}                              // L1: O(1)
    for _, tok := range tokens {                  // L2: n iterations
        switch tok {                              // L3: O(1) check
        case "+", "-", "*", "/":
            b := stack[len(stack)-1]              // L4: O(1) pop
            a := stack[len(stack)-2]              // L5: O(1) pop
            stack = stack[:len(stack)-2]
            switch tok {
            case "+": stack = append(stack, a+b) // L7: O(1)
            case "-": stack = append(stack, a-b) // L8: O(1)
            case "*": stack = append(stack, a*b) // L9: O(1)
            case "/": stack = append(stack, int(float64(a)/float64(b))) // L10: truncate toward zero
            }
        default:
            n, _ := strconv.Atoi(tok)
            stack = append(stack, n)              // L11: O(1) parse + push
        }
    }
    return stack[0]                               // L12: O(1)
}

Swift

final class Solution {
    func evalRPN(_ tokens: [String]) -> Int {
        var stack: [Int] = []
        for token in tokens {
            if let number = Int(token) { stack.append(number); continue }
            let right = stack.removeLast()
            let left = stack.removeLast()
            if token == "+" { stack.append(left + right) }
            else if token == "-" { stack.append(left - right) }
            else if token == "*" { stack.append(left * right) }
            else { stack.append(left / right) }
        }
        return stack.last ?? 0
    }
}

Where the time goes, line by line

Variables: n = len(tokens).

Line	Per-call cost	Times executed	Contribution
L2 (loop)	$O(1)$	n	$O(n)$
L3-L11 (per-token: push or pop+apply)	$O(1)$	n	$O(n)$ ← dominates
L12 (return)	$O(1)$	1	$O(1)$

Each token is processed in $O(1)$; one pass over all n tokens.

Complexity

• Time: $O(n)$, driven by L3-L11 (one push or pop+apply per token).
• Space: $O(n)$. Stack depth at most $O(n)$.

Approach 2: Stack with operator dictionary (cleaner)

Replace the if/elif branching with a dict of lambdas.

Python

def eval_rpn(tokens: list[str]) -> int:
    ops = {                                       # L1: O(1) constant dict
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "*": lambda a, b: a * b,
        "/": lambda a, b: int(a / b),             # truncate toward zero
    }
    stack = []                                    # L2: O(1)
    for tok in tokens:                            # L3: n iterations
        if tok in ops:                            # L4: O(1) dict lookup
            b = stack.pop()                       # L5: O(1)
            a = stack.pop()                       # L6: O(1)
            stack.append(ops[tok](a, b))          # L7: O(1) apply lambda
        else:
            stack.append(int(tok))                # L8: O(1) parse + push
    return stack[0]                               # L9: O(1)

TypeScript

function evalRpn(tokens: string[]): number {
    const ops: Record<string, (a: number, b: number) => number> = {   // L1: O(1)
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => Math.trunc(a / b),                              // truncate toward zero
    };
    const stack: number[] = [];                                        // L2: O(1)
    for (const tok of tokens) {                                        // L3: n iterations
        if (tok in ops) {                                              // L4: O(1) dict lookup
            const b = stack.pop()!;                                    // L5: O(1)
            const a = stack.pop()!;                                    // L6: O(1)
            stack.push(ops[tok](a, b));                                // L7: O(1) apply
        } else {
            stack.push(Number(tok));                                   // L8: O(1) parse + push
        }
    }
    return stack[0];                                                   // L9: O(1)
}

Go

func evalRPN(tokens []string) int {
    ops := map[string]func(int, int) int{           // L1: O(1) constant map
        "+": func(a, b int) int { return a + b },
        "-": func(a, b int) int { return a - b },
        "*": func(a, b int) int { return a * b },
        "/": func(a, b int) int { return int(float64(a) / float64(b)) }, // truncate toward zero
    }
    stack := []int{}                                // L2: O(1)
    for _, tok := range tokens {                    // L3: n iterations
        if fn, ok := ops[tok]; ok {                 // L4: O(1) map lookup
            b := stack[len(stack)-1]               // L5: O(1)
            a := stack[len(stack)-2]               // L6: O(1)
            stack = stack[:len(stack)-2]
            stack = append(stack, fn(a, b))        // L7: O(1) apply
        } else {
            n, _ := strconv.Atoi(tok)
            stack = append(stack, n)               // L8: O(1) parse + push
        }
    }
    return stack[0]                                // L9: O(1)
}

Swift

final class Solution {
    func evalRPN(_ tokens: [String]) -> Int {
        let operators: [String: (Int, Int) -> Int] = [
            "+": { $0 + $1 }, "-": { $0 - $1 }, "*": { $0 * $1 }, "/": { $0 / $1 },
        ]
        var stack: [Int] = []
        for token in tokens {
            if let number = Int(token) { stack.append(number); continue }
            let right = stack.removeLast()
            let left = stack.removeLast()
            if let operation = operators[token] { stack.append(operation(left, right)) }
        }
        return stack.last ?? 0
    }
}

Where the time goes, line by line

Variables: n = len(tokens).

Line	Per-call cost	Times executed	Contribution
L1 (init ops dict)	$O(1)$	1	$O(1)$
L3 (loop)	$O(1)$	n	$O(n)$
L4-L8 (per-token: push or apply)	$O(1)$	n	$O(n)$ ← dominates
L9 (return)	$O(1)$	1	$O(1)$

Functionally identical to Approach 1; easier to extend (new operators) and easier to read.

Complexity

• Time: $O(n)$, driven by L4-L8 (one push or pop+apply per token).
• Space: $O(n)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space	Notes
Stack + if/elif	$O(n)$	$O(n)$	Verbose
Stack + operator dict	$O(n)$	$O(n)$	Cleanest

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_eval_rpn.py and run.
# Uses the canonical implementation (Approach 2: stack + operator dict).

def eval_rpn(tokens: list[str]) -> int:
    ops = {
        "+": lambda a, b: a + b,
        "-": lambda a, b: a - b,
        "*": lambda a, b: a * b,
        "/": lambda a, b: int(a / b),
    }
    stack = []
    for tok in tokens:
        if tok in ops:
            b = stack.pop()
            a = stack.pop()
            stack.append(ops[tok](a, b))
        else:
            stack.append(int(tok))
    return stack[0]

def _run_tests():
    assert eval_rpn(["2","1","+","3","*"]) == 9
    assert eval_rpn(["4","13","5","/","+"]) == 6
    assert eval_rpn(["10","6","9","3","+","-11","*","/","*","17","+","5","+"]) == 22
    assert eval_rpn(["3"]) == 3
    assert eval_rpn(["6","2","/"]) == 3      # truncate toward zero
    assert eval_rpn(["7","2","/"]) == 3      # truncate: 7/2 = 3.5 → 3
    assert eval_rpn(["-7","2","/"]) == -3    # truncate toward zero: -3.5 → -3
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function evalRpn(tokens: string[]): number {
    const ops: Record<string, (a: number, b: number) => number> = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => Math.trunc(a / b),
    };
    const stack: number[] = [];
    for (const tok of tokens) {
        if (tok in ops) {
            const b = stack.pop()!;
            const a = stack.pop()!;
            stack.push(ops[tok](a, b));
        } else {
            stack.push(Number(tok));
        }
    }
    return stack[0];
}

console.assert(evalRpn(['2', '1', '+', '3', '*']) === 9);
console.assert(evalRpn(['4', '13', '5', '/', '+']) === 6);
console.assert(evalRpn(['3']) === 3);
console.assert(evalRpn(['6', '2', '/']) === 3);
console.assert(evalRpn(['7', '2', '/']) === 3);
console.assert(evalRpn(['-7', '2', '/']) === -3);
console.log('all tests pass');

Related data structures

• Stacks, postfix evaluation is the textbook stack use case

Related concepts

• Stack Parsing, the last open, first closed model for nested syntax and reversible operations.
• Simulation, the explicit state model for executing rules exactly while keeping cases organized.