#117

Evaluate Reverse Polish Notation

medium

arraymathstack

You are given an arithmetic expression in Reverse Polish Notation (postfix) as an array of string tokens. Evaluate it and return the resulting integer.

A token is either an integer (possibly negative) or one of the four operators "+", "-", "*", "/". Each operator applies to the two values that immediately precede it.

Notes: - Division between two integers truncates toward zero (so 6 / -4 is -1, not -2). - The expression is always valid, every operator has its two operands, and the result fits in a 32-bit signed integer.

Example

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

Output: 9

(2 + 1) * 3 = 9.

Constraints

1 <= tokens.length <= 10^4
Each token is "+", "-", "*", "/", or an integer in [-200, 200].
The expression is always a valid postfix expression.

Intuition

Postfix notation puts each operator after its two operands, so there are no parentheses to balance. A first instinct is to rewrite it into a normal infix expression and evaluate that — but reconstructing and re-parsing the grouping is fiddly and slow.

function evalRPN(tokens) {
  const t = [...tokens];
  const ops = { '+': (a, b) => a + b, '-': (a, b) => a - b,
                '*': (a, b) => a * b, '/': (a, b) => Math.trunc(a / b) };
  // Find the first operator; its operands are the two tokens just before it.
  while (t.length > 1) {
    const i = t.findIndex((tok) => tok in ops);
    const val = ops[t[i]](Number(t[i - 2]), Number(t[i - 1]));
    t.splice(i - 2, 3, String(val)); // replace the triple with its result
  }
  return Number(t[0]);
}

Brute force — collapse the leftmost operator and its two operands, repeat: O(n²).

Each findIndex + splice is O(n) and we do it O(n) times — O(n²), with array shuffling on top. Can we do better?

The key observation: when you read an operator, its operands are the two values produced most recently — last produced is the first one you need. “Most recent, handled first” is a [stack](/study-guide/algos/topic/stacks). Push every number. On an operator, pop the top two (the second pop is the left operand), apply it, and push the result back. One left-to-right pass; the final lone value is the answer.

The lane below is the token stream being scanned; the caption tracks the operand stack after each token (its top is the rightmost value listed). Walking it through:

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

i↓

131

push 4, push 13

Numbers go straight onto the operand stack. Stack: [4, 13].

131

i↓

push 5

Another number. Stack: [4, 13, 5].

131

i↓

'/' → pop 5 (b), pop 13 (a), push trunc(13/5)=2

Operator: the two most-recent values are its operands, a=13 (left) over b=5. Stack: [4, 2].

131

i↓

'+' → pop 2 (b), pop 4 (a), push 4+2=6

Add the remaining two. Stack: [6].

131

i↓

scan ends → return stack top

One value left on the stack — that's the result: 6.

Operand order matters for - and /: the first pop is the right operand b, the second is the left operand a — compute a - b, not b - a.
Integer division truncates toward zero (Math.trunc), so 6 / -4 is -1, not the -2 that Math.floor would give.

Optimization

Operand stack

Postfix needs no parentheses: when you read an operator, its operands are the two most recently produced values. So push every number onto a stack; on an operator, pop the top two (the second pop is the left operand), apply the operation, and push the result back. After the last token a single value remains — the answer.

Truncation toward zero matters for division: Math.trunc(a / b) drops the fractional part regardless of sign, unlike Math.floor.

O(n) time, O(n) space.

function evalRPN(tokens) {
  const stack = [];
  for (const token of tokens) {
    if (token === "+" || token === "-" || token === "*" || token === "/") {
      // The two operands are the last two values produced; order matters for - and /.
      const b = stack.pop();
      const a = stack.pop();
      if (token === "+") stack.push(a + b);
      else if (token === "-") stack.push(a - b);
      else if (token === "*") stack.push(a * b);
      else stack.push(Math.trunc(a / b)); // truncate toward zero, not floor
    } else {
      stack.push(Number(token));
    }
  }
  return stack[0];
}

Complexity analysis

Time complexity: O(n). Here's why:

Each token is read once.
A number is one push; an operator is two pops, one arithmetic op, and one push — all O(1).

So the work is n × O(1) = O(n), where n is the token count. The brute force's repeated findIndex + splice is the O(n²) this replaces.

Space complexity: O(n). Here's why:

The operand stack holds values not yet consumed by an operator.
An expression that pushes many numbers before the first operator (e.g. a long run of operands) holds all of them at once.

So the stack can hold up to about n / 2 operands — O(n) auxiliary space.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
tokens = ["5"]	5	A single number — no operators, the value itself.
tokens = ["4","5","*"]	20	One operation: 4 * 5.
tokens = ["2","1","+","3","*"]	9	(2 + 1) * 3 — the result feeds the next operator.
tokens = ["9","3","/"]	3	Division truncates toward zero: 9 / 3 = 3 exactly.
tokens = ["10","2","-"]	8	Operand order: a − b = 10 − 2, the second pop is the left operand.
tokens = ["-50","4","+"]	-46	Negative operand: -50 + 4.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor