Evaluate a Postfix Arithmetic Expression
Solve this Problemexpr containing single-digit operands and the operators +, -, *, /, evaluate it and return the result.
Postfix notation is built specifically to make evaluation trivial with a stack: since every operator immediately follows its two already-resolved operands, there's never any need to look ahead or worry about precedence — push operands as they're read, and whenever an operator is seen, pop the two most recent values, apply it, and push the result back. By the time the whole expression has been scanned, exactly one value remains on the stack: the answer.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ expr.length ≤ 9 - ◆
expr contains only single-digit operands (0-9) and the operators '+', '-', '*', '/' - ◆
Division truncates toward zero - ◆
expr is guaranteed to be a valid postfix expression
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursively Split Into Two Sub-Expressions
BruteThe last character of any postfix expression (longer than one character) is always its final operator, and everything before it is exactly two complete postfix sub-expressions concatenated — one for each operand. Find where the split falls by simulating a stack of index ranges (rather than values): each digit contributes its own 1-character range; each operator merges the two most recent ranges into one spanning from the left one's start through itself. After processing, exactly two ranges remain — recursively evaluate each, then apply the final operator. Rebuilding that range stack from scratch happens again inside every recursive call, so the O(n) scan repeats at every level — O(n²) overall.
O(n²)O(n)1class Solution {
2 public int evaluatePostfix(String expr) {
3 return evalHelper(expr);
4 }
5
6 private int apply(char op, int a, int b) {
7 if (op == '+') return a + b;
8 if (op == '-') return a - b;
9 if (op == '*') return a * b;
10 return a / b;
11 }
12
13 private int evalHelper(String s) {
14 if (s.length() == 1) return s.charAt(0) - '0';
15 char lastOp = s.charAt(s.length() - 1);
16 String body = s.substring(0, s.length() - 1);
17 List<int[]> stack = new ArrayList<>();
18 for (int i = 0; i < body.length(); i++) {
19 char c = body.charAt(i);
20 if (Character.isDigit(c)) {
21 stack.add(new int[]{i, i + 1});
22 } else {
23 stack.remove(stack.size() - 1);
24 int[] left = stack.remove(stack.size() - 1);
25 stack.add(new int[]{left[0], i + 1});
26 }
27 }
28 int[] r1 = stack.get(0);
29 int[] r2 = stack.get(1);
30 int a = evalHelper(body.substring(r1[0], r1[1]));
31 int b = evalHelper(body.substring(r2[0], r2[1]));
32 return apply(lastOp, a, b);
33 }
34}Optimal — Single Pass With a Value Stack
OptimalWalk the expression once. A digit pushes its numeric value. An operator pops the two most recent values (the second-to-last pop is the left operand, the last pop is the right operand — order matters for '-' and '/'), computes the result, and pushes that back. Because postfix guarantees every operator's operands are already fully resolved by the time it's reached, no lookahead or backtracking is ever needed — one pass, one push or pop per token.
O(n)O(n)1class Solution {
2 public int evaluatePostfix(String expr) {
3 Deque<Integer> stack = new ArrayDeque<>();
4 for (char c : expr.toCharArray()) {
5 if (Character.isDigit(c)) {
6 stack.push(c - '0');
7 } else {
8 int b = stack.pop();
9 int a = stack.pop();
10 if (c == '+') stack.push(a + b);
11 else if (c == '-') stack.push(a - b);
12 else if (c == '*') stack.push(a * b);
13 else stack.push(a / b);
14 }
15 }
16 return stack.pop();
17 }
18}