☕ DSA Java Articles

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

Infix to Prefix Conversion

Medium TUF ID 587 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a valid infix expression, the everyday notation where each binary operator sits between its operands, and must return the equivalent prefix expression (Polish notation), where each operator comes before its two operands. Operands are single letters or digits. Operators are + - * / ^, and round brackets may appear.

Infix needs rules to be unambiguous, and the conversion must respect them:

Constraints: the input is valid, with length up to about 10^4.

Example 1

infix  = "x+y*z/w+u"
prefix = "++x/*yzwu"       // ((x + ((y*z)/w)) + u)

Example 2

infix  = "(A-B/C)*(A/K-L)"
prefix = "*-A/BC-/AKL"     // brackets force both subtractions before the multiplication

Example 3

infix  = "a^b^c"
prefix = "^a^bc"           // right-associative: a ^ (b ^ c)

The one rule both approaches share. Scanning left to right, operators wait on a stack until it is safe to apply them. When a new operator arrives, the operator on top of the stack must be applied first if it has higher precedence, or equal precedence and the incoming operator is left-associative. That is why a-b-c applies the first - before pushing the second, while a^b^c lets the first ^ wait so the second one binds first.

Approach 1: Two stacks, building prefix strings directly

Intuition. This is the classic two-stack evaluator for infix expressions, the same one a calculator uses, with one change: instead of numbers, the operand stack holds prefix strings. An operand is a prefix expression of length one. “Applying” an operator means popping it, popping its right and left operand strings, and pushing op + left + right. When the input ends, apply everything that is left, and the single string on the operand stack is the answer.

Brackets are handled the usual way: ( is pushed as a barrier; ) applies operators until the matching ( and then discards it. The barrier also stops the precedence loop, so nothing inside a bracket is combined with anything outside it too early.

Algorithm.

  1. Keep operands (strings) and ops (characters).
  2. For each character c:
    • Operand: push it onto operands.
    • (: push onto ops.
    • ): reduce until the top of ops is (, then pop the (.
    • Operator: while ops is not empty, its top is not (, and the top must be applied before c, reduce. Then push c.
  3. Reduce until ops is empty, and return the top of operands.
static String twoStacks(String infix) {
    Deque<String> operands = new ArrayDeque<>();
    Deque<Character> ops = new ArrayDeque<>();
    for (int i = 0; i < infix.length(); i++) {
        char c = infix.charAt(i);
        if (isOperand(c)) {
            operands.push(String.valueOf(c));
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (ops.peek() != '(') reduce(operands, ops);
            ops.pop();                           // discard the matching '('
        } else {
            while (!ops.isEmpty() && ops.peek() != '(' && appliesBefore(ops.peek(), c)) reduce(operands, ops);
            ops.push(c);
        }
    }
    while (!ops.isEmpty()) reduce(operands, ops);
    return operands.isEmpty() ? "" : operands.pop();
}

/** True when the operator on the stack must be applied before the incoming one is pushed. */
static boolean appliesBefore(char top, char incoming) {
    if (precedence(top) != precedence(incoming)) return precedence(top) > precedence(incoming);
    return incoming != '^';                      // equal precedence: left-associative operators go first, '^' waits
}

/** Pops one operator and its two operands and pushes the combined prefix string. */
static void reduce(Deque<String> operands, Deque<Character> ops) {
    char op = ops.pop();
    String right = operands.pop();
    String left = operands.pop();
    operands.push(op + left + right);
}

Dry run on "x+y*z/w+u":

char action operands (bottom to top) ops
x push x  
+ push x +
y push x, y +
* + is lower, just push x, y + *
z push x, y, z + *
/ * equal and / is left-assoc: reduce *yz, push / x, *yz + /
w push x, *yz, w + /
+ reduce /*yzw, then reduce +x/*yzw, push + +x/*yzw +
u push +x/*yzw, u +
end reduce ++x/*yzwu  

Complexity. Time O(n^2) in the worst case: each character is pushed and popped once, but each reduction copies both operand strings, and a long chain like a+a+a+... re-copies the growing prefix string every time. Space O(n).

Approach 2: Optimal, reverse, convert to postfix, reverse again

Intuition. There is a neat relationship between prefix and postfix. Take the expression tree and mirror it, swapping the left and right operand of every operator. Then the postfix of the mirrored tree is exactly the reverse of the prefix of the original tree. (By induction: the postfix of the mirror of op(L, R) is post(mirror R) + post(mirror L) + op, which is rev(pre R) + rev(pre L) + op = rev(op + pre L + pre R).)

Reversing the infix string produces the mirrored expression, as long as we also swap ( with ) so brackets still open before they close. Then we can reuse the standard linear infix-to-postfix algorithm on the reversed string and reverse its output.

There is one trap. Mirroring flips associativity. The original a-b-c is (a-b)-c; its mirror must be c-(b-a), which groups to the right. Likewise the mirror of a^(b^c) is (c^b)^a, which groups to the left. So, on the reversed string, ties are broken the opposite way from the normal postfix algorithm: an equal-precedence operator on the stack is popped only when the incoming operator is ^.

Algorithm.

  1. Reverse the infix string and swap every ( with ).
  2. Run infix to postfix on it: operands go straight to the output; ( is pushed; ) pops to the output until (; an operator pops while the top has higher precedence, or equal precedence and the incoming operator is ^, then is pushed.
  3. Pop the remaining operators to the output.
  4. Reverse the output.
static String optimal(String infix) {
    StringBuilder rev = new StringBuilder(infix).reverse();
    for (int i = 0; i < rev.length(); i++) {
        char c = rev.charAt(i);
        if (c == '(') rev.setCharAt(i, ')');
        else if (c == ')') rev.setCharAt(i, '(');
    }
    StringBuilder out = new StringBuilder(infix.length());
    Deque<Character> ops = new ArrayDeque<>();
    for (int i = 0; i < rev.length(); i++) {
        char c = rev.charAt(i);
        if (isOperand(c)) {
            out.append(c);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (ops.peek() != '(') out.append(ops.pop());
            ops.pop();
        } else {
            while (!ops.isEmpty() && ops.peek() != '(' && popsInReversed(ops.peek(), c)) out.append(ops.pop());
            ops.push(c);
        }
    }
    while (!ops.isEmpty()) out.append(ops.pop());
    return out.reverse().toString();
}

/** Pop rule for the reversed string: associativity is mirrored, so only '^' pops an equal-precedence operator. */
static boolean popsInReversed(char top, char incoming) {
    if (precedence(top) != precedence(incoming)) return precedence(top) > precedence(incoming);
    return incoming == '^';
}

Dry run on "x+y*z/w+u", reversed to "u+w/z*y+x":

char action output ops
u output u  
+ push u +
w output uw +
/ + is lower, push uw + /
z output uwz + /
* / equal, * is not ^: no pop, push uwz + / *
y output uwzy + / *
+ pop *, pop /; + equal, no pop; push uwzy*/ + +
x output uwzy*/x + +
end pop all uwzy*/x++  

Reversing uwzy*/x++ gives ++x/*yzwu, matching Approach 1.

Complexity. Time O(n): two reversals, and each character is pushed and popped at most once; no string is ever re-copied. Space O(n) for the reversed copy, the operator stack and the output.

Edge cases and pitfalls