Evaluate Reverse Polish Notation

STACK · MEDIUM

Builds on Day 17: Stacks

The optimal solution below is a textbook stack use case; read that lesson first if push/pop LIFO mechanics are still new.

The problem

You’re given an array of string tokens representing an arithmetic expression written in Reverse Polish (postfix) Notation — every operator comes after its two operands instead of between them, so no parentheses are ever needed. Valid tokens are integers (as strings, possibly negative) or one of the four operators +, -, *, /. Division always truncates toward zero, not toward negative infinity. Evaluate the expression and return the resulting integer. For example ["2","1","+","3","*"] means (2 + 1) * 3 = 9, and ["4","13","5","/","+"] means 4 + (13 / 5) = 4 + 2 = 6 (13/5 truncates to 2, not 2.6).

Solution 1: Brute force — repeated rescan and splice, no explicit stack

You don’t strictly need a stack to evaluate RPN — you can treat the token array itself as the workspace. Repeatedly scan from the very start of the array looking for the first operator token. Once found, it’s guaranteed (by the definition of valid RPN) that the two tokens immediately before it are its operands. Apply the operator to them, then splice that 3-token window down to a single result token, and start scanning again from index 0. Keep going until only one token is left — that’s the answer. It’s honest and correct, but every single operator application pays for a full re-scan of whatever’s left, plus the cost of splice shifting every token after it.

Interactive visualization

tokens = [10, 6, 9, 3, +, -11, *, /, *, 17, +, 5, +] — brute force approach

Press Play or Step to begin.

Step 0 / 20

▶ Play⏭ Step↺ Reset

This animation traces tokens=[“10”,“6”,“9”,“3”,“+”,“-11”,“”,“/”,“”,“17”,“+”,“5”,“+”] (expected: 22), verified above before any HTML was written.

The code

function evalRPNBruteForce(tokens) {
  const OPERATORS = new Set(['+', '-', '*', '/']);
  const working = tokens.slice();

  while (working.length > 1) {
    let opIdx = -1;
    for (let i = 0; i < working.length; i++) {
      if (OPERATORS.has(working[i])) { opIdx = i; break; }
    }

    const a = Number(working[opIdx - 2]);
    const b = Number(working[opIdx - 1]);
    const op = working[opIdx];
    let result;
    if (op === '+') result = a + b;
    else if (op === '-') result = a - b;
    else if (op === '*') result = a * b;
    else result = Math.trunc(a / b);

    working.splice(opIdx - 2, 3, String(result));
  }
  return Number(working[0]);
}

Line by line:

