Convert an Infix Expression to Postfix
Solve this Problemexpr — operators appearing between their operands, the everyday way arithmetic is written, using single-character operands and standard operator precedence — convert it to postfix notationPostfix NotationAlso called Reverse Polish Notation: every operator follows its operands instead of sitting between them (e.g. "a+b" becomes "ab+"). It needs no parentheses and no precedence rules to evaluate — a single left-to-right stack pass suffices., where every operator comes immediately after its two operands instead of between them.
Postfix's appeal is that it can be evaluated with a single stack pass and no precedence rules at all — the conversion is where the precedence logic has to live instead. The classic technique (Shunting-Yard) handles that in one left-to-right pass: operands go straight to the output, and operators get held on a stack until something of equal-or-lower precedence needs to interrupt them, at which point they're released into the output in the right order. The same idea this category has used throughout — a stack remembers exactly what's still "pending" — applies here to remember exactly which operators are still waiting for their right-hand operand to finish being decided.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ expr.length ≤ 15 - ◆
expr contains only single-letter or single-digit operands, the operators '+', '-', '*', '/', '^', and matched parentheses - ◆
'^' (exponentiation) is right-associative; all other operators are left-associative - ◆
Standard precedence applies: '^' highest, then '*' and '/', then '+' and '-'
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursively Split at the Lowest-Precedence Operator
BruteMirror how the expression would actually be evaluated: find the operator with the lowest precedence at the top level (outside any parentheses) — that's the very last operation that would run, so it becomes the root. Split the expression there into a left and right half, recursively convert each to postfix, and concatenate left + right + operator. (Ties between equal-precedence operators split at the last one, except '^', which splits at the first, to respect associativity.) Finding that lowest-precedence operator means scanning the whole substring at every level of recursion — O(n) work repeated across up to n levels, so O(n²) overall.
O(n²)O(n)1class Solution {
2 public String infixToPostfix(String expr) {
3 return helper(expr);
4 }
5
6 private int precedence(char op) {
7 if (op == '+' || op == '-') return 1;
8 if (op == '*' || op == '/') return 2;
9 if (op == '^') return 3;
10 return 0;
11 }
12
13 private int matchParen(String s, int openIdx) {
14 int depth = 0;
15 for (int i = openIdx; i < s.length(); i++) {
16 if (s.charAt(i) == '(') depth++;
17 else if (s.charAt(i) == ')') { depth--; if (depth == 0) return i; }
18 }
19 return -1;
20 }
21
22 private String helper(String s) {
23 while (s.charAt(0) == '(' && matchParen(s, 0) == s.length() - 1) {
24 s = s.substring(1, s.length() - 1);
25 }
26 if (s.length() == 1) return s;
27 int minPrec = Integer.MAX_VALUE;
28 List<Integer> splitPositions = new ArrayList<>();
29 int depth = 0;
30 for (int i = 0; i < s.length(); i++) {
31 char c = s.charAt(i);
32 if (c == '(') depth++;
33 else if (c == ')') depth--;
34 else if (depth == 0 && "+-*/^".indexOf(c) >= 0) {
35 int p = precedence(c);
36 if (p < minPrec) { minPrec = p; splitPositions.clear(); splitPositions.add(i); }
37 else if (p == minPrec) { splitPositions.add(i); }
38 }
39 }
40 int splitPos;
41 if (s.charAt(splitPositions.get(0)) == '^') {
42 splitPos = splitPositions.get(0);
43 } else {
44 splitPos = splitPositions.get(splitPositions.size() - 1);
45 }
46 String left = helper(s.substring(0, splitPos));
47 String right = helper(s.substring(splitPos + 1));
48 return left + right + s.charAt(splitPos);
49 }
50}Optimal — Shunting-Yard, Single Pass With an Operator Stack
OptimalWalk the expression once, left to right. An operand goes straight to the output. '(' always gets pushed. ')' pops operators off the stack into the output until the matching '(' is found (then discards it). An operator c first pops off — into the output — every operator currently on top of the stack that has strictly higher precedence, or equal precedence with left-associativity, since those already-pending operations must resolve before c can; then c itself gets pushed. After the whole expression is scanned, drain whatever's left on the stack into the output. Every character is pushed and popped at most once — O(n) total, with no re-scanning.
O(n)O(n)1class Solution {
2 private int precedence(char op) {
3 if (op == '+' || op == '-') return 1;
4 if (op == '*' || op == '/') return 2;
5 if (op == '^') return 3;
6 return 0;
7 }
8
9 private boolean rightAssoc(char op) {
10 return op == '^';
11 }
12
13 public String infixToPostfix(String expr) {
14 Deque<Character> stack = new ArrayDeque<>();
15 StringBuilder output = new StringBuilder();
16 for (char c : expr.toCharArray()) {
17 if (Character.isLetterOrDigit(c)) {
18 output.append(c);
19 } else if (c == '(') {
20 stack.push(c);
21 } else if (c == ')') {
22 while (stack.peek() != '(') output.append(stack.pop());
23 stack.pop();
24 } else {
25 while (!stack.isEmpty() && stack.peek() != '(' &&
26 (precedence(stack.peek()) > precedence(c) ||
27 (precedence(stack.peek()) == precedence(c) && !rightAssoc(c)))) {
28 output.append(stack.pop());
29 }
30 stack.push(c);
31 }
32 }
33 while (!stack.isEmpty()) output.append(stack.pop());
34 return output.toString();
35 }
36}