☕ DSA Java Articles

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

Postfix to Prefix Conversion

Medium TUF ID 825 A2Z

Java source ↗ Edit this article ↗

Problem

You are given a valid postfix expression (reverse Polish notation, every operator written after its two operands) and must return the equivalent prefix expression (Polish notation, every operator written before its operands). Operands are single letters or digits; every other character is a binary operator such as + - * / ^.

Both notations are bracket-free and need no precedence table: the position of each operator already says exactly which operands it combines. The conversion only rearranges symbols; it never has to decide what binds tighter.

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

Example 1

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

Example 2

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

Example 3

postfix = "abc^^"
prefix  = "^a^bc"          // a ^ (b ^ c): the grouping survives the conversion

The picture to keep in mind. Every expression is a binary tree whose leaves are operands and whose internal nodes are operators. Postfix is the postorder of that tree (left, right, node) and prefix is the preorder (node, left, right). Converting means reading one traversal and writing the other.

Approach 1: Stack of strings, scanning left to right

Intuition. Postfix was designed to be evaluated with a stack. Read left to right: an operand is pushed, and an operator applies to the two values on top of the stack. We do exactly the same thing, except that instead of numbers the stack holds already-converted prefix strings. An operand is a finished prefix expression of length one. When an operator arrives, the top two strings are its operands, so combining them as operator + left + right produces the prefix form of the bigger sub-expression.

The only thing to get right is the order of the pops. The right operand was finished last, so it is on top: the first pop is the right operand, the second pop is the left operand.

Algorithm.

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

In c + left + right the char is concatenated with a String, so Java performs string concatenation, not integer addition. (Writing c + d + left with two chars first would add their character codes, a classic slip.)

Dry run on "AB+CD-*":

char action stack (bottom to top)
A push A
B push A, B
+ pop B, pop A, push +AB +AB
C push +AB, C
D push +AB, C, D
- pop D, pop C, push -CD +AB, -CD
* pop -CD, pop +AB, push *+AB-CD *+AB-CD

Complexity. Time O(n^2) in the worst case. There are only O(n) pushes and pops, but every concatenation copies both operand strings. On a left-leaning chain such as aa+a+a+..., the string on the stack grows by two characters per operator, so the total copying is 3 + 5 + 7 + ..., which is quadratic. Space O(n) for the stack and its strings.

This is the expected interview answer and is fast enough for typical input sizes. The next approach shows how to make it strictly linear.

Approach 2: Optimal, build the expression tree once

Intuition. The cost in Approach 1 comes from re-copying the same characters every time a sub-expression is wrapped by another operator. We can avoid copying by not producing strings until the very end. Run the same stack algorithm, but push tree nodes instead of strings: an operand becomes a leaf, and an operator becomes a node whose children are the two popped nodes. Creating a node is O(1) no matter how large its subtrees are.

When the scan ends, the stack holds the root of the expression tree. Writing that tree in preorder (node, left subtree, right subtree) is exactly the prefix expression, and a traversal visits each node once.

To avoid recursion (a degenerate chain can be thousands of levels deep), the preorder walk uses an explicit stack: pop a node, write it, then push its right child before its left child so that the left subtree is processed first.

Algorithm.

  1. If the input is empty, return "".
  2. Scan left to right with a stack of nodes. Push a leaf for each operand. For an operator, pop right, pop left, and push new Node(op, left, right).
  3. Preorder: push the root onto a todo stack. While it is not empty, pop a node, append its symbol, push its right child if any, then its left child if any.
  4. Return the built string.
static final class Node {
    final char symbol;
    final Node left, right;

    Node(char symbol, Node left, Node right) {
        this.symbol = symbol;
        this.left = left;
        this.right = right;
    }
}

/** Approach 2: build the expression tree once, then emit its preorder traversal. O(n) time, O(n) space. */
static String expressionTree(String postfix) {
    if (postfix.isEmpty()) return "";
    Deque<Node> st = new ArrayDeque<>();
    for (int i = 0; i < postfix.length(); i++) {
        char c = postfix.charAt(i);
        if (isOperand(c)) {
            st.push(new Node(c, null, null));
        } else {
            Node right = st.pop();
            Node left = st.pop();
            st.push(new Node(c, left, right));
        }
    }
    StringBuilder out = new StringBuilder(postfix.length());
    Deque<Node> todo = new ArrayDeque<>();
    todo.push(st.pop());
    while (!todo.isEmpty()) {                    // iterative preorder: node, left subtree, right subtree
        Node node = todo.pop();
        out.append(node.symbol);
        if (node.right != null) todo.push(node.right);   // pushed first, so it is visited after the left
        if (node.left != null) todo.push(node.left);
    }
    return out.toString();
}

Why the preorder is the prefix expression. By construction each operator node’s left subtree is the left operand and its right subtree is the right operand. Preorder writes the operator, then the whole left operand in prefix form, then the whole right operand in prefix form, which is the recursive definition of prefix notation.

Complexity. Time O(n): one pass to build n nodes, and one traversal that pushes and pops every node once. Space O(n) for the nodes and the two stacks.

Edge cases and pitfalls