Code Logo

Evaluate Reverse Polish Notation

Published at23 Jul 2026
Created by
Medium 5 views
Like0

Reverse Polish Notation (RPN) is a mathematical notation where operators follow their operands, eliminating the need for parentheses to define evaluation order. The expression 3 4 + means 3 + 4, and 3 4 + 2 * means (3 + 4) * 2.

RPN is naturally evaluated with a stack. Scan the tokens from left to right. When you see a number, push it onto the stack. When you see an operator (+, -, *, /), pop the top two values from the stack, apply the operator, and push the result back. At the end, the stack contains exactly one value: the answer.

The stack works perfectly here because it follows the LIFO (last-in-first-out) principle. The most recently pushed number is the first one popped when an operator needs its second operand. This naturally handles nested expressions without requiring explicit precedence rules.

Division between two integers should truncate toward zero (floor for positive, ceiling for negative). The input expression is always valid RPN, meaning the stack will never have too few operands and will end with exactly one value.

For example, ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] evaluates to 22. Working through the full expression step by step is the best way to understand how the stack accumulates intermediate results.

Example Input & Output

Example 1
Input
["2", "1", "+", "3", "*"]
Output
9
Explanation

(2 + 1) * 3 = 9

Example 2
Input
["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output
22
Explanation

A longer valid RPN expression evaluating to 22

Example 3
Input
["4", "13", "5", "/", "+"]
Output
6
Explanation

4 + (13 / 5) = 4 + 2 = 6

Algorithm Flow

Recommendation Algorithm Flow for Evaluate Reverse Polish Notation
Recommendation Algorithm Flow for Evaluate Reverse Polish Notation

Solution Approach

The stack is ideal for RPN evaluation because it naturally matches the order of operations. Numbers are pushed and operators consume the top two values, producing a result that becomes available for the next operator.

function solution(tokens) {
  const stack = []
  for (const t of tokens) {
    if ('+-*/'.includes(t)) {
      const b = stack.pop()
      const a = stack.pop()
      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))
    } else {
      stack.push(Number(t))
    }
  }
  return stack[0]
}

Time complexity is O(n). Space complexity is O(n) for the stack.

Best Answers

java
import java.util.*;
class Solution {
    public int solution(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String t : tokens) {
            if ("+-*/".contains(t)) {
                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;
                    case "/": stack.push(a / b); break;
                }
            } else {
                stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }
}