DSA-043 · Completed-subexpression value stack with checked long arithmetic

Evaluate Reverse Polish Notation

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 10021 deterministic checks. Learner drafts are not executed.

Understand the problem

Evaluate a binary reverse-Polish expression with signed long operands and checked intermediate arithmetic.

tokens is a non-null String[] with at most 100,000 tokens and at most 1,000,000 total characters. Integer tokens have optional ASCII + or - followed by one or more ASCII digits; leading zeros are allowed. Exactly +, -, *, / are binary operator tokens. Null, empty, malformed, or out-of-long-range integer tokens cause IllegalArgumentException (including its NumberFormatException subclass).
Every operator needs two completed values and the final stack must contain exactly one. Missing operands, an empty token list, or extra final values cause IllegalArgumentException. Preserve the token array. A single signed integer is a complete expression.
Return a long. Addition, subtraction, and multiplication throw ArithmeticException on overflow. Division truncates toward zero and throws ArithmeticException for division by zero or Long.MIN_VALUE / -1. Every intermediate must fit, even if a later operation could bring the final result back into range.
When an input has several independent errors, baseline and optimized methods need not report the same first error because their validation/evaluation order differs. Valid expressions and single-error examples have the declared behavior.

Examples

Input: ["2","1","+","3","*"]
Output: 9
First complete 2+1, then multiply that value by three.
Input: ["7","-3","/"]
Output: -2
Java signed integer division truncates toward zero, not toward negative infinity.

Before you start

Stack top versus bottom and last-in-first-out order
Loop invariants, checked arithmetic, and amortized analysis

Recognize the structure

Postfix order places both child subexpressions before their parent operator. A stack holds completed child values, with the right operand on top and the left operand immediately below it.

Try before revealing

Hint 1

Which completed subexpression is at the top when an operator arrives?

Hint 2

Name the first popped value right and the next left.

Hint 3

Reduce with checked arithmetic and require one final value.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Repeatedly reduce the first operator in a list

Validate number tokens, find the first remaining operator, replace its preceding two values and itself with one result, and repeat. For 2 1 + 3 *, replace 2 1 + by 3 to get 3 3 *, then replace that triple by 9. List rescans and shifting can cost O(T²) for T tokens, but expose the expression-reduction semantics directly.

Improve the baseline

Push complete leaf values

A numeric token already represents a complete subexpression, so push its parsed long value.

Respect operand order

At an operator, pop right first and left second. Compute left op right using checked arithmetic, then push the completed parent value.

Validate one completed expression

An underflow means missing child expressions. More than one final value means disconnected expressions remain; exactly one value is the result.

Why it is correct

Value-stack invariant

After a processed token prefix, the stack contains the evaluated values of complete subexpressions whose parent operator has not yet combined them, in encounter order.

Operator reduction

Postfix syntax guarantees the two latest completed subexpressions are the operator’s left and right children, with right on top. Replacing them by checked left op right preserves the invariant and the expression’s value.

Completion and failure semantics

A well-formed expression reduces to one value. Underflow or extra values violates binary postfix structure. Checked operations enforce the numeric contract at each reduction rather than permitting wraparound; every successful scan processes each token once.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static boolean operator(String token) {
        return token != null && (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/"));
    }
    private static long number(String token) {
        if (token == null || !token.matches("[+-]?[0-9]+")) throw new IllegalArgumentException("invalid integer token");
        return Long.parseLong(token);
    }
    private static long apply(String op, long left, long right) {
        return switch (op) {
            case "+" -> Math.addExact(left, right);
            case "-" -> Math.subtractExact(left, right);
            case "*" -> Math.multiplyExact(left, right);
            case "/" -> {
                if (right == 0 || left == Long.MIN_VALUE && right == -1) throw new ArithmeticException("invalid exact long division");
                yield left / right;
            }
            default -> throw new IllegalArgumentException("unknown operator");
        };
    }
    public static long evalRPN(String[] tokens) {
        ArrayDeque<Long> values = new ArrayDeque<>();
        for (String token : tokens) {
            if (!operator(token)) values.push(number(token));
            else {
                if (values.size() < 2) throw new IllegalArgumentException("two operands required");
                long right = values.pop(), left = values.pop();
                values.push(apply(token, left, right));
            }
        }
        if (values.size() != 1) throw new IllegalArgumentException("one final value required");
        return values.pop();
    }
    public static long baseline(String[] tokens) {
        List<String> work = new ArrayList<>(Arrays.asList(tokens));
        for (String token : work) if (!operator(token)) number(token);
        while (true) {
            int at = 0;
            while (at < work.size() && !operator(work.get(at))) at++;
            if (at == work.size()) {
                if (work.size() != 1) throw new IllegalArgumentException("one final value required");
                return number(work.getFirst());
            }
            if (at < 2) throw new IllegalArgumentException("two operands required");
            long result = apply(work.get(at), number(work.get(at - 2)), number(work.get(at - 1)));
            work.set(at - 2, Long.toString(result));
            work.remove(at); work.remove(at - 1);
        }
    }
}

