☕ DSA Java Articles

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

Prefix to Infix Conversion

Medium TUF ID 848 A2Z

Java source ↗ Edit this article ↗

Problem

A prefix (Polish) expression writes each binary operator before its two operands: +ab means a+b, and *+ab-cd means (a+b)*(c-d). Like postfix, it needs no parentheses. Convert a prefix expression to a fully parenthesised infix expression, in which every operator application is wrapped in its own pair of parentheses so that the original structure is unambiguous.

Operands are single characters (letters or digits); operators are +, -, *, /, ^. The input has no spaces and is assumed well formed; the code throws IllegalArgumentException when an operator lacks operands or operands are left over.

Constraints: 1 ≤ n ≤ 10^5 characters.

Example 1

prefix = *-A/BC-/AKL
infix  = ((A-(B/C))*((A/K)-L))

The leading * multiplies two sub-expressions: -A/BC, which is A-(B/C), and -/AKL, which is (A/K)-L.

Example 2

prefix = +12
infix  = (1+2)

Both approaches use one helper:

static boolean isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

Approach 1: Recursion from the left

Intuition. A prefix expression is either a single operand, or an operator followed by two complete prefix expressions, the left operand first and the right operand second. That is a recursive definition, so a recursive parser follows it exactly: read one character; if it is an operand, that is the whole expression; if it is an operator, parse the left expression, then the right expression, and wrap them as (left op right). The recursion does not need to know where the left operand ends, because the recursive call consumes exactly the characters that belong to it and leaves the cursor at the start of the right operand.

Algorithm.

  1. Keep a shared cursor pos, starting at 0.
  2. parse: if the cursor is past the end, the expression is incomplete, throw. Read c at the cursor and advance.
  3. If c is an operand, return it as a one-character string.
  4. Otherwise c is an operator: left = parse(), right = parse(), return "(" + left + c + right + ")".
  5. After the top-level parse, the cursor must be at the end of the input; otherwise there are leftover characters.
static String recursive(String prefix) {
    int[] pos = {0};                                        // cursor shared by all recursive calls
    String result = parse(prefix, pos);
    if (pos[0] != prefix.length()) throw new IllegalArgumentException("leftover tokens from index " + pos[0]);
    return result;
}

    String result = parse(prefix, pos);
    if (pos[0] != prefix.length()) throw new IllegalArgumentException("leftover tokens from index " + pos[0]);
    return result;
}

Complexity. Time O(n) recursive calls, one per character. The string concatenations copy each sub-result once per enclosing level, so the total character copying is O(n × depth): O(n log n) for balanced trees and O(n^2) for a degenerate chain such as ----abcde. Space O(depth) for the call stack, which is O(n) in the worst case, plus the output.

The cursor is passed as a one-element int[] so that the recursive calls can advance it; Java passes arguments by value, so a plain int parameter would not be updated for the caller.

Approach 2: Optimal, a stack scanned from the right

Intuition. Reading prefix left to right, an operator arrives before its operands, so we cannot combine anything yet. Reading right to left, by the time we meet an operator both of its operands have already been seen, and they are the two most recently completed sub-expressions. “Most recently completed” is exactly what a stack gives us. So scan from the end: push each operand; on an operator pop two sub-expressions, combine them, and push the result. One sub-expression remains at the end: the answer.

The order of the two pops matters. Scanning right to left, the operand that is closer to the operator in the original string, that is the left operand, is pushed later, so it is popped first.

Algorithm.

  1. For i from n - 1 down to 0, let c be the character at i.
  2. If c is an operand, push the one-character string.
  3. If c is an operator: if the stack has fewer than two entries, throw. left = pop(), right = pop(), push "(" + left + c + right + ")".
  4. At the end the stack must contain exactly one string; return it.
static String optimal(String prefix) {
    Deque<String> stack = new ArrayDeque<>();
    for (int i = prefix.length() - 1; i >= 0; i--) {
        char c = prefix.charAt(i);
        if (isOperator(c)) {
            if (stack.size() < 2) throw new IllegalArgumentException("operator '" + c + "' at " + i + " lacks operands");
            String left = stack.pop();                      // nearer to the operator = left operand
            String right = stack.pop();
            stack.push("(" + left + c + right + ")");
        } else {
            stack.push(String.valueOf(c));
        }
    }
    if (stack.size() != 1) throw new IllegalArgumentException("malformed prefix expression");
    return stack.pop();
}

Dry run on example 1, *-A/BC-/AKL, scanning from the right:

i c action stack (bottom → top)
10 L push L
9 K push L, K
8 A push L, K, A
7 / pop A, pop K L, (A/K)
6 - pop (A/K), pop L ((A/K)-L)
5 C push ((A/K)-L), C
4 B push ((A/K)-L), C, B
3 / pop B, pop C ((A/K)-L), (B/C)
2 A push ((A/K)-L), (B/C), A
1 - pop A, pop (B/C) ((A/K)-L), (A-(B/C))
0 * pop (A-(B/C)), pop ((A/K)-L) ((A-(B/C))*((A/K)-L))

Complexity. Time O(n) stack operations, with the same O(n × depth) bound on character copying as approach 1, because the same strings are built. Space O(n) for the stack of partial strings.

The two approaches build the same tree, once top-down and once bottom-up; the recursive version is a depth-first walk of the expression tree, and the stack version is the same walk with the recursion made explicit. The test file runs both on identical inputs and expects identical output, including the asymmetric chains -a-b-cd → (a-(b-(c-d))) and ---abcd → (((a-b)-c)-d).

Edge cases and pitfalls