Stack crash course ↗ · 18

150. Evaluate Reverse Polish Notation

Reverse Polish Notation eliminates parentheses by placing operators after their operands. A single operand stack evaluates any RPN expression in one linear scan — numbers go on, operators pull two off and push the result.

● MediumStackExpression EvaluationTypeScript

PROBLEM What we're solving

Given a list of tokens representing an expression in Reverse Polish Notation, return its integer result. Operators are +, -, *, / (truncates toward zero). For example, ["2", "1", "+", "3", "*"] encodes (2 + 1) * 3 and returns 9. Similarly, ["4", "13", "5", "/", "+"] encodes 4 + (13 / 5) and returns 6 (since 13/5 = 2 after truncation).

KEY IDEA An operator always acts on the two most-recently-pushed numbers

Insight → in RPN, every operator immediately follows its two operands. So the top two values on a stack are always the correct operands for the current operator. Push numbers as you see them; on an operator, pop b (top) then a (next), compute a op b, and push the result. One pass, one stack — no parentheses or precedence rules needed.

RECIPE Push numbers, pop-pair on operators

  • 0 · Initialize. Create an empty number[] stack. It will hold the operands waiting to be consumed.
  • 1 · Scan left to right. For each token, decide: number or operator?
  • 2 · Number token. Parse it with parseInt and push onto the stack. Negative integers are valid tokens (e.g. "-3").
  • 3 · Operator token. Pop b = stack.pop() first (it was pushed second), then a = stack.pop(). Compute a op b and push the result. Order matters for - and /.
  • 4 · Return. After scanning all tokens the stack holds exactly one value — the answer. Return stack[0].
Classic confusion → when you pop two operands, which is a and which is b? The first pop gives b (the right operand — pushed later), and the second pop gives a (the left operand — pushed earlier). Getting this backwards produces the wrong sign on subtraction and a wrong quotient on division. The rule: pop b, pop a, compute a op b.

COST Complexity & alternatives

Recursive eval / parse tree
O(n)
Same time, but O(n) call-stack space and far more code.
Single operand stack
O(n)
O(n) time, O(n) stack space — trivial to code.

Space note

The stack grows at most to half the token count (all numbers, no operators yet). Worst case is O(n) stack entries. There is no constant-space alternative for a general RPN evaluator — you must hold intermediate results somewhere.

Pattern transfer → the same stack-of-operands pattern powers Basic Calculator (LC 224/227), Decode String (LC 394 — stack of partial results), Valid Parentheses (LC 20 — stack of open brackets), and any problem where an operator or closing delimiter needs to act on the most-recent data.

RUN IT Push numbers, pop & compute on operators

step 0 / 8
STARTStarting RPN evaluation. Stack is empty. We'll scan each token left-to-right.
1▶function evalRPN(tokens: string[]): number {
2▶  const stack: number[] = [];
3 
4  for (const tok of tokens) {
5    if (tok === '+' || tok === '-' || tok === '*' || tok === '/') {
6      const b = stack.pop()!;   // second operand (pushed last)
7      const a = stack.pop()!;   // first operand (pushed first)
8      if (tok === '+') stack.push(a + b);
9      else if (tok === '-') stack.push(a - b);
10      else if (tok === '*') stack.push(a * b);
11      else stack.push(Math.trunc(a / b));   // truncate toward zero
12    } else {
13      stack.push(parseInt(tok, 10));
14    }
15  }
16 
17  return stack[0];
18}
tokens2011+233*4
State
[]
stack
—
tok
active token / operands a & balready processed / stack contentsstack after popscomputed result / answer
slowfast

TYPESCRIPT The solution, annotated

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

  for (const tok of tokens) {
    if (tok === '+' || tok === '-' || tok === '*' || tok === '/') {
      const b = stack.pop()!;   // second operand (pushed last)
      const a = stack.pop()!;   // first operand (pushed first)
      if (tok === '+') stack.push(a + b);
      else if (tok === '-') stack.push(a - b);
      else if (tok === '*') stack.push(a * b);
      else stack.push(Math.trunc(a / b));   // truncate toward zero
    } else {
      stack.push(parseInt(tok, 10));
    }
  }

  return stack[0];
}

Reading it block by block

Line 2 — the stack. A single number[] holds every intermediate operand. Operators consume from it; numbers feed it.
Lines 4–5 — scan tokens. One pass, left to right. The if on line 5 checks whether the token is one of the four operators. All other tokens are treated as integer strings.
Lines 6–12 — operator branch. Pop b first (top of stack = right operand), then a (next = left operand). The non-null assertion ! is safe because a valid RPN always has two values available when an operator appears. For division, Math.trunc truncates toward zero as the problem requires (matches C++ integer division).
Line 14 — number branch. Parse the string token to an integer and push. Handles negative numbers like "-3" correctly because parseInt accepts a leading minus sign.
Line 18 — return. A valid RPN leaves exactly one value on the stack. Return stack[0]. No length check needed given the problem guarantees.
Complexity → O(n) time — one pass over all tokens, each push/pop is O(1). O(n) space in the worst case (all numbers before any operator). In practice, the stack is much smaller.

INTERVIEWFollow-ups they'll ask

  • "What if operands can be floats?" Change the stack type to number[] (already handles floats in JS/TS), drop Math.trunc, and parse with parseFloat.
  • "What if the input can be invalid?" Validate: after the scan the stack should have exactly one element. If at any operator the stack has fewer than two elements, throw or return an error.
  • "Can you support additional operators like ^"? Replace the chain of if/else with a Map<string, (a: number, b: number) => number>; adding an operator is one line.
  • "How does this relate to infix evaluation?" Infix needs a two-stack approach (operators + operands) or a shunting-yard conversion to RPN first. RPN removes the need for precedence and associativity handling entirely.
  • "What is the Shunting-Yard algorithm?" It converts infix to RPN in O(n) using an operator stack and a precedence table. Once in RPN, this evaluator runs directly. A great follow-up for LC 224 / 772.

MNEMONIC The one-liner

"Numbers queue up on the stack; every operator pops b then a, computes a op b, and pushes back."

TRIGGERS When you see ___ → reach for ___

postfix / RPN expression to evaluatestack of operands
"pop two, apply operator, push result"pop b then a → a op b
division must truncate toward zeroMath.trunc(a / b)
nested/matching structure resolved by most-recentstack (LIFO)

SKELETON The reusable shape

skeleton.ts
function evalRPN(tokens: string[]): number {
  const stack: number[] = [];
  for (const tok of tokens) {
    if (isOperator(tok)) {
      const b = stack.pop()!;  // second operand
      const a = stack.pop()!;  // first operand
      stack.push(apply(tok, a, b));
    } else {
      stack.push(parseInt(tok, 10));
    }
  }
  return stack[0];
}

FLASHCARDS Tap to flip

What data structure evaluates RPN in one pass?
A stack of operands. Numbers push; operators pop two, compute, push one result.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
Evaluate ["2", "1", "+", "3", "*"]. What does the stack look like after processing the + operator?
QUESTION 02
When you pop two values to apply an operator, which pop gives you the RIGHT operand (b)?
QUESTION 03
What does ["4", "13", "5", "/", "+"] evaluate to?
QUESTION 04
What is the correct way to handle integer division that truncates toward zero in TypeScript?
QUESTION 05
What is the time complexity of the stack-based RPN evaluator?
QUESTION 06
After a valid RPN expression is fully evaluated, how many values remain on the stack?
QUESTION 07
Evaluate ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]. What is the result?
QUESTION 08
#150 · Evaluate Reverse Polish NotationProcess tokens left to right: push numbers, and on an operator pop two operands — b then a — compute a op b, and push the result back. Division truncates toward zero.Which algorithmic approach does this primarily use?
QUESTION 09
#150 · Evaluate Reverse Polish NotationProcess tokens left to right: push numbers, and on an operator pop two operands — b then a — compute a op b, and push the result back. Division truncates toward zero.Which implementation correctly solves it?