Read the meaningful blocks

Pop right before left

Subtraction and division are not commutative. Naming both operands avoids accidentally evaluating right-left.

Check all overflow cases

Math.addExact/subtractExact/multiplyExact cover the arithmetic operations. Signed division needs an explicit MIN_VALUE/-1 check because Java long division otherwise wraps that one overflow.

Parse an explicit token grammar

The regex accepts ASCII signed decimal digits only, and parseLong enforces range. A standalone + or - is an operator rather than a numeric sign without digits.

Complexity

O(T+C) time for T tokens and C input characters, including parsing and constant-width arithmetic. O(T) value-stack entries, excluding the caller’s token strings.

The list-reduction baseline costs O(T²+C) time under the fixed long-width numeric contract and O(T+C) live reference/string storage. Large expressions run only through the optimized method; the baseline is intended for small differential tests.

Exact-state walkthroughs

Reveal normal and boundary traces

Reduce completed child expressions

Input: ["2","1","+","3","*"] · Result: 9

Step 1 of 7: Begin without completed subexpressions.

Values are displayed bottom to top; the top holds the latest completed child expression.

Postfix tokens — current token highlighted

0: "2"
1: "1"
2: "+"
3: "3"
4: "*"

Stack — bottom to top

Empty at this step.

State after this step
Variable	Value
tokens	`["2","1","+","3","*"]`
stackValues	`[]`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static boolean operator(String token) {
 4         return token != null && (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/"));
 5     }
 6     private static long number(String token) {
 7         if (token == null || !token.matches("[+-]?[0-9]+")) throw new IllegalArgumentException("invalid integer token");
 8         return Long.parseLong(token);
 9     }
10     private static long apply(String op, long left, long right) {
11         return switch (op) {
12             case "+" -> Math.addExact(left, right);
13             case "-" -> Math.subtractExact(left, right);
14             case "*" -> Math.multiplyExact(left, right);
15             case "/" -> {
16                 if (right == 0 || left == Long.MIN_VALUE && right == -1) throw new ArithmeticException("invalid exact long division");
17                 yield left / right;
18             }
19             default -> throw new IllegalArgumentException("unknown operator");
20         };
21     }
22     public static long evalRPN(String[] tokens) {
23         ArrayDeque<Long> values = new ArrayDeque<>();
24         for (String token : tokens) {
25             if (!operator(token)) values.push(number(token));
26             else {
27                 if (values.size() < 2) throw new IllegalArgumentException("two operands required");
28                 long right = values.pop(), left = values.pop();
29                 values.push(apply(token, left, right));
30             }
31         }
32         if (values.size() != 1) throw new IllegalArgumentException("one final value required");
33         return values.pop();
34     }
35     public static long baseline(String[] tokens) {
36         List<String> work = new ArrayList<>(Arrays.asList(tokens));
37         for (String token : work) if (!operator(token)) number(token);
38         while (true) {
39             int at = 0;
40             while (at < work.size() && !operator(work.get(at))) at++;
41             if (at == work.size()) {
42                 if (work.size() != 1) throw new IllegalArgumentException("one final value required");
43                 return number(work.getFirst());
44             }
45             if (at < 2) throw new IllegalArgumentException("two operands required");
46             long result = apply(work.get(at), number(work.get(at - 2)), number(work.get(at - 1)));
47             work.set(at - 2, Long.toString(result));
48             work.remove(at); work.remove(at - 1);
49         }
50     }
51 }
52

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin without completed subexpressions.
Values are displayed bottom to top; the top holds the latest completed child expression.
tokens
["2","1","+","3","*"]
stackValues
[]
Push a complete integer leaf.
This leaf is ready for a later parent operator.
tokens
["2","1","+","3","*"]
index
0
token
"2"
stackValues
[2]
Push a complete integer leaf.
This leaf is ready for a later parent operator.
tokens
["2","1","+","3","*"]
index
1
token
"1"
stackValues
[2,1]
Reduce left + right in operand order.
The top was the right operand and the next value was left. The new value represents their completed parent expression.
tokens
["2","1","+","3","*"]
index
2
token
"+"
left
2
right
1
value
3
stackValues
[3]
Push a complete integer leaf.
This leaf is ready for a later parent operator.
tokens
["2","1","+","3","*"]
index
3
token
"3"
stackValues
[3,3]
Reduce left * right in operand order.
The top was the right operand and the next value was left. The new value represents their completed parent expression.
tokens
["2","1","+","3","*"]
index
4
token
"*"
left
3
right
3
value
9
stackValues
[9]
Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
result
9

