Evaluate Reverse Polish Notation

Stack evaluation

Stack as an accumulator. This pattern scales to expression parsing.

Published Apr 15, 2026

Problem

You are given an array of tokens representing a Reverse Polish Notation expression.

Evaluate the expression and return its integer result. The operators are +, -, *, and /. Division truncates toward zero.

Input

tokens = ["2","1","+","3","*"]

Output

Explanation

((2 + 1) * 3) = 9.

Input

tokens = ["4","13","5","/","+"]

Output

Explanation

13 / 5 truncates to 2, so 4 + 2 = 6.

Intuition

RPN is postfix notation: every operator appears after its operands. That means you never need precedence rules or parentheses. The expression can be evaluated left to right with one stack.

When you see a number, push it. When you see an operator, pop the last two numbers, apply the operator, and push the result back.

The only subtlety is operand order. For a - b and a / b, the second pop is the right operand, not the left one.

Approach

Stack Evaluation

TimeO(n)

SpaceO(n)

Recommended

Scan the tokens once. Push numbers. On an operator, pop b, pop a, compute a op b, and push the result.

There is no backtracking and no tree construction. The stack itself is the evaluator.

impl Solution {
    pub fn eval_rpn(tokens: Vec<String>) -> i32 {
        let mut stack: Vec<i32> = Vec::with_capacity(tokens.len());

        for token in tokens {
            match token.as_str() {
                "+" | "-" | "*" | "/" => {
                    let b = stack.pop().unwrap();
                    let a = stack.pop().unwrap();
                    let value = match token.as_str() {
                        "+" => a + b,
                        "-" => a - b,
                        "*" => a * b,
                        "/" => a / b,
                        _ => unreachable!(),
                    };
                    stack.push(value);
                }
                _ => stack.push(token.parse::<i32>().unwrap()),
            }
        }

        stack.pop().unwrap()
    }
}

Rust · runnable

function evalRPN(tokens: string[]): number {
  const stack: number[] = [];

  for (const token of tokens) {
    if (token === "+" || token === "-" || token === "*" || token === "/") {
      const b = stack.pop()!;
      const a = stack.pop()!;

      switch (token) {
        case "+":
          stack.push(a + b);
          break;
        case "-":
          stack.push(a - b);
          break;
        case "*":
          stack.push(a * b);
          break;
        case "/":
          stack.push(Math.trunc(a / b));
          break;
      }
    } else {
      stack.push(Number(token));
    }
  }

  return stack[0];
}

TypeScript · runnable

Language notes:

Rust — integer division already truncates toward zero, which matches the problem statement.
TypeScript — use Math.trunc(a / b), not Math.floor, because negative division must truncate toward zero, not toward -∞.

Trace

Evaluate ["2", "1", "+", "3", "*"]:

token	stack before	action	stack after
2	[]	push 2	[2]
1	[2]	push 1	[2, 1]
+	[2, 1]	pop 1, pop 2, push 3	[3]
3	[3]	push 3	[3, 3]
*	[3, 3]	pop 3, pop 3, push 9	[9]

The stack never holds more values than the expression has unresolved subresults.

Edge cases

Non-commutative operators — always pop b first and a second.
Negative intermediate values — allowed; they behave exactly like any other integer.
Division semantics — truncation toward zero is required, so -3 / 2 becomes -1.

💡

Tip

RPN is just "compiler output without the compiler". If you ever need to evaluate an infix expression, converting it to postfix or parsing it into a stack/AST is the same underlying idea.

Takeaway

When the input already encodes evaluation order, the stack becomes the execution engine. That is the big idea behind postfix notation and a lot of parser and interpreter code.

Once you see "operator after operands", the algorithm is usually one pass and one stack.

Easy#20

Valid Parentheses

The stack’s ‘hello world’. Match most-recent open bracket.

Medium#155

Min Stack

Auxiliary structure trick: maintain a parallel stack of minimums.

Medium#739

Daily Temperatures

Your first monotonic stack! ‘Next greater element’ pattern.