☕ DSA Java Articles

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

Prefix to Postfix Conversion

Medium TUF ID 849 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a valid prefix expression (Polish notation, operator before its operands) and must return the equivalent postfix expression (reverse Polish notation, operator after its operands). Every operand is a single letter or digit, and every other character is a binary operator such as + - * / ^.

Neither prefix nor postfix needs brackets or precedence rules: the order of the symbols alone fixes which operator applies to which operands. That is why this conversion is purely structural. Precedence never has to be consulted.

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

Example 1

prefix  = "*+AB-CD"
postfix = "AB+CD-*"        // both mean (A + B) * (C - D)

Example 2

prefix  = "*-A/BC-/AKL"
postfix = "ABC/-AK/L-*"    // both mean (A - B / C) * (A / K - L)

Example 3

prefix  = "A"
postfix = "A"              // a lone operand is already in every notation

The picture to keep in mind. Any expression is a binary tree: leaves are operands, internal nodes are operators with a left and a right child. Prefix is that tree written in preorder (node, left, right). Postfix is the same tree written in postorder (left, right, node). So the task is to re-serialise a tree we are given in one traversal order into another, ideally without building the tree explicitly.

Approach 1: Stack of strings, scanning right to left

Intuition. In prefix, an operator comes before both of its operands. If we read the string from the right, then by the time we reach an operator, both of its operands have already been read in full. Keep each finished sub-expression on a stack, already converted to postfix. A single operand is a finished sub-expression of length one. When an operator arrives, the two most recent pieces on the stack are exactly its operands.

Which one is the left operand? The left operand sits immediately after the operator in the string, so when scanning from the right it was finished last and is on top. The first pop is the left operand and the second pop is the right operand. Combine them as left + right + operator and push the result back.

Algorithm.

  1. Create an empty stack of strings.
  2. Walk i from n - 1 down to 0:
    • If prefix[i] is an operand, push it as a one-character string.
    • Otherwise pop left, pop right, and push left + right + prefix[i].
  3. The only string left on the stack is the answer (an empty input gives "").
static String stackOfStrings(String prefix) {
    Deque<String> st = new ArrayDeque<>();
    for (int i = prefix.length() - 1; i >= 0; i--) {
        char c = prefix.charAt(i);
        if (isOperand(c)) {
            st.push(String.valueOf(c));
        } else {
            String left = st.pop();              // pushed last, so it is the left operand
            String right = st.pop();
            st.push(left + right + c);
        }
    }
    return st.isEmpty() ? "" : st.pop();
}

Dry run on "*+AB-CD":

i char action stack (bottom to top)
6 D push D
5 C push D, C
4 - pop C, pop D, push CD- CD-
3 B push CD-, B
2 A push CD-, B, A
1 + pop A, pop B, push AB+ CD-, AB+
0 * pop AB+, pop CD-, push AB+CD-* AB+CD-*

Complexity. Time O(n^2) in the worst case: there are O(n) stack operations, but each concatenation copies both pieces. For a chain like +++...+aaaa...a the piece on the stack grows by two characters per operator, so the copies add up to 1 + 3 + 5 + ..., which is quadratic. For balanced trees it is closer to O(n log n). Space O(n) for the stack and the pieces it holds.

This is the solution most interviewers expect and it is perfectly fine for inputs of a few thousand characters. The two approaches below show how to remove the repeated copying.

Approach 2: Recursive descent

Intuition. Prefix notation has a tiny grammar: an expression is either a single operand, or an operator followed by two expressions. That definition is already a recursive algorithm. Write parse(i), which reads exactly one expression starting at index i, appends its postfix form to a shared StringBuilder, and returns the index just past it.

If s[i] is an operand, append it and return i + 1. If it is an operator, its left operand starts at i + 1; parse it and remember where it ended. The right operand starts exactly there; parse it too. Only then append the operator, because postfix puts the operator after both operands.

Nothing is ever concatenated: every character is appended to the output exactly once, in its final position.

Algorithm.

  1. If the input is empty, return "".
  2. Call parse(s, 0, out) and return out.
  3. parse(s, i, out): if s[i] is an operand, append it and return i + 1. Otherwise a = parse(s, i + 1, out), b = parse(s, a, out), append s[i], return b.
static String recursiveDescent(String prefix) {
    if (prefix.isEmpty()) return "";
    StringBuilder out = new StringBuilder(prefix.length());
    parse(prefix, 0, out);
    return out.toString();
}

/** Converts the prefix expression starting at index i, appends its postfix form, returns the index just past it. */
static int parse(String s, int i, StringBuilder out) {
    char c = s.charAt(i);
    if (isOperand(c)) {
        out.append(c);
        return i + 1;
    }
    int afterLeft = parse(s, i + 1, out);      // left operand starts right after the operator
    int afterRight = parse(s, afterLeft, out); // right operand starts where the left one ended
    out.append(c);                             // in postfix the operator comes last
    return afterRight;
}

Complexity. Time O(n): each call handles one character and appends one character. Space O(h) for the call stack, where h is the height of the expression tree. For a chain like +++...+aaaa the height is about n / 2, and a Java thread’s default stack overflows after roughly ten thousand or more frames, depending on the JVM. That is the one weakness this approach has, and the next approach removes it.

Approach 3: Optimal, iterative with operand counters

Intuition. Look at when the recursive version writes each character. An operand is written the moment it is read. An operator is written the moment its second operand finishes. So the only state we need is: which operators have started but not finished, and how many operands each has completed so far. The recursion kept that in its call stack; we can keep it in an explicit stack of {operator, count} pairs instead.

The stack always holds exactly the operators whose sub-expressions are still open, innermost on top, which is precisely the call stack of Approach 2. Since the order of writes is identical, so is the output.

Algorithm.

  1. Create an empty output builder and an empty stack pending of {operator, count}.
  2. For each character c from left to right:
    • If c is an operator, push {c, 0} and continue.
    • Otherwise append c. Then, while pending is not empty, increment the top’s count; if it became 2, append the top’s operator and pop it; otherwise stop.
  3. Return the output.
static String optimal(String prefix) {
    StringBuilder out = new StringBuilder(prefix.length());
    Deque<int[]> pending = new ArrayDeque<>();   // {operator, operands completed so far}
    for (int i = 0; i < prefix.length(); i++) {
        char c = prefix.charAt(i);
        if (!isOperand(c)) {
            pending.push(new int[]{c, 0});
            continue;
        }
        out.append(c);
        // a complete operand just ended; an operator that now has both operands is complete too
        while (!pending.isEmpty() && ++pending.peek()[1] == 2) {
            out.append((char) pending.pop()[0]);
        }
    }
    return out.toString();
}

++pending.peek()[1] == 2 increments the counter stored in the top array and tests the new value in one expression. Storing the operator as an int inside the array is fine; it is cast back to char when written.

Dry run on "*+AB-CD":

char output after this step pending (bottom to top)
*   {*,0}
+   {*,0} {+,0}
A A {*,0} {+,1}
B AB, then + completes: AB+ {*,1}
- AB+ {*,1} {-,0}
C AB+C {*,1} {-,1}
D AB+CD, - completes, then * completes: AB+CD-* empty

Complexity. Time O(n): every character is appended once, every operator is pushed and popped once, and each iteration of the inner loop either pops (bounded by the number of operators overall) or stops. Space O(n) for the stack of pending operators, and no recursion at all.

Edge cases and pitfalls