Evaluate Reverse Polish Notation with a Stack

You're given a string expr holding an arithmetic expression in reverse Polish notation, with the tokens separated by single spaces. Each token is an integer or one of + - * /, and an operator applies to the two values before it. Return the value of the expression.

Division between two integers truncates towards zero, so -7 2 / is -3. The expression is always valid, it never divides by zero, and every intermediate value fits in a 32-bit signed integer.

Examples

Input	Output	Why
`expr = "2 1 + 3 *"`	`9`	(2 + 1) × 3.
`expr = "4 13 5 / +"`	`6`	13 / 5 truncates to 2, and 4 + 2 = 6.
`expr = "-7 2 /"`	`-3`	Truncated towards zero, not rounded down to −4.

Constraints

1 ≤ number of tokens ≤ 10⁴
Each integer is between −200 and 200
Every intermediate value fits in 32 bits

Hints

Hint 1

Whenever you read an operator, think about which two values it applies to. I'd say they're always the two most recent values that you haven't used up yet.

Hint 2

That suggests keeping the values on a stack, where each number gets pushed and each operator pops two values and pushes its result back on.

Hint 3

Remember that the first value you pop is the right-hand operand, so for 13 5 / you'll pop 5 and then 13 and you want 13 / 5 (which is 2 after truncating).

Where people lose marks

Popping the operands in the wrong order is probably the most common mistake I see, because "3 4 -" should give −1 and swapping them gives you 1.
Python's // and Haskell's div both round downwards, so -7 // 2 gives −4 when the answer you want is −3. You'd use int(a / b) in Python and quot in Haskell instead.
If you check for an operator with something like token[0] == '-' you'll get caught out by negative numbers such as "-3", which also start with a minus sign, so I'd always compare the whole token.

Dry run on `"4 13 5 / + 3 -"`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 8

Step 1 / 8

tokens
40i13152/3+435-6
stack
40
4 is a number, so it goes on the stack until an operator needs it.
Step 2 / 8

tokens
40131i52/3+435-6
stack
40131
13 is a number, so it goes on the stack until an operator needs it.
Step 3 / 8

tokens
4013152i/3+435-6
stack
4013152
5 is a number, so it goes on the stack until an operator needs it.
Step 4 / 8

tokens
4013152/3i+435-6
stack
4021
13 / 52
'/' pops 5 and then 13, so it works out 13 / 5 = 2 and pushes that back.
Step 5 / 8

tokens
4013152/3+4i35-6
stack
60
4 + 26
'+' pops 2 and then 4, so it works out 4 + 2 = 6 and pushes that back.
Step 6 / 8

tokens
4013152/3+435i-6
stack
6031
3 is a number, so it goes on the stack until an operator needs it.
Step 7 / 8

tokens
4013152/3+435-6i
stack
30
6 - 33
'-' pops 3 and then 6, so it works out 6 - 3 = 3 and pushes that back.
Step 8 / 8

stack
30
answer3
Every token is used and one value is left, 3, which is the answer.

How to think about it

Reverse Polish notation puts each operator after its operands, which means that by the time you reach an operator both of its operands have already been calculated. As far as I can tell that's the whole reason it's convenient for computers, since the operands are always the two most recent values you haven't used yet and the result becomes another value that some later operator can use. That behaviour is exactly what a stack gives you. You push every number you read, and whenever an operator arrives you pop two values, apply the operator and push the result back on. When you've finished reading the tokens there should be exactly one value remaining and that's your answer.

The order matters for - and /. The value on top is the right-hand operand, so pop b first and then a and compute a − b or a / b.

Complexity. Time O(n) · Space O(n)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def eval_rpn(expr):
    stack = []
    for t in expr.split():
        if t in ('+', '-', '*', '/'):
            b = stack.pop()                  # the right-hand operand is on top
            a = stack.pop()
            if t == '+':
                stack.append(a + b)
            elif t == '-':
                stack.append(a - b)
            elif t == '*':
                stack.append(a * b)
            else:
                stack.append(int(a / b))     # truncate towards zero, not //
        else:
            stack.append(int(t))
    return stack[0]

