Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Postfix to Infix Conversion

MEDIUMProblemSolveExternal Links

Description

You are given a string that represents a valid mathematical expression in postfix form (also known as Reverse Polish Notation). Convert it to its equivalent infix form.

Postfix Notation: Operators are placed after their operands. For example, AB+ means A + B.

Infix Notation: Operators are placed between their operands, which is the standard mathematical notation humans use. For example, A + B. When converting from postfix, we must add parentheses around each sub-expression to preserve the correct evaluation order.

Your task is to convert the given postfix expression into a fully parenthesized infix expression.

Examples

Example 1

Input: post_exp = "ab*c+"

Output: "((a*b)+c)"

Explanation: First, ab* means a * b, giving the sub-expression (a*b). Then + combines (a*b) and c, giving ((a*b)+c). Each operator-operand group is wrapped in parentheses.

Example 2

Input: post_exp = "ab+"

Output: "(a+b)"

Explanation: The postfix ab+ means a + b. In fully parenthesized infix form: (a+b).

Example 3

Input: post_exp = "AB+CD-*"

Output: "((A+B)*(C-D))"

Explanation: AB+ → (A+B), CD- → (C-D), then * combines them: ((A+B)*(C-D)). The parentheses make the evaluation order explicit without relying on operator precedence rules.

Example 4

Input: post_exp = "abc*+de/-"

Output: "((a+(b*c))-(d/e))"

Explanation: Processing left to right: bc* → (b*c), then a + (b*c) gives (a+(b*c)). Next, de/ → (d/e). Finally, - combines: ((a+(b*c))-(d/e)).

Constraints

  • 3 ≤ post_exp.length() ≤ 10⁴
  • The input is a valid postfix expression
  • Operands are single characters (letters)
  • Operators are one of: +, -, *, /, ^

Editorial

Brute Force

Intuition

Just as with other expression notation conversions, the most conceptually straightforward approach is to build an expression tree from the postfix expression and then perform an in-order traversal to produce the infix result.

Recall that a binary expression tree represents:

  • Operands as leaf nodes
  • Operators as internal nodes with left and right children

Different tree traversals yield different notations:

  • Pre-order (Root → Left → Right) → Prefix
  • In-order (Left → Root → Right) → Infix
  • Post-order (Left → Right → Root) → Postfix

So our strategy is:

  1. Build the expression tree from postfix using a stack of tree nodes
  2. Perform in-order traversal, adding parentheses around each sub-expression

During in-order traversal, for each internal (operator) node, we output ( + left subtree result + operator + right subtree result + ). Leaf nodes simply return their operand character.

This approach is general-purpose — the same tree can be traversed in any order to produce any notation. However, it requires constructing an intermediate tree data structure, which adds complexity.

Step-by-Step Explanation

Let's trace through with ab*c+:

Phase 1 — Build the Expression Tree:

Step 1: Read a — operand → create Node(a), push. Stack: [Node(a)]

Step 2: Read b — operand → create Node(b), push. Stack: [Node(a), Node(b)]

Step 3: Read * — operator → pop Node(b) (right child), pop Node(a) (left child). Create Node(*) with children a and b. Push. Stack: [Node(*)]

Step 4: Read c — operand → create Node(c), push. Stack: [Node(*), Node(c)]

Step 5: Read + — operator → pop Node(c) (right child), pop Node(*) (left child). Create Node(+) as root. Push. Stack: [Node(+)]

The expression tree:

        +
       / \
      *   c
     / \
    a   b

Phase 2 — In-order Traversal with Parentheses:

Starting at root +:

  • It's an operator node → output (
  • Go left to *:
    • It's an operator node → output (
    • Go left to a → leaf → output a
    • Output *
    • Go right to b → leaf → output b
    • Output ) → sub-result: (a*b)
  • Output +
  • Go right to c → leaf → output c
  • Output ) → final: ((a*b)+c)

Result: ((a*b)+c) ✓

Expression tree for postfix expression ab*c+ showing root node + with left subtree * having children a and b, and right child c, with in-order traversal path marked
Expression tree for postfix expression ab*c+ showing root node + with left subtree * having children a and b, and right child c, with in-order traversal path marked

Building Expression Tree from Postfix and In-order Traversal — Watch how we build an expression tree from 'ab*c+' using a node stack, then perform in-order traversal with parenthesization to get the infix expression '((a*b)+c)'.

Algorithm

Phase 1 — Build Expression Tree:

  1. Initialize an empty stack of tree nodes
  2. Scan the postfix expression left to right:
    a. Operand → create leaf node, push onto stack
    b. Operator → pop right child, pop left child, create operator node, push
  3. The remaining node is the root

