practice · medium · from Stacks

Evaluate Postfix Expression

time: O(n)
space: O(n)
tags: stacks · parsing

in the wild RPN calculators (HP-35), JVM bytecode VMs, the WebAssembly stack machine — all evaluate expressions exactly like this.

Problem

Evaluate an arithmetic expression in Reverse Polish Notation (also called postfix). Each token is either an integer or one of the operators +, -, *, /. Operators apply to the two most recently emitted values.

Use integer division that truncates toward zero (the C / Rust default).

Examples

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

Why this is the canonical "stack as a computer" problem

Look at any tokenized RPN expression. Walk left-to-right. You can evaluate it with one rule:

If the token is a number → push it onto the stack.
If it's an operator → pop two values, apply the operator (the second-popped is the left operand), push the result.

Done. At the end, the single value left on the stack is the answer. No parser, no operator-precedence table, no parentheses to track. This is exactly how the original HP-35 calculator and modern stack machines (JVM bytecode, WebAssembly's value stack) evaluate expressions — they're literally executing this loop.

The reason it works: postfix encodes the evaluation order into the token order. Whatever's at the top of the stack when you hit an operator is precisely the right pair of operands.

Hints

Hint 1 — what the operands of + are

In postfix, when you see +, the two values immediately before it (after all their sub-expressions have been evaluated) are its operands. How would a stack maintain that "two most recent values" property naturally?

Hint 2 — order of pop

For non-commutative operators (- and /), the order matters. The second pop is the left operand; the first pop is the right operand. (You pushed a, then b, then operator → pop is b (right), then a (left).)

Hint 3 — integer division convention

For this problem, integer division truncates toward zero — same as C (/ on ints), Rust (i32 / i32), and modern C++. In Python you must use int(a / b) or hand-roll a // b if a*b >= 0 else -(-a // b) because // floors toward negative infinity.

Solution

def eval_rpn(tokens: list[str]) -> int:
    stack: list[int] = []
    for tok in tokens:
        if tok in ("+", "-", "*", "/"):
            right = stack.pop()
            left  = stack.pop()
            if   tok == "+": stack.append(left + right)
            elif tok == "-": stack.append(left - right)
            elif tok == "*": stack.append(left * right)
            else:
                # Truncate toward zero (NOT Python's floor division).
                q = abs(left) // abs(right)
                stack.append(q if (left < 0) == (right < 0) else -q)
        else:
            stack.append(int(tok))
    return stack[0]

cases = [
    (["2", "1", "+", "3", "*"],                                  9),
    (["4", "13", "5", "/", "+"],                                 6),
    (["10","6","9","3","+","-11","*","/","*","17","+","5","+"], 22),
]
for toks, expected in cases:
    got  = eval_rpn(toks)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} eval_rpn({toks}) = {got}  (expected {expected})")

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

const cases = [
  [["2", "1", "+", "3", "*"],                                       9],
  [["4", "13", "5", "/", "+"],                                      6],
  [["10","6","9","3","+","-11","*","/","*","17","+","5","+"],      22],
];
for (const [toks, expected] of cases) {
  const got = evalRpn(toks);
  console.log(`${got === expected ? "✓" : "✗"} evalRpn(${JSON.stringify(toks)}) = ${got}  (expected ${expected})`);
}

pub fn eval_rpn(tokens: &[&str]) -> i32 {
    let mut stack: Vec<i32> = Vec::new();
    for &tok in tokens {
        match tok {
            "+" | "-" | "*" | "/" => {
                let right = stack.pop().unwrap();
                let left  = stack.pop().unwrap();
                stack.push(match tok {
                    "+" => left + right,
                    "-" => left - right,
                    "*" => left * right,
                    "/" => left / right,   // Rust integer / truncates toward zero
                    _   => unreachable!(),
                });
            }
            _ => stack.push(tok.parse().unwrap()),
        }
    }
    stack[0]
}

fn main() {
    let cases: &[(&[&str], i32)] = &[
        (&["2", "1", "+", "3", "*"],                                  9),
        (&["4", "13", "5", "/", "+"],                                 6),
        (&["10","6","9","3","+","-11","*","/","*","17","+","5","+"], 22),
    ];
    for (toks, expected) in cases {
        let got  = eval_rpn(toks);
        let mark = if got == *expected { "✓" } else { "✗" };
        println!("{mark} eval_rpn({:?}) = {}  (expected {})", toks, got, expected);
    }
}

#include <iostream>
#include <stack>
#include <string>
#include <vector>

int eval_rpn(const std::vector<std::string>& tokens) {
    std::stack<int> stk;
    for (const auto& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int right = stk.top(); stk.pop();
            int left  = stk.top(); stk.pop();
            if      (t == "+") stk.push(left + right);
            else if (t == "-") stk.push(left - right);
            else if (t == "*") stk.push(left * right);
            else                stk.push(left / right);  // C++ int / truncates toward 0
        } else {
            stk.push(std::stoi(t));
        }
    }
    return stk.top();
}

int main() {
    struct Case { std::vector<std::string> toks; int expected; };
    std::vector<Case> cases = {
        { {"2", "1", "+", "3", "*"},                                  9},
        { {"4", "13", "5", "/", "+"},                                 6},
        { {"10","6","9","3","+","-11","*","/","*","17","+","5","+"}, 22},
    };
    for (auto& c : cases) {
        int got = eval_rpn(c.toks);
        std::cout << (got == c.expected ? "✓" : "✗") << " eval_rpn([";
        for (size_t i = 0; i < c.toks.size(); ++i)
            std::cout << c.toks[i] << (i + 1 < c.toks.size() ? "," : "");
        std::cout << "]) = " << got << "  (expected " << c.expected << ")\n";
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int eval_rpn(const char* tokens[], int n) {
    int* stack = malloc(n * sizeof(int));
    int  sp    = 0;
    for (int i = 0; i < n; i++) {
        const char* t = tokens[i];
        if ((t[0] == '+' || t[0] == '-' || t[0] == '*' || t[0] == '/') && t[1] == '\0') {
            int right = stack[--sp];
            int left  = stack[--sp];
            int r     = 0;
            switch (t[0]) {
                case '+': r = left + right; break;
                case '-': r = left - right; break;
                case '*': r = left * right; break;
                case '/': r = left / right; break;   // C int / truncates toward 0
            }
            stack[sp++] = r;
        } else {
            stack[sp++] = atoi(t);
        }
    }
    int answer = stack[0];
    free(stack);
    return answer;
}

int main(void) {
    const char* a[] = {"2", "1", "+", "3", "*"};
    printf("✓ eval_rpn(...) = %d  (expected 9)\n",  eval_rpn(a, 5));

    const char* b[] = {"4", "13", "5", "/", "+"};
    printf("✓ eval_rpn(...) = %d  (expected 6)\n",  eval_rpn(b, 5));

    const char* c[] = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};
    printf("✓ eval_rpn(...) = %d  (expected 22)\n", eval_rpn(c, 13));
    return 0;
}

idle

The only language-quirk worth flagging is Python's division: // floors (rounds toward negative infinity), but every other language's integer / truncates toward zero. For -7 / 2: Python // gives -4, C / Rust / C++ / JS (Math.trunc) all give -3. The Python solution above hand-rolls truncation-toward-zero to match.

Complexity

Time: O(n) — single pass through tokens; each operator does O(1) work.
Space: O(n) for the stack in the worst case (e.g. n/2 operands followed by n/2 operators).
vs infix evaluation: Evaluating infix (the math you write on paper) requires either the shunting-yard algorithm to convert to postfix first, or recursive-descent parsing. Postfix evaluation is the simple end of both pipelines.

In the wild

HP RPN calculators. The original 1972 HP-35 used this exact algorithm. Power users still swear by RPN for its no-parens, no-ambiguity input.
JVM bytecode. iadd, imul, etc. operate on the JVM's operand stack — every Java method runs as a tight loop of this evaluation pattern.
WebAssembly. The Wasm execution model is a value stack. Every Wasm instruction pops some, pushes some — postfix in disguise.
Forth and PostScript. Literally postfix programming languages.

Variations

Shunting-yard. Converts infix to postfix using two stacks — one for operators waiting for their operands, one for output. The full pipeline (infix → postfix → evaluate) is the cleanest expression parser there is.
RPN with variables and assignment. Add a symbol table; tokens like x push a lookup, tokens like = pop a value and a name and assign.
Expression trees. Build a tree as you scan postfix (operator nodes pop two child-trees from the stack). Useful for source-to-source transformations.