#include <sstream>
#include <string>
#include <vector>

long long solve(const std::string& expr) {
    std::vector<long long> stack;
    std::istringstream in(expr);
    std::string t;
    while (in >> t) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            long long b = stack.back(); stack.pop_back();   // the right-hand operand is on top
            long long a = stack.back(); stack.pop_back();
            if (t == "+") stack.push_back(a + b);
            else if (t == "-") stack.push_back(a - b);
            else if (t == "*") stack.push_back(a * b);
            else stack.push_back(a / b);                    // C++ division truncates towards zero
        } else {
            stack.push_back(std::stoll(t));
        }
    }
    return stack[0];
}

class Solution {
    public long evalRPN(String expr) {
        String[] toks = expr.split(" ");
        long[] stack = new long[toks.length];
        int top = 0;
        for (String t : toks) {
            if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
                long b = stack[--top], a = stack[--top];    // the right-hand operand is on top
                long r;
                if (t.equals("+")) r = a + b;
                else if (t.equals("-")) r = a - b;
                else if (t.equals("*")) r = a * b;
                else r = a / b;                             // Java division truncates towards zero
                stack[top++] = r;
            } else {
                stack[top++] = Long.parseLong(t);
            }
        }
        return stack[0];
    }
}

function evalRPN(expr) {
  const stack = [];
  for (const t of expr.split(' ')) {
    if (t === '+' || t === '-' || t === '*' || t === '/') {
      const b = stack.pop(), a = stack.pop();   // the right-hand operand is on top
      if (t === '+') stack.push(a + b);
      else if (t === '-') stack.push(a - b);
      else if (t === '*') stack.push(a * b);
      else stack.push(Math.trunc(a / b));       // truncate towards zero
    } else {
      stack.push(Number(t));
    }
  }
  return stack[0];
}

fn solve(expr: &str) -> i64 {
    let mut stack: Vec<i64> = Vec::new();
    for t in expr.split_whitespace() {
        match t {
            "+" | "-" | "*" | "/" => {
                let b = stack.pop().unwrap();       // the right-hand operand is on top
                let a = stack.pop().unwrap();
                stack.push(match t {
                    "+" => a + b,
                    "-" => a - b,
                    "*" => a * b,
                    _ => a / b,                     // Rust division truncates towards zero
                });
            }
            _ => stack.push(t.parse().unwrap()),
        }
    }
    stack[0]
}

-- The stack is a list with its top at the head; quot truncates towards zero (div would round down).
solve :: String -> Integer
solve = head . foldl step [] . words
  where
    step (b : a : rest) "+" = a + b : rest
    step (b : a : rest) "-" = a - b : rest
    step (b : a : rest) "*" = a * b : rest
    step (b : a : rest) "/" = a `quot` b : rest
    step stack t            = read t : stack

Variants to try

An interviewer might ask you to convert an ordinary expression with brackets and precedence into reverse Polish notation first, and the shunting-yard algorithm does that with a second stack holding the operators.
You can also evaluate the expression without an explicit stack by recursing from the last token backwards, which is what the tests on this page use as their independent oracle.
If you add a unary minus or exponentiation you'll need to decide how many values each new operator pops, and exponentiation is usually right-associative, which changes the conversion step as well.

Next problems

Hard25 min

Evaluate reverse Polish notation

Examples

Constraints

Hints

Where people lose marks

Dry run on `"4 13 5 / + 3 -"`

How to think about it

The solution, in six languages

Variants to try

Next problems

A calculator for plus, minus and brackets

Balanced brackets

Days until a warmer day

Keep going

A calculator for plus, minus and brackets

Balanced brackets

Days until a warmer day

The pattern behind it

Evaluate reverse Polish notation

Examples

Constraints

Hints

Where people lose marks

Dry run on "4 13 5 / + 3 -"

How to think about it

The solution, in six languages

Variants to try

Next problems

A calculator for plus, minus and brackets

Balanced brackets

Days until a warmer day

Keep going

A calculator for plus, minus and brackets

Balanced brackets

Days until a warmer day

The pattern behind it

Dry run on `"4 13 5 / + 3 -"`