Evaluate Reverse Polish Notation

Most of us write math like 3 + 4. The operator sits between the two numbers. But computers often prefer a different order. They like 3 4 +, where the operator comes last. This question asks you to read that strange order and find the answer. It looks scary at first. But a stack makes it almost easy.

🎯 The Problem

You get a list of tokens and must read it as math written in Reverse Polish Notation, where the operator comes after its two numbers.

• A token is one item in the list. It is either a number or one of +, -, *, /.
• Reverse Polish Notation, also called postfix, puts the operator after its two numbers.
• Read the whole list and return the single final number.
• Division cuts toward zero, so 6 / 4 gives 1, not 1.5.
• You can assume the list is always valid.

A quick read of ["2", "1", "+", "3", "*"]. First 2 1 + means 2 + 1, which is 3. Then 3 3 * means 3 * 3, which is 9. So the answer is 9.

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

Explanation: ((2 + 1) * 3) = 9

Here is the same expression drawn as a tree, so you can see how the operators wrap around the numbers.

🐢 Approach 1: Rewrite Into Normal Math (Brute Force)

Turn the postfix list back into normal math, one operation at a time.

The idea:

• Scan the list for an operator.
• Find the two numbers right before it.
• Replace all three with their single result.
• Repeat until one number is left.

Why it is weak:

• Every replace shifts the whole list.
• So you keep scanning from the start again and again.
• It needs heavy bookkeeping to track positions.
• Time climbs to O(n²) on a long list.

Here is the expression-tree style code:

def eval_rpn(tokens):
    stack = []
    for token in tokens:
        if token in "+-*/":
            b = stack.pop()
            a = stack.pop()
            stack.append(f"int({a}{token}{b})" if token == "/" else f"({a}{token}{b})")
        else:
            stack.append(token)
    return eval(stack[0])

⚡ Approach 2: Evaluate With a Stack (Best)

The idea in one line: in postfix the two numbers an operator needs are always the freshest items, so a stack serves them up for free.

The idea:

• A stack is a pile where you only add to the top and remove from the top.
• The last thing you put in is the first thing you take out.

How it works:

• Walk the tokens once.
• See a number: push it onto the stack.
• See an operator: pop the top two numbers, apply it, push the result back.
• The first pop is the right side. The second pop is the left side. This matters for minus and divide.
• At the end, one number is left on the stack. That is the answer.

Why it is fast:

• Each token is read once and does constant work.
• So the whole pass is O(n).

Here is a dry run of ["2", "1", "+", "3", "*"]. Watch how the stack contents change at each step.

Steps to Solve

1. Create an empty stack.
2. Walk through the tokens one by one.
3. If the token is a number, push it onto the stack.
4. If the token is an operator, pop the top number as the right side, then pop the next as the left side.
5. Apply the operator to left and right, then push the result back.
6. After the last token, the only number left on the stack is the answer.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int isOperator(const char *s) {
    // an operator is a single character +, -, *, or /
    if (strlen(s) != 1) return 0;
    char c = s[0];
    return c == '+' || c == '-' || c == '*' || c == '/';
}

int evalRPN(char *tokens[], int n) {
    int stack[1000];
    int top = 0;  // points to the next free slot
    for (int i = 0; i < n; i++) {
        if (isOperator(tokens[i])) {
            int right = stack[--top];  // first pop is the right side
            int left = stack[--top];   // second pop is the left side
            int res = 0;
            char c = tokens[i][0];
            if (c == '+') res = left + right;
            else if (c == '-') res = left - right;
            else if (c == '*') res = left * right;
            else res = left / right;   // C division cuts toward zero
            stack[top++] = res;        // push the result back
        } else {
            stack[top++] = atoi(tokens[i]);  // push the number
        }
    }
    return stack[0];
}

int main(void) {
    char *tokens[] = {"2", "1", "+", "3", "*"};
    int n = 5;
    printf("%d\n", evalRPN(tokens, n));
    return 0;
}

9

#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;