• OPERATORS.has(working[i]) tests for an exact match against +/-/*// — a negative-number token like "-11" never matches, since it’s a two-character string, not the single character "-".
• The inner for loop re-scans working from index 0 every single time this outer while body runs — that repeated full rescan, not a different algorithmic idea, is what makes this O(n²) instead of O(n).
• Because the tokens form valid RPN, working[opIdx - 2] and working[opIdx - 1] are guaranteed to be exactly this operator’s two operands — no searching or validation needed to find them.
• Math.trunc(a / b), not Math.floor(a / b), is required for the division case — truncation drops the fractional part toward zero, while floor rounds toward negative infinity and gives the wrong answer whenever the true quotient is negative.
• working.splice(opIdx - 2, 3, String(result)) removes the 3-token window and replaces it with one token in a single call — but every token after that window still has to shift down by two positions, an O(n) cost on top of the rescan.

Complexity

Time	Space	Approach
O(n²)	O(n)	Repeated full rescan + splice per operator, no explicit stack

Solution 2: Optimal — explicit stack, single pass

Walk the tokens exactly once, left to right, using an explicit stack. Every number token gets parsed and pushed. Every operator token pops the top two values — b first, then a, since the stack is LIFO and b was pushed more recently — applies the operator as a op b (never b op a; getting the operand order backward silently breaks non-commutative operators like - and /), and pushes the result back on. After the last token, exactly one value remains on the stack: the answer. No rescanning, no shifting — every push and pop is O(1).

Interactive visualization

tokens = [10, 6, 9, 3, +, -11, *, /, *, 17, +, 5, +] — optimal stack-based approach

TOKENS (fixed list)

STACK (grows/shrinks)

Press Play or Step to begin.

Step 0 / 21

▶ Play⏭ Step↺ Reset

Same tokens=[“10”,“6”,“9”,“3”,“+”,“-11”,“”,“/”,“”,“17”,“+”,“5”,“+”] as Solution 1, so you can compare step counts directly — the stack view shows values left-to-right, bottom of stack first.

The code

function evalRPNOptimal(tokens) {
  const OPERATORS = new Set(['+', '-', '*', '/']);
  const stack = [];

  for (const token of tokens) {
    if (OPERATORS.has(token)) {
      const b = stack.pop();
      const a = stack.pop();
      let result;
      if (token === '+') result = a + b;
      else if (token === '-') result = a - b;
      else if (token === '*') result = a * b;
      else result = Math.trunc(a / b);
      stack.push(result);
    } else {
      stack.push(Number(token));
    }
  }
  return stack[0];
}

Line by line:

• OPERATORS.has(token) is the same exact-match test as the brute-force version — "-11" falls through to the else branch and gets parsed as a number, never mistaken for the "-" operator.
• const b = stack.pop(); const a = stack.pop(); — order matters. b is popped first because it was pushed second (LIFO), and the operator is then applied as a op b, matching the original left-to-right operand order in the expression.
• Same Math.trunc(a / b) truncating-toward-zero division as Solution 1 — this isn’t a place the two solutions differ, only how they find their operands differs.
• stack.push(Number(token)) parses every non-operator token as a number exactly once — no re-parsing, no re-scanning of earlier tokens.
• After the loop, stack[0] is the sole remaining value for any valid RPN input — returning it doesn’t need to check the stack’s length, because valid input guarantees exactly one value is left.

Complexity

Time	Space	Approach
O(n)	O(n)	Single linear pass with an explicit stack, O(1) push/pop

Complexity comparison

Solution	Time	Space
Brute force (rescan + splice)	O(n²)	O(n)
Optimal (explicit stack)	O(n)	O(n)

This is a real, clean asymptotic improvement, not just a different constant factor. Both solutions apply operators in the exact same order and get the exact same operands for each one — the difference is purely how those operands are located. The brute-force version pays an O(n) rescan-plus-shift for every single operator application, while the stack version finds both operands in O(1) via pop(), because the stack’s own LIFO order already keeps “the two most recent unconsumed values” sitting right on top, with zero searching required.

Interview corner

Why must the optimal solution pop b before a, and then apply the operator as a op b — not b op a?

• The stack is LIFO: whichever operand was pushed later in the expression comes off the stack first. In postfix, the operand written second in the source is always b, so it’s on top and pops first.
• Getting the assignment backward (const a = stack.pop(); const b = stack.pop();) would silently swap which value is a and which is b.
• For + and * that swap wouldn’t even be visible — the wrong code would happen to produce right answers on those tokens. For - and /, which aren’t commutative, it produces a confidently wrong answer with no error thrown (e.g. a - b vs b - a differ by sign whenever they’re unequal).

Both solutions apply operators in the exact same order to the exact same operands. What actually makes the brute-force version O(n²) instead of O(n)?

• The brute-force version re-scans the entire remaining token array from index 0 to find the next operator, every single time — not a smarter search, a fresh linear pass.
• splice() also shifts every token after the removed window down by two positions, another O(n) cost layered on top of the scan.
• The stack version never re-scans anything: each token is visited exactly once, and finding “the two most recent operands” is an O(1) pop() because the stack’s own structure already keeps them on top — that’s the entire source of the asymptotic gap, not a different evaluation strategy.

Why is it always safe to assume, without checking, that the two tokens immediately before an operator (brute force) or the top two stack values (optimal) are exactly that operator’s operands?

• This relies on the input being valid RPN, which both solutions are entitled to assume (per the problem’s constraints) — it’s not something either one re-verifies.
• In valid postfix notation, at any point during a left-to-right scan, everything seen so far reduces to a stack of complete, already-evaluated sub-expression results — there’s no way for an operator to appear before both of its operands have been fully resolved.
• That invariant is exactly why “top two of the stack” (or “two tokens immediately before” in the array version) always correctly identifies the operands — no searching, matching, or bracket-tracking is ever needed, unlike evaluating infix expressions.

Trick question — what does this log?

console.log(parseInt('3*'));
console.log(Number('3*'));

• Answer: 3, then NaN — two very different results for the same malformed-looking string.
• parseInt reads digits from the left and silently stops at the first character that isn’t part of a valid number, discarding the rest — it would happily treat a corrupted token like "3*" as the number 3, no error, no warning.
• Number(...) requires the entire string to be a valid numeric literal — anything left over makes the whole conversion fail to NaN.

⚠️ Trap: This is exactly why both solutions above use Number(token) to parse operands, never parseInt(token). Since every token is checked against OPERATORS first, only genuine number tokens ever reach the parse step — but Number() is still the safer default, because a stray malformed token becomes a loud NaN that propagates and breaks the final result, instead of parseInt silently truncating it into a plausible-looking but wrong number.

Quiz

Question 1

In the optimal solution, why is b popped before a, with the operator then applied as a op b?

A) The stack is LIFO — the operand pushed later (b) comes off first, and applying a op b preserves the original operand order B) Variables are conventionally popped in alphabetical order in every stack-based algorithm C) It doesn’t actually matter which order they’re popped in, since all four operators give the same result either way

Correct answer: A — The stack is LIFO — the operand pushed later (b) comes off the stack first, and applying a op b reproduces the original left-to-right operand order.

Question 2

Both solutions evaluate operators in the same order on the same operands. What actually makes the brute-force version O(n²) instead of O(n)?

A) It re-scans the entire remaining array from index 0 for every operator, and splice() shifts everything after the removed window — both repeated O(n) costs B) It uses a fundamentally different, mathematically incorrect evaluation rule C) It relies on unbounded recursion, which the stack version avoids entirely

Correct answer: A — It re-scans the entire remaining array from index 0 to find each operator, and splice() shifts everything after it — both repeated O(n) costs paid again and again. The stack version never rescans; each token is visited exactly once.

Question 3

Why does the division case use Math.trunc(a / b) instead of Math.floor(a / b)?

A) Math.trunc rounds toward zero as required; Math.floor rounds toward negative infinity and gives a different, wrong answer for negative quotients B) Math.trunc is measurably faster than Math.floor, which matters at scale C) They always return the same value for any input, so it’s purely a style choice

Correct answer: A — Math.trunc drops the fractional part and rounds toward zero, which is exactly what the problem requires. Math.floor rounds toward negative infinity instead — for a negative true quotient like -7/2 = -3.5, floor gives -4 (wrong) while trunc correctly gives -3.

Question 4

Why can both solutions safely assume the operands for any operator are exactly the two values sitting right before it, with no verification needed?

A) Valid RPN guarantees every operator’s operands are already fully resolved and sitting immediately before it — an invariant of the notation itself, not something either solution checks B) It happens to work for the specific test cases shown, but isn’t actually guaranteed in general C) Because the input array secretly still contains parentheses that get stripped out first

Correct answer: A — Valid RPN guarantees that at every point in a left-to-right scan, everything seen so far reduces to a stack of complete sub-expression results. An operator can never appear before both of its operands are fully resolved, so ‘top two of the stack’ (or ‘two tokens immediately before’ in the array version) is always correct — no searching or bracket-matching needed.

Question 5

What does parseInt('3*') return, and why do both solutions use Number(token) instead?

A) It returns 3 — parseInt silently stops at the first non-digit character. Number(‘3*’) returns NaN instead, which is why the code uses Number(token) to parse operands B) It throws a TypeError immediately, which parseInt does for any string containing a non-digit character C) parseInt(‘3*’) and Number(‘3*’) both return NaN, so either function would work equally well here

Correct answer: A — parseInt(‘3*’) reads digits left to right and silently stops at the first non-digit character, returning 3 with no error. Number(‘3*’) requires the entire string to be a valid numeric literal, so any leftover garbage makes the whole conversion fail to NaN instead — which is why both solutions deliberately use Number(token), not parseInt(token).