Phase 2 — In-order Traversal with Parentheses:
4. Define recursive function inOrder(node):

  • If node is a leaf: return its character
  • If node is an operator: return "(" + inOrder(left) + node.data + inOrder(right) + ")"
  1. Call inOrder(root) to get the infix expression

Code

#include <string>
#include <stack>
using namespace std;

struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c) : data(c), left(nullptr), right(nullptr) {}
};

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

string inOrder(TreeNode* root) {
    if (!root) return "";
    // Leaf node — just return the operand
    if (!root->left && !root->right) {
        return string(1, root->data);
    }
    // Operator node — wrap in parentheses
    return "(" + inOrder(root->left) + string(1, root->data) + inOrder(root->right) + ")";
}

string postToInfix(string post_exp) {
    stack<TreeNode*> st;
    for (char c : post_exp) {
        if (isOperator(c)) {
            TreeNode* node = new TreeNode(c);
            node->right = st.top(); st.pop();
            node->left = st.top(); st.pop();
            st.push(node);
        } else {
            st.push(new TreeNode(c));
        }
    }
    return inOrder(st.top());
}
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def is_operator(c):
    return c in "+-*/^"

def in_order(root):
    if not root:
        return ""
    # Leaf node
    if not root.left and not root.right:
        return root.data
    # Operator node — wrap in parentheses
    return "(" + in_order(root.left) + root.data + in_order(root.right) + ")"

def postToInfix(post_exp):
    stack = []
    for c in post_exp:
        if is_operator(c):
            node = TreeNode(c)
            node.right = stack.pop()
            node.left = stack.pop()
            stack.append(node)
        else:
            stack.append(TreeNode(c))
    return in_order(stack[-1])
import java.util.Stack;

class Solution {
    static class TreeNode {
        char data;
        TreeNode left, right;
        TreeNode(char c) { data = c; left = right = null; }
    }

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

    static String inOrder(TreeNode root) {
        if (root == null) return "";
        if (root.left == null && root.right == null) {
            return String.valueOf(root.data);
        }
        return "(" + inOrder(root.left) + root.data + inOrder(root.right) + ")";
    }

    static String postToInfix(String post_exp) {
        Stack<TreeNode> st = new Stack<>();
        for (char c : post_exp.toCharArray()) {
            if (isOperator(c)) {
                TreeNode node = new TreeNode(c);
                node.right = st.pop();
                node.left = st.pop();
                st.push(node);
            } else {
                st.push(new TreeNode(c));
            }
        }
        return inOrder(st.peek());
    }
}

Complexity Analysis

Time Complexity: O(N²)

Building the tree takes O(N). The in-order traversal visits each node once, but at each operator node, string concatenation creates a new string. The concatenation "(" + left + operator + right + ")" copies all characters of the left and right substrings. In the worst case (a skewed tree), this results in O(N²) total character copies.

Space Complexity: O(N)

We create N tree node objects. The recursive in-order traversal uses O(H) stack space where H is the tree height — O(N) worst case for skewed trees. The intermediate strings during concatenation also use O(N) space.

Why This Approach Is Not Efficient

The expression tree approach introduces unnecessary complexity:

1. Redundant Intermediate Structure: We build an entire tree of N nodes only to immediately walk through it and discard it. The tree serves no purpose beyond converting the notation — it's an expensive middleman.

2. Memory Overhead: Each tree node requires dynamic memory allocation (a character + two pointers + object overhead). For an expression of length 10,000, that's 10,000 heap allocations. In languages with garbage collection (Java, Python), this adds GC pressure.

3. Recursive Traversal Risk: In-order traversal is recursive. For skewed expressions like abcde++++ (which produce a chain-like tree of height N), the recursion depth equals N. With N up to 10,000, this risks stack overflow in environments with limited recursion depth.

4. Two-Pass Design: The algorithm scans the input once to build the tree, then traverses the tree — two complete passes over the data.

Key Insight: We can skip the tree entirely. Instead of building nodes and later extracting infix strings via traversal, we can directly build infix sub-expressions as strings during a single pass through the postfix expression, using a stack of strings. This is simpler, faster (same asymptotic complexity but much better constants), and avoids recursion entirely.

Optimal Approach - Direct Stack-Based String Manipulation

Intuition

The direct approach mirrors the tree approach but eliminates the tree. Instead of pushing nodes onto the stack, we push strings representing infix sub-expressions.

The key rule is:

  • When we see an operand, push it as a string
  • When we see an operator, pop two strings, wrap them as "(" + op2 + operator + op1 + ")", and push the result

Here, op1 is the first string popped (top of stack = right operand) and op2 is the second string popped (left operand). We place the operator between them and wrap with parentheses — that's exactly what infix notation is!

Why does the order matter? In postfix, operands appear in left-to-right order. The operand pushed first (earlier in the expression) sits deeper in the stack, so it's popped second. This naturally becomes the left operand in the infix expression. The operand pushed later (right operand) is on top and gets popped first.

This is identical to the tree approach's in-order traversal result, but we compute it inline as we go — no tree, no recursion, just a stack and string concatenation.

Think of it like building with LEGO: instead of first assembling a model and then photographing it from the side (tree + in-order traversal), you arrange each piece directly into the final picture as you go.

Step-by-Step Explanation

Let's trace through with AB+CD-*:

Step 1: Read A. Operand → push "A". Stack: ["A"]

Step 2: Read B. Operand → push "B". Stack: ["A", "B"]

Step 3: Read +. Operator → pop "B" (op1), pop "A" (op2). Form infix: "(" + "A" + "+" + "B" + ")" = "(A+B)". Push. Stack: ["(A+B)"]

Step 4: Read C. Operand → push "C". Stack: ["(A+B)", "C"]

Step 5: Read D. Operand → push "D". Stack: ["(A+B)", "C", "D"]

Step 6: Read -. Operator → pop "D" (op1), pop "C" (op2). Form: "(C-D)". Push. Stack: ["(A+B)", "(C-D)"]

Step 7: Read *. Operator → pop "(C-D)" (op1), pop "(A+B)" (op2). Form: "((A+B)*(C-D))". Push. Stack: ["((A+B)*(C-D))"]

Result: "((A+B)*(C-D))" ✓

Notice how each operator step produces a fully parenthesized infix sub-expression. The parentheses naturally nest to preserve the correct evaluation order, exactly as they would in the tree traversal — but without the tree.

Direct Stack Conversion — Postfix to Infix in One Pass — Watch how we convert 'AB+CD-*' to infix '((A+B)*(C-D))' using a single stack of strings. Each operator pops two strings and pushes the parenthesized infix expression.

Algorithm

  1. Initialize an empty stack of strings
  2. Scan the postfix expression from left to right, for each character c:
    a. If c is an operand (not an operator):
    • Push c as a single-character string onto the stack
      b. If c is an operator (+, -, *, /, ^):
    • Pop the top element → call it op1 (right operand)
    • Pop the next element → call it op2 (left operand)
    • Form the infix string: "(" + op2 + c + op1 + ")"
    • Push this combined string onto the stack
  3. After processing all characters, the stack contains exactly one element
  4. Return that element — it is the fully parenthesized infix expression

Code

#include <string>
#include <stack>
using namespace std;

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

string postToInfix(string post_exp) {
    stack<string> st;
    for (char c : post_exp) {
        if (isOperator(c)) {
            string op1 = st.top(); st.pop();
            string op2 = st.top(); st.pop();
            string result = "(" + op2 + string(1, c) + op1 + ")";
            st.push(result);
        } else {
            st.push(string(1, c));
        }
    }
    return st.top();
}
def postToInfix(post_exp: str) -> str:
    operators = set("+-*/^")
    stack = []
    for c in post_exp:
        if c in operators:
            op1 = stack.pop()
            op2 = stack.pop()
            stack.append("(" + op2 + c + op1 + ")")
        else:
            stack.append(c)
    return stack[-1]
import java.util.Stack;

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

    static String postToInfix(String post_exp) {
        Stack<String> st = new Stack<>();
        for (char c : post_exp.toCharArray()) {
            if (isOperator(c)) {
                String op1 = st.pop();
                String op2 = st.pop();
                st.push("(" + op2 + c + op1 + ")");
            } else {
                st.push(String.valueOf(c));
            }
        }
        return st.peek();
    }
}

Complexity Analysis

Time Complexity: O(N²)

We make a single pass through the expression of length N. Each character involves O(1) stack operations. However, string concatenation at each operator step creates a new string. The concatenation "(" + op2 + c + op1 + ")" copies all characters from both operand strings. In the worst case (a skewed expression like abc*+), the concatenation at the last operator copies nearly all N characters, and the total work across all operators sums to O(N²).

Note: This can be optimized to O(N) using StringBuilder (Java) or building with lists and joining at the end, but the straightforward approach shown here is O(N²).

Space Complexity: O(N)

The stack holds at most O(N) strings (when all operands are pushed before any operator). The total length of all strings stored on the stack at any moment is proportional to the output length, which is O(N) — each original character appears in exactly one string, plus a constant number of parentheses per operator. No auxiliary data structures beyond the stack are used.