Evaluate Reverse Polish Notation

1. Define the problem

Evaluate Reverse Polish Notation

You are given a list of tokens that describe an arithmetic expression written in reverse Polish notation . Work out its value. In this notation the operator comes after the two numbers it works on. The everyday expression (2 + 1) * 3 is written as the tokens 2, 1, +, 3, *. There are no brackets at all, because the order is already fixed by the layout. Use a stack of numbers . Push every number you read. When you read an operator, pop the top two numbers, apply the operator to them, and push the result back. At the end exactly one number is left, and that is the answer. Division cuts off the decimal part and rounds toward zero , so 7 / 2 is 3 and -7 / 2 is -3.

Constraints

1 ≤ tokens.length ≤ 10⁴
Each token is an operator '+', '-', '*' or '/', or an integer written as text
The expression is always valid
Division never divides by zero
Every intermediate value fits in a normal integer

Example

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

Output9

Explanation This is (2 + 1) * 3. Push 2 and 1, the + turns them into 3, push 3, then the * gives 9.

2. Know the words first

In plain terms

Reverse Polish notation: A way of writing maths where the operator comes after its two numbers. "3 4 +" means 3 + 4. No brackets are needed.
Operator: One of the four symbols +, -, * and / that combine two numbers into one.
Operand: A number that an operator works on. Every operator here takes exactly two of them.
Round toward zero: Throw away the part after the decimal point instead of rounding up or down. 3.7 becomes 3 and -3.7 becomes -3.

3. Visualize the solution

The row is the stack of numbers, bottom-left to top-right

0—

1—

2—

3—

Statusinit

Start with an empty stack before reading any token.

What happens in this step

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

No numbers are waiting yet, so every slot shows a dash.

Step 1 of 7

Steps to visualize

Each filled cell is a number waiting to be used. A dash means an empty slot.
A number token is pushed straight on top of the stack.
An operator token pops the top two numbers — the second one popped is the left-hand side.
The result of the operator is pushed back on, so the stack shrinks by one.
When the tokens run out, the single remaining number is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the stack of numbers, bottom-left to top-right

0—

1—

2—

3—

Statusinit

Start with an empty stack before reading any token.

What happens in this step

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

No numbers are waiting yet, so every slot shows a dash.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

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

  for (const token of tokens) {
    if (token !== '+' && token !== '-' && token !== '*' && token !== '/') {
      stack.push(Number(token));
      continue;
    }

    const right = stack.pop();
    const left = stack.pop();

    if (token === '+') {
      stack.push(left + right);
    } else if (token === '-') {
      stack.push(left - right);
    } else if (token === '*') {
      stack.push(left * right);
    } else {
      stack.push(Math.trunc(left / right));
    }
  }

  return stack.pop();
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`tokens = ["2", "1", "+", "3", "*"]`	`9`	example from the description
`tokens = ["42"]`	`42`	smallest input, one number and no operator
`tokens = ["4", "13", "5", "/", "+"]`	`6`	division that cuts off the decimal part
`tokens = ["5", "1", "2", "+", "4", "*", "+", "3", "-"]`	`14`	a longer nested expression where operand order matters
`tokens = ["-3", "4", "*"]`	`-12`	a negative number written as text
`tokens = ["7", "-2", "/"]`	`-3`	negative division rounding toward zero rather than down

Evaluate Reverse Polish Notation