Evaluate Reverse Polish Notation

MEDIUM✓ CHIP-TIMEDLC #150 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Evaluate an expression written in postfix (Reverse Polish) form: an operator token acts on the two numbers immediately before it, and the whole array reduces to a single value.

An array of string tokens arrives representing an arithmetic expression written in postfix — Reverse Polish — notation, where numbers appear before the operator that combines them.

A number token is a plain operand. An operator token — +, -, *, or / — always acts on the two operands that came immediately before it in the scan, replacing all three with a single resulting value.

Division truncates toward zero, and the tokens are always arranged so the whole array reduces to exactly one final value once every operator has been applied.

token list holds a handful up to a couple thousand entries
operands can be negative, zero, or positive integers
only +, -, *, / appear as operators
division truncates toward zero and never divides by zero

EX 01

tokens = ["6", "2", "/"]

→ 3

plain division

EX 02

tokens = ["10", "3", "-", "2", "*"]

→ 14

subtraction feeds a multiplication

EX 03

tokens = ["-5", "3", "+"]

→ -2

negative operand

The hintstake only what you need

HINT 1 THE NUDGE

Every operator here needs exactly the two most recent numbers it hasn't consumed yet — the ones nearest to it in the scan, not the oldest ones.

HINT 2 THE STRUCTURE

A stack holds “numbers not yet used.” Push numbers as you read them; on an operator, pop the top two, combine them, and push the result back as a new “number.”

HINT 3 ONE STEP FROM THE ANSWER

Pop b then a, in that order — operand order matters for subtraction and division — compute a OP b, and push it back. After the last token, the stack holds exactly one value: the answer.

Coach's boardthe pattern, step by step

THE OPERAND STACKPATTERN · OPERAND STACKtokens = ["10", "3", "-", "2", "*"]

OPERAND STACK

— empty —

STEP 1

Numbers push onto a stack; an operator pops the two most recent and pushes the result back.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/evaluate-reverse-polish-notation.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        ops = {"+", "-", "*", "/"}
        for t in tokens:
            if t in ops:
                b = stack.pop()
                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 toward zero
            else:
                stack.append(int(t))
        return stack[0]

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 19 LN

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        toks = tokens[:]
        ops = {"+", "-", "*", "/"}
        while len(toks) > 1:
            for i, t in enumerate(toks):
                if t in ops:
                    a, b = int(toks[i - 2]), int(toks[i - 1])
                    if t == "+":
                        res = a + b
                    elif t == "-":
                        res = a - b
                    elif t == "*":
                        res = a * b
                    else:
                        res = int(a / b)  # truncate toward zero
                    toks[i - 2:i + 1] = [str(res)]
                    break
        return int(toks[0])

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 19 LN

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String t : tokens) {
            switch (t) {
                case "+":
                case "-":
                case "*":
                case "/": {
                    int b = stack.pop();
                    int a = stack.pop();
                    switch (t) {
                        case "+":
                            stack.push(a + b);
                            break;
                        case "-":
                            stack.push(a - b);
                            break;
                        case "*":
                            stack.push(a * b);
                            break;
                        default:
                            stack.push(a / b);
                            break;
                    }
                    break;
                }
                default:
                    stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 34 LN

class Solution {
    public int evalRPN(String[] tokens) {
        List<String> toks = new ArrayList<>(Arrays.asList(tokens));
        Set<String> ops = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
        while (toks.size() > 1) {
            for (int i = 0; i < toks.size(); i++) {
                if (ops.contains(toks.get(i))) {
                    int a = Integer.parseInt(toks.get(i - 2));
                    int b = Integer.parseInt(toks.get(i - 1));
                    int res;
                    switch (toks.get(i)) {
                        case "+":
                            res = a + b;
                            break;
                        case "-":
                            res = a - b;
                            break;
                        case "*":
                            res = a * b;
                            break;
                        default:
                            res = a / b;
                            break;
                    }
                    toks.subList(i - 2, i + 1).clear();
                    toks.add(i - 2, String.valueOf(res));
                    break;
                }
            }
        }
        return Integer.parseInt(toks.get(0));
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 33 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED