☕ DSA Java Articles

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

Postfix to Infix Conversion

Easy TUF ID 824 A2Z

Java source ↗ Edit this article ↗

Problem

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

Infix is the one notation that is ambiguous without help: a*b+c could mean (a*b)+c or a*(b+c). To keep the output unambiguous without reasoning about precedence, the standard version of this problem asks for a fully parenthesised result: every operator together with its two operands is wrapped in one pair of brackets.

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

Example 1

postfix = "ab*c+"
infix   = "((a*b)+c)"      // multiply first, then add c

Example 2

postfix = "abc++"
infix   = "(a+(b+c))"      // b + c is formed first, so it is the inner bracket

Example 3

postfix = "a"
infix   = "a"              // a lone operand gets no brackets

The picture to keep in mind. An expression is a binary tree with operands at the leaves and operators at the internal nodes. Postfix is that tree’s postorder (left, right, node). Fully bracketed infix is its inorder (left, node, right) with a ( before and a ) after every internal node. The conversion reads one traversal and writes the other.

Approach 1: Stack of strings

Intuition. Postfix is built for stack evaluation: scanning left to right, every operator applies to the two most recent complete values. Here the “values” are strings that already hold the infix form of a sub-expression. An operand is a complete sub-expression by itself. When an operator arrives, pop its two operands and push the combined string "(" + left + op + right + ")". At the end, one string remains, and it is the whole expression.

Order matters. The right operand was completed last, so it is on top. The first pop is the right operand and the second is the left operand.

The brackets are what make this correct without a precedence table. Each combined string is a closed unit, so when it later becomes an operand of another operator, its internal structure cannot be misread.

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 "(" + left + c + right + ")".
  3. Return the single remaining string ("" 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("(" + left + c + right + ")");
        }
    }
    return st.isEmpty() ? "" : st.pop();
}

Dry run on "ab*c+":

char action stack (bottom to top)
a push a
b push a, b
* pop b, pop a, push (a*b) (a*b)
c push (a*b), c
+ pop c, pop (a*b), push ((a*b)+c) ((a*b)+c)

Complexity. Time O(n^2) in the worst case. There are O(n) stack operations, but each concatenation copies both operands. A left-leaning chain like aa+a+a+... builds strings of length 5, 9, 13, …, and copying all of them is quadratic in n. Space O(n) for the stack and the strings on it.

This is the answer most people give in an interview and it is fine for inputs of a few thousand characters.

Approach 2: Optimal, expression tree and one bracketed inorder walk

Intuition. The quadratic cost comes from repeatedly copying the same characters each time a sub-expression gets wrapped by another operator. So postpone writing text until the structure is complete. Run the same stack scan, but push tree nodes: a leaf for each operand, and for each operator a new node whose children are the two popped nodes. Building a node is O(1) regardless of how big its subtrees are.

When the scan ends, the stack holds the root. A recursive inorder traversal then writes the answer straight into one StringBuilder: for a leaf, write its symbol; for an operator, write (, the left subtree, the operator, the right subtree, and ). Each node is visited once and each output character is written once.

Algorithm.

  1. If the input is empty, return "".
  2. Scan left to right with a stack of nodes. Operand: push a leaf. Operator: pop right, pop left, push new Node(op, left, right).
  3. Call inorder(root, out) and return out.
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, then write a bracketed inorder traversal into one StringBuilder. 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();
    inorder(st.pop(), out);
    return out.toString();
}

static void inorder(Node node, StringBuilder out) {
    if (node.left == null) {                     // a leaf is an operand
        out.append(node.symbol);
        return;
    }
    out.append('(');
    inorder(node.left, out);
    out.append(node.symbol);
    inorder(node.right, out);
    out.append(')');
}

Why it produces the same string as Approach 1. By induction on the tree: a leaf produces its own character in both methods. For an operator node, Approach 1 produces "(" + L + op + R + ")" where L and R are the strings for the subtrees, and inorder writes (, then whatever the left subtree writes, then op, then the right subtree, then ), which is the same sequence of characters.

Complexity. Time O(n): n nodes are created and each is visited once; the output has length at most n + 2 × (number of operators), which is under 2n. Space O(n) for the nodes, plus recursion depth equal to the tree height. A left-leaning chain has height about n / 2, so for very long degenerate inputs an iterative traversal (with an explicit stack of pending actions) would be safer; the test file exercises a chain of 1000 operators.

Edge cases and pitfalls