bool isOperator(const string& s) {
    return s == "+" || s == "-" || s == "*" || s == "/";
}

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (const string& t : tokens) {
        if (isOperator(t)) {
            int right = st.top(); st.pop();  // first pop is the right side
            int left = st.top(); st.pop();   // second pop is the left side
            if (t == "+") st.push(left + right);
            else if (t == "-") st.push(left - right);
            else if (t == "*") st.push(left * right);
            else st.push(left / right);      // cuts toward zero
        } else {
            st.push(stoi(t));                // push the number
        }
    }
    return st.top();
}

int main() {
    vector<string> tokens = {"2", "1", "+", "3", "*"};
    cout << evalRPN(tokens) << endl;
    return 0;
}

9

import java.util.Deque;
import java.util.ArrayDeque;

public class EvalRPN {
    static boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }

    public static int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String t : tokens) {
            if (isOperator(t)) {
                int right = stack.pop();  // first pop is the right side
                int left = stack.pop();   // second pop is the left side
                switch (t) {
                    case "+": stack.push(left + right); break;
                    case "-": stack.push(left - right); break;
                    case "*": stack.push(left * right); break;
                    default:  stack.push(left / right); break; // cuts toward zero
                }
            } else {
                stack.push(Integer.parseInt(t)); // push the number
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String[] tokens = {"2", "1", "+", "3", "*"};
        System.out.println(evalRPN(tokens));
    }
}

9

def eval_rpn(tokens):
    stack = []
    operators = {"+", "-", "*", "/"}
    for token in tokens:
        if token in operators:
            right = stack.pop()          # first pop is the right side
            left = stack.pop()           # second pop is the left side
            if token == "+":
                stack.append(left + right)
            elif token == "-":
                stack.append(left - right)
            elif token == "*":
                stack.append(left * right)
            else:
                stack.append(int(left / right))  # cut toward zero
        else:
            stack.append(int(token))     # push the number
    return stack[0]


tokens = ["2", "1", "+", "3", "*"]
print(eval_rpn(tokens))

9

function evalRPN(tokens) {
  const stack = [];
  const operators = new Set(["+", "-", "*", "/"]);
  for (const token of tokens) {
    if (operators.has(token)) {
      const right = stack.pop(); // first pop is the right side
      const left = stack.pop();  // second pop is the left side
      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)); // cut toward zero
    } else {
      stack.push(Number(token)); // push the number
    }
  }
  return stack[0];
}

const tokens = ["2", "1", "+", "3", "*"];
console.log(evalRPN(tokens));

9

Let us walk through the Python version line by line and see why each part is there.

The line stack = [] creates the empty pile. A Python list already behaves like a stack. We use append to add to the top and pop to take from the top. The set operators holds the four symbols. We use a set because checking token in operators in a set is almost instant.

The loop for token in tokens reads each item once. The check if token in operators asks: is this an operator or a number? If it is an operator, we need the two numbers above it. The line right = stack.pop() takes the top number. That top number was pushed most recently. In postfix that is the right side of the operation. The next line left = stack.pop() takes the new top, which is the left side. Getting this order right is the whole trick. For + and * the order does not matter. But for - and / it does. So we always treat the first pop as the right side.

The if/elif/else block does the math and pushes the result back with append. For division we write int(left / right). Plain / in Python gives a float and floors toward negative infinity for negatives. We want it to cut toward zero. So we divide as a float, then int(...) chops the decimal toward zero. If the token was not an operator, the else branch runs. There we do stack.append(int(token)) to turn the text into a number and push it. At the end one value remains, and return stack[0] hands it back.

⏱️ Time and Space Complexity

The stack approach reads each token once and does constant work per token. So it runs in O(n) time, where n is the number of tokens. It stores numbers on the stack, so in the worst case the stack holds about half the tokens. That makes the space O(n). The rewrite approach scans the list many times, so it climbs to O(n²).

🧩 Key Takeaways

• ✅ A stack is the natural fit for postfix expressions, because the two numbers an operator needs are always on top.
• ✅ Push numbers as you see them. On an operator, pop two and push the result.
• ✅ The first number you pop is the right side. The second is the left side. This matters for minus and divide.
• ✅ Division cuts toward zero, so handle it carefully in each language.
• ✅ One pass gives O(n) time, far better than rewriting the list again and again.

🚀 What’s Next?

• Generate Parentheses
• Daily Temperatures