Evaluate a Postfix Expression

In postfix notation (also called Reverse Polish Notation), an operator comes after its two operands: 2 3 + means 2 + 3. No parentheses are needed, because the order of the tokens fully determines the order of evaluation.

Given a postfix expression whose tokens are separated by spaces, evaluate it. The operators are +, -, *, and /, and division truncates toward zero. Return OptionalInt.empty() if the expression is invalid.

LeetCode: 150. Evaluate Reverse Polish Notation

Example 1

Text

Input:  "2 1 + 3 *"
Output: 9
Explanation: (2 + 1) * 3

Example 2

Text

Input:  "4 13 5 / +"
Output: 6
Explanation: 4 + (13 / 5) = 4 + 2

Example 3

Text

Input:  "1 +"
Output: empty   (+ has only one operand)

A helper that applies an operator

OptionalInt is a container that holds either one int or nothing. OptionalInt.of(5) holds a value and OptionalInt.empty() holds nothing, so a method can report "no answer" without returning null.

Java

import java.util.OptionalInt;

public class Main {
    static OptionalInt apply(String op, int a, int b) {
        switch (op) {
            case "+": return OptionalInt.of(a + b);
            case "-": return OptionalInt.of(a - b);
            case "*": return OptionalInt.of(a * b);
            case "/": return b == 0 ? OptionalInt.empty() : OptionalInt.of(a / b); // empty on division by zero
            default: return OptionalInt.empty();                                  // unknown operator
        }
    }

    public static void main(String[] args) {
        System.out.println(apply("-", 7, 2));
        System.out.println(apply("/", 7, 0));
    }
}

Output

OptionalInt[5]
OptionalInt.empty

a is the left operand and b the right one. For - and / the order matters: "7 2 -" is 7 - 2.

Brute force: rewrite the token list

Find the first operator. The two tokens right before it are its operands. Replace those three tokens with the result, and repeat until one number is left.

Text

[2, 1, +, 3, *]  ->  [3, 3, *]  ->  [9]

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.OptionalInt;

public class Main {
    static OptionalInt apply(String op, int a, int b) {
        switch (op) {
            case "+": return OptionalInt.of(a + b);
            case "-": return OptionalInt.of(a - b);
            case "*": return OptionalInt.of(a * b);
            case "/": return b == 0 ? OptionalInt.empty() : OptionalInt.of(a / b);
            default: return OptionalInt.empty();
        }
    }

    static boolean isOperator(String t) {
        return t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/");
    }

    static OptionalInt evalPostfix(String expr) {
        List<String> tokens = new ArrayList<>(Arrays.asList(expr.trim().split("\\s+")));
        while (tokens.size() > 1) {
            int i = 0;
            while (i < tokens.size() && !isOperator(tokens.get(i))) i++;
            if (i < 2 || i == tokens.size()) {
                return OptionalInt.empty(); // operator without two operands, or no operator left
            }
            int a, b;
            try {
                a = Integer.parseInt(tokens.get(i - 2));
                b = Integer.parseInt(tokens.get(i - 1));
            } catch (NumberFormatException e) {
                return OptionalInt.empty();
            }
            OptionalInt value = apply(tokens.get(i), a, b);
            if (value.isEmpty()) return OptionalInt.empty();
            tokens.subList(i - 2, i + 1).clear();                // remove the three tokens
            tokens.add(i - 2, String.valueOf(value.getAsInt())); // insert the result
        }
        try {
            return OptionalInt.of(Integer.parseInt(tokens.get(0)));
        } catch (NumberFormatException e) {
            return OptionalInt.empty();
        }
    }

    public static void main(String[] args) {
        System.out.println(evalPostfix("2 1 + 3 *"));
        System.out.println(evalPostfix("4 13 5 / +"));
        System.out.println(evalPostfix("1 +"));
    }
}

Output

OptionalInt[9]
OptionalInt[6]
OptionalInt.empty

Time: O(n²): each of up to n/2 rewrites searches and shifts the token list. Space: O(n).

Optimal: a stack of operands

Scan the tokens from left to right:

Number: push it.
Operator: pop the right operand, then the left operand, apply the operator, and push the result.

At the end, the stack must hold exactly one value: the answer.

Walkthrough with "2 1 + 3 *":

token	action	stack after (bottom → top)
2	push	[2]
1	push	[2, 1]
+	pop 1 and 2, push 2 + 1	[3]
3	push	[3, 3]
*	pop 3 and 3, push 3 * 3	[9]

ArrayDeque is the standard stack in Java: push and pop work at the front in O(1). The legacy Stack class is synchronized and slower, so it is not used here.

Java

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

public class Main {
    static OptionalInt apply(String op, int a, int b) {
        switch (op) {
            case "+": return OptionalInt.of(a + b);
            case "-": return OptionalInt.of(a - b);
            case "*": return OptionalInt.of(a * b);
            case "/": return b == 0 ? OptionalInt.empty() : OptionalInt.of(a / b);
            default: return OptionalInt.empty();
        }
    }

    static OptionalInt evalPostfix(String expr) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : expr.trim().split("\\s+")) {
            try {
                stack.push(Integer.parseInt(token));
            } catch (NumberFormatException notANumber) {
                if (stack.size() < 2) return OptionalInt.empty(); // operator without two operands
                int b = stack.pop(); // right operand is on top
                int a = stack.pop();
                OptionalInt result = apply(token, a, b);
                if (result.isEmpty()) return OptionalInt.empty();
                stack.push(result.getAsInt());
            }
        }
        return stack.size() == 1 ? OptionalInt.of(stack.pop()) : OptionalInt.empty();
    }

    public static void main(String[] args) {
        System.out.println(evalPostfix("2 1 + 3 *"));
        System.out.println(evalPostfix("4 13 5 / +"));
        System.out.println(evalPostfix("10 6 9 3 + -11 * / * 17 + 5 +"));
        System.out.println(evalPostfix("1 +"));
        System.out.println(evalPostfix("1 2"));
        System.out.println(evalPostfix("4 0 /"));
    }
}

Output

OptionalInt[9]
OptionalInt[6]
OptionalInt[22]
OptionalInt.empty
OptionalInt.empty
OptionalInt.empty

Time: O(n): one pass, O(1) per token. Space: O(n) for the stack.

Each check handles one kind of invalid input:

stack.size() < 2: an operator without enough operands ("1 +").
result.isEmpty(): an unknown operator, or division by zero ("4 0 /").
the final size() == 1 check: leftover operands ("1 2").

Parsing each token as a number first means -11 is treated as a negative number, not as the - operator.

Edge cases

A single number: "5" evaluates to 5.
Negative results and truncation: "7 -2 /" is -3, since Java's / on int truncates toward zero.
Overflow: Java int arithmetic wraps around silently on overflow. For large inputs, use long and Math.addExact / Math.multiplyExact, which throw ArithmeticException instead.