Topics › Stacks and Queues › Prefix, Infix, PostFix Conversion Problems

Infix to Postfix Conversion

Medium TUF ID 586 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

An infix expression writes each binary operator between its operands, the way we normally write arithmetic: a+b*c. A postfix (reverse Polish) expression writes the operator after both operands: abc*+. Postfix needs no parentheses and no precedence rules to be read back, which is why calculators and compilers like it.

Convert a given infix expression to postfix. Operands are single characters (letters or digits). Operators are +, -, *, / and ^, with the usual rules:

Parentheses override precedence. The input has no spaces and is assumed well formed; the code throws IllegalArgumentException on unmatched parentheses or missing operands.

Constraints: 1 ≤ n ≤ 10^5 characters.

Example 1

infix   = a+b*(c^d-e)^(f+g*h)-i
postfix = abcd^e-fgh*+^*+i-

c^d-e becomes cd^e- (the ^ binds first), the second group becomes fgh*+, the two groups are joined by ^, multiplied by b, added to a, and finally i is subtracted.

Example 2

infix   = (A+B)*(C-D)
postfix = AB+CD-*

Both approaches rely on these two small helpers:

static int precedence(char op) {
    return switch (op) {
        case '^' -> 3;
        case '*', '/' -> 2;
        case '+', '-' -> 1;
        default -> -1;
    };
}

static boolean isOperand(char c) {
    return Character.isLetterOrDigit(c);
}

Approach 1: Recursive descent

Intuition. Precedence levels are really a grammar. An expression is a sum of terms; a term is a product of factors; a factor is a base possibly raised to a power; a base is an operand or a parenthesised expression. Writing one method per level, where each method parses its operands first and only then emits its operator, produces postfix order automatically: by the time expr appends a +, the two terms it joins have already been written out.

expr   -> term   { ('+' | '-') term }
term   -> factor { ('*' | '/') factor }
factor -> base   [ '^' factor ]
base   -> operand | '(' expr ')'

Left associativity comes from the loop in expr and term: after a-b is emitted as ab-, the loop sees the next -, parses c, and emits ab-c-. Right associativity of ^ comes from recursion in factor: after base reads a and sees ^, it calls factor again, which consumes all of b^c first, so the output is abc^^.

Algorithm.

1. Keep a cursor pos into the string and an output builder.
2. expr: parse a term; while the next character is + or -, consume it, parse another term, append the operator.
3. term: same with * and / around factor.
4. factor: parse a base; if the next character is ^, consume it, parse a factor recursively, append ^.
5. base: on (, consume it, parse an expr, require ). On an operand, append it. Anything else is an error.
6. After the top-level expr, the cursor must be at the end of the input.

static String recursiveDescent(String infix) {
    Parser p = new Parser(infix);
    p.expr();
    if (p.pos != infix.length()) throw new IllegalArgumentException("unexpected '" + infix.charAt(p.pos) + "' at " + p.pos);
    return p.out.toString();
}

    Parser p = new Parser(infix);
    p.expr();
    if (p.pos != infix.length()) throw new IllegalArgumentException("unexpected '" + infix.charAt(p.pos) + "' at " + p.pos);
    return p.out.toString();
}

Complexity. Time O(n): every character is examined a constant number of times. Space O(d) for the call stack, where d is the nesting depth of the expression (bounded by n), plus O(n) for the output.

This is the method a compiler writer reaches for, and it validates the input as it goes. Its drawback is that the grammar is hard-coded: adding an operator or a precedence level means adding a method.

Approach 2: Optimal, shunting-yard with an operator stack

Intuition. Scan left to right. Operands can be written out as soon as they are seen, because in postfix they keep their relative order. Operators cannot: + in a+b*c must wait until b*c has been emitted. Park waiting operators on a stack. When a new operator arrives, any operator on the stack that binds at least as tightly (and came earlier, so for equal precedence and left associativity it goes first) has both of its operands written already and can be flushed to the output. Then the new operator is pushed. A ( is pushed as a barrier that nothing pops past; a ) flushes down to that barrier and removes it. At the end, flush the stack.

The single comparison that encodes the table above is: pop while prec(top) > prec(c), or prec(top) == prec(c) and c is left-associative (not ^).

Algorithm.

1. For each character c:
   • Operand: append to output.
   • (: push.
   • ): pop and append until the top is (, then discard the (. An empty stack here means an unmatched ).
   • Operator: while the top is an operator with higher precedence, or equal precedence and c is not ^, pop and append. Then push c.
2. Pop and append everything left. A ( left on the stack means an unmatched (.

static String optimal(String infix) {
    if (infix.isEmpty()) throw new IllegalArgumentException("empty expression");
    StringBuilder out = new StringBuilder();
    Deque<Character> ops = new ArrayDeque<>();
    for (int i = 0; i < infix.length(); i++) {
        char c = infix.charAt(i);
        if (isOperand(c)) {
            out.append(c);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.isEmpty() && ops.peek() != '(') out.append(ops.pop());
            if (ops.isEmpty()) throw new IllegalArgumentException("unmatched ')' at " + i);
            ops.pop();                                       // discard the '('
        } else if (precedence(c) > 0) {
            while (!ops.isEmpty() && ops.peek() != '('
                    && (precedence(ops.peek()) > precedence(c)
                        || (precedence(ops.peek()) == precedence(c) && c != '^'))) {
                out.append(ops.pop());                       // it binds at least as tightly and came first
            }
            ops.push(c);
        } else {
            throw new IllegalArgumentException("unexpected '" + c + "' at " + i);
        }
    }
    while (!ops.isEmpty()) {
        if (ops.peek() == '(') throw new IllegalArgumentException("unmatched '('");
        out.append(ops.pop());
    }
    return out.toString();
}

Dry run on example 2, (A+B)*(C-D):

Complexity. Time O(n): each character is appended at most once and each operator is pushed and popped at most once. Space O(n) for the stack and the output.

Both approaches produce identical output on every valid input; the test file checks them against the same expected strings, including the right-associative a^b^c → abc^^ and the left-associative a-b-c → ab-c-.

Edge cases and pitfalls

• Associativity of ^. Treating ^ as left-associative gives ab^c^ for a^b^c, which evaluates (a^b)^c. The c != '^' clause in the pop condition is what prevents popping an earlier ^.
• Equal precedence must pop. a-b+c must become ab-c+, not abc+-. Popping only on strictly greater precedence gets this wrong.
• Parentheses on the stack. A ( must never be popped by an operator, and must not be appended to the output when a ) removes it. The ops.peek() != '(' guard handles the first; the explicit ops.pop() after the loop handles the second.
• Unmatched parentheses. A ) with no ( on the stack, or a ( still on the stack at the end, is an error; both implementations throw, and rejects in the test file checks that they agree.
• Single operand and redundant parentheses. a converts to a, and ((a)) also converts to a; the parentheses leave no trace in postfix.
• Unary minus and multi-character operands are not part of this problem. Handling -a or 12+3 requires tokenising first; the stack logic itself does not change.
• Character unboxing. ops.peek() != '(' compares an unboxed char with a char literal, which is correct. Comparing two Character objects with != would compare references.

Related problems

• Infix to Prefix Conversion runs the same algorithm on the reversed string with the associativity rule flipped.
• Prefix to Infix Conversion and Postfix to Infix Conversion go the other way with a stack of partial strings.
• Prefix to Postfix Conversion and Postfix to Prefix Conversion convert between the two parenthesis-free forms.
• Balanced Paranthesis is the simpler stack problem whose “pop until the opener” step reappears here.