Signed division truncates toward zero

Input: ["7","-3","/"] · Result: -2

Step 1 of 5: Begin without completed subexpressions.

Values are displayed bottom to top; the top holds the latest completed child expression.

Postfix tokens — current token highlighted

0: "7"
1: "-3"
2: "/"

Stack — bottom to top

Empty at this step.

State after this step
Variable	Value
tokens	`["7","-3","/"]`
stackValues	`[]`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static boolean operator(String token) {
 4         return token != null && (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/"));
 5     }
 6     private static long number(String token) {
 7         if (token == null || !token.matches("[+-]?[0-9]+")) throw new IllegalArgumentException("invalid integer token");
 8         return Long.parseLong(token);
 9     }
10     private static long apply(String op, long left, long right) {
11         return switch (op) {
12             case "+" -> Math.addExact(left, right);
13             case "-" -> Math.subtractExact(left, right);
14             case "*" -> Math.multiplyExact(left, right);
15             case "/" -> {
16                 if (right == 0 || left == Long.MIN_VALUE && right == -1) throw new ArithmeticException("invalid exact long division");
17                 yield left / right;
18             }
19             default -> throw new IllegalArgumentException("unknown operator");
20         };
21     }
22     public static long evalRPN(String[] tokens) {
23         ArrayDeque<Long> values = new ArrayDeque<>();
24         for (String token : tokens) {
25             if (!operator(token)) values.push(number(token));
26             else {
27                 if (values.size() < 2) throw new IllegalArgumentException("two operands required");
28                 long right = values.pop(), left = values.pop();
29                 values.push(apply(token, left, right));
30             }
31         }
32         if (values.size() != 1) throw new IllegalArgumentException("one final value required");
33         return values.pop();
34     }
35     public static long baseline(String[] tokens) {
36         List<String> work = new ArrayList<>(Arrays.asList(tokens));
37         for (String token : work) if (!operator(token)) number(token);
38         while (true) {
39             int at = 0;
40             while (at < work.size() && !operator(work.get(at))) at++;
41             if (at == work.size()) {
42                 if (work.size() != 1) throw new IllegalArgumentException("one final value required");
43                 return number(work.getFirst());
44             }
45             if (at < 2) throw new IllegalArgumentException("two operands required");
46             long result = apply(work.get(at), number(work.get(at - 2)), number(work.get(at - 1)));
47             work.set(at - 2, Long.toString(result));
48             work.remove(at); work.remove(at - 1);
49         }
50     }
51 }
52

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Begin without completed subexpressions.
Values are displayed bottom to top; the top holds the latest completed child expression.
tokens
["7","-3","/"]
stackValues
[]
Push a complete integer leaf.
This leaf is ready for a later parent operator.
tokens
["7","-3","/"]
index
0
token
"7"
stackValues
[7]
Push a complete integer leaf.
This leaf is ready for a later parent operator.
tokens
["7","-3","/"]
index
1
token
"-3"
stackValues
[7,-3]
Reduce left / right in operand order.
The top was the right operand and the next value was left. The new value represents their completed parent expression.
tokens
["7","-3","/"]
index
2
token
"/"
left
7
right
-3
value
-2
stackValues
[-2]
Return the contract result.
The completed result follows the declared ordering, empty-state, and numeric semantics.
result
-2

Test the contract

Input: ["4","13","5","/","+"]
Output: 6
13/5 truncates to two, then add four.
Input: ["1","2"]
Output: IllegalArgumentException
Extra final values.
Input: ["1","0","/"]
Output: ArithmeticException
Division by zero.
Input: ["9223372036854775807","1","+"]
Output: ArithmeticException
Intermediate addition overflow.

Common mistakes and counterexamples

Reverse operand order

Counterexample: 4 2 - should be two, not negative two.

Pop right, then left, and compute left op right.

Use floating-point division then cast

Counterexample: Precision can be lost for full-range long values.

Use integer division directly with the explicit overflow and zero checks.

Return the last value without checking stack size

Counterexample: 1 2 contains two separate values and is not one expression.

Require exactly one final value.

Follow-ups

Convert to infix.

Store expression nodes or parenthesized strings instead of only values. Preserve operator precedence and associativity; naive string concatenation can create quadratic copying.

Add unary operators.

Declare each operator’s arity before popping. Reusing the binary underflow rule for unary negation is incorrect, and negating Long.MIN_VALUE still needs overflow handling.

Use arbitrary precision.

Replace long values with BigInteger and remove the long-range restriction, while retaining division-by-zero and truncation semantics. Arithmetic complexity then depends on operand bit length rather than a fixed-width constant.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 132/20,000 characters

Self-review

I preserve left/right operand order.I distinguish grammar, structure, and arithmetic errors.I check every intermediate, not only the final result.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Stacks: pending work, saved state, and monotonic spans

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.