Evaluate Reverse Polish Notation

How it works

A stack fits Reverse Polish Notation perfectly because the most recent numbers are always the ones used next.
As we scan the tokens:

• When we see a number, we push it onto the stack.
• When we see an operator, we pop the top two numbers, apply the operation, and push the result back.

This way, the stack always holds the intermediate results, and the final remaining value is the answer.
It is clean, efficient, and directly follows how RPN is meant to be evaluated.

Steps

1. Create an empty stack.
2. For each token:
   • If it is a number, convert it to an integer and push it onto the stack.
   • If it is an operator:
     • Pop the top two numbers.
     • Apply the operator in the correct order.
     • Push the result back onto the stack.
3. After processing all tokens, the stack contains exactly one value — return it.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Wrong Operand Order for Subtraction and Division

For subtraction and division, the order matters: the second-to-last operand is the left operand, and the last operand is the right operand. When you pop from a stack, the first pop gives you the right operand (b), and the second pop gives you the left operand (a). Computing b - a or b / a instead of a - b or a / b will produce incorrect results.

Incorrect Integer Division Truncation

Division in RPN truncates toward zero, not toward negative infinity. In languages like Python 2 or when using floor division, -7 / 2 gives -4, but the correct RPN result is -3. You must use truncation toward zero, such as int(a / b) in Python 3 or Math.trunc() in JavaScript.

Treating Negative Numbers as Operators

Tokens like "-3" are valid negative numbers, not the subtraction operator followed by "3". When checking if a token is an operator, you cannot simply check if the first character is -. Instead, check if the token equals exactly "+", "-", "*", or "/", or verify that the token has length 1 when it starts with an operator character.

from typing import List

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for c in tokens:
            if c == "+":
                stack.append(stack.pop() + stack.pop())
            elif c == "-":
                a, b = stack.pop(), stack.pop()
                stack.append(b - a)
            elif c == "*":
                stack.append(stack.pop() * stack.pop())
            elif c == "/":
                a, b = stack.pop(), stack.pop()
                stack.append(int(float(b) / a))
            else:
                stack.append(int(c))
        return stack[0]

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stack;
        for (const string& c : tokens) {
            if (c == "+") {
                int a = stack.top(); stack.pop();
                int b = stack.top(); stack.pop();
                stack.push(b + a);
            } else if (c == "-") {
                int a = stack.top(); stack.pop();
                int b = stack.top(); stack.pop();
                stack.push(b - a);
            } else if (c == "*") {
                int a = stack.top(); stack.pop();
                int b = stack.top(); stack.pop();
                stack.push(b * a);
            } else if (c == "/") {
                int a = stack.top(); stack.pop();
                int b = stack.top(); stack.pop();
                stack.push(b / a);
            } else {
                stack.push(stoi(c));
            }
        }
        return stack.top();
    }
};