Prefix to Infix Conversion

Description

You are given a string S of size N that represents a valid mathematical expression written in prefix notation (also known as Polish notation). In prefix notation, the operator appears before its two operands.

The string contains only lowercase and uppercase English alphabets as operands, and the operators are +, -, *, /, %, and ^.

Your task is to convert this prefix expression into its equivalent infix notation. In infix notation, the operator is placed between its two operands, and each sub-expression is enclosed in parentheses to preserve the correct order of operations.

For example, the prefix expression *+AB-CD means "multiply the result of adding A and B with the result of subtracting D from C," which in infix form becomes ((A+B)*(C-D)).

Examples

Example 1

Input: pre_exp = "*-A/BC-/AKL"

Output: "((A-(B/C))*((A/K)-L))"

Explanation: Breaking down the prefix expression from the outermost operator:

The * operator applies to two sub-expressions: -A/BC and -/AKL.
-A/BC means subtract (B/C) from A, giving (A-(B/C)).
-/AKL means subtract L from (A/K), giving ((A/K)-L).
Multiplying these two results gives ((A-(B/C))*((A/K)-L)).

Example 2

Input: pre_exp = "*+AB-CD"

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

Explanation: The * operator applies to +AB (which is (A+B) in infix) and -CD (which is (C-D) in infix). Combining with * in between gives ((A+B)*(C-D)).

Example 3

Input: pre_exp = "+AB"

Output: "(A+B)"

Explanation: This is the simplest case — a single operator + with two operands A and B. The infix form simply places the operator between them with enclosing parentheses: (A+B).

Constraints

3 ≤ |S| ≤ 10^4
S contains only lowercase and uppercase English alphabets as operands
Operators are limited to: +, -, *, /, %, ^
The input is always a valid prefix expression

Editorial

Brute Force - Recursive Descent Parsing

Intuition

Prefix notation has a natural recursive structure. Every prefix expression is either:

A single operand (a letter like A, B, x), or
An operator followed by two prefix sub-expressions.

This recursive definition directly suggests a recursive parsing approach. Think of it like reading a sentence: when you see an operator, you know the next two "phrases" are its operands. You read the first phrase (which might itself contain nested phrases), then the second, and combine them.

Imagine you are reading the expression *+AB-CD left to right. You see * and think: "I need two things to multiply." You then read +AB and recognize it as (A+B). Then you read -CD and recognize it as (C-D). Finally, you combine: ((A+B)*(C-D)).

We can implement this by maintaining a pointer (index) that advances through the string as we consume characters. Each recursive call handles one complete sub-expression and moves the pointer past it.

Step-by-Step Explanation

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

Step 1: Call solve() at index 0. Character is *.

* is an operator (not a letter).
We need to recursively parse its left operand, then its right operand.
State: idx = 0, char = '*', type = operator
Advance idx to 1. Recursively call solve() for left operand.

Step 2: Recursive call for left operand at index 1. Character is +.

+ is an operator.
We need its left and right operands too.
State: idx = 1, char = '+', type = operator
Advance idx to 2. Recursively call solve() for left operand of +.

Step 3: Recursive call at index 2. Character is A.

A is a letter — it is an operand.
Return "A" immediately. Advance idx to 3.
State: idx = 2 → 3, char = 'A', returns = "A"

Step 4: Back in the + call (Step 2). Left operand = "A". Now parse right operand at index 3. Character is B.

B is an operand. Return "B". Advance idx to 4.
State: idx = 3 → 4, char = 'B', returns = "B"

Step 5: Back in the + call. Left = "A", Right = "B".

Combine: "(" + "A" + "+" + "B" + ")" = "(A+B)"
Return "(A+B)" to the caller (the * call from Step 1).
State: combined = "(A+B)"

Step 6: Back in the * call (Step 1). Left operand = "(A+B)". Now parse right operand at index 4. Character is -.

- is an operator. Recursively parse its left and right operands.
State: idx = 4, char = '-', type = operator
Advance idx to 5.

Step 7: Recursive call at index 5. Character is C.

C is an operand. Return "C". Advance idx to 6.
State: idx = 5 → 6, char = 'C', returns = "C"

Step 8: Parse right operand of - at index 6. Character is D.

D is an operand. Return "D". Advance idx to 7.
State: idx = 6 → 7, char = 'D', returns = "D"

Step 9: Back in the - call (Step 6). Left = "C", Right = "D".

Combine: "(" + "C" + "-" + "D" + ")" = "(C-D)"
Return "(C-D)".

Step 10: Back in the * call (Step 1). Left = "(A+B)", Right = "(C-D)".

Combine: "(" + "(A+B)" + "" + "(C-D)" + ")" = "((A+B)(C-D))"
Return "((A+B)*(C-D))".

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

Algorithm

Initialize a global index pointer idx = 0.
Define a recursive function solve():
a. Read the character at position idx and advance idx by 1.
b. If the character is a letter (operand), return it as a string.
c. If the character is an operator:
- Recursively call solve() to get the left operand string.
- Recursively call solve() to get the right operand string.
- Return "(" + left + operator + right + ")".
Call solve() and return the result.

Code

class Solution {
public:
    int idx;

    string solve(string &preExp) {
        char ch = preExp[idx++];

        // If operand (letter), return as string
        if (isalpha(ch)) {
            return string(1, ch);
        }

        // Operator: recursively parse left and right operands
        string left = solve(preExp);
        string right = solve(preExp);

        return "(" + left + ch + right + ")";
    }

    string preToInfix(string pre_exp) {
        idx = 0;
        return solve(pre_exp);
    }
};

class Solution:
    def preToInfix(self, pre_exp):
        self.idx = 0

        def solve():
            ch = pre_exp[self.idx]
            self.idx += 1

            # If operand (letter), return it
            if ch.isalpha():
                return ch

            # Operator: recursively parse left and right
            left = solve()
            right = solve()

            return "(" + left + ch + right + ")"

        return solve()

class Solution {
    int idx;

    String solve(String preExp) {
        char ch = preExp.charAt(idx++);

        // If operand (letter), return as string
        if (Character.isLetter(ch)) {
            return String.valueOf(ch);
        }

        // Operator: recursively parse left and right operands
        String left = solve(preExp);
        String right = solve(preExp);

        return "(" + left + ch + right + ")";
    }

    String preToInfix(String pre_exp) {
        idx = 0;
        return solve(pre_exp);
    }
}

Complexity Analysis

Time Complexity: O(N²) in the worst case

Each character is visited exactly once during parsing, which is O(N). However, at every operator node, we perform string concatenation to build the infix sub-expression. In languages like Java and Python, string concatenation creates a new string, and the length of intermediate strings can grow up to O(N). For a deeply nested expression (like +A+B+C+D...), concatenation at each level copies an increasingly large string. The total concatenation work sums to O(1 + 2 + 3 + ... + N/2) = O(N²).

Space Complexity: O(N)

The recursion depth equals the nesting depth of the expression. In the worst case (a completely left-skewed or right-skewed expression like +A+B+C...), the recursion depth is O(N/2) = O(N). Each recursive call uses O(1) stack frame space (excluding the result string), giving O(N) total call stack usage.

Why This Approach Is Not Efficient

While the recursive descent approach is conceptually elegant, it has practical limitations:

Recursion depth risk: For a deeply nested prefix expression of length N (e.g., +A+B+C+D+E...), the recursion depth reaches O(N/2). With N up to 10^4, this means up to 5,000 nested function calls. Many language runtimes have default stack sizes that could overflow with this depth, especially in Java or Python (Python's default recursion limit is 1,000).
Function call overhead: Every character triggers at least one function call. Function calls involve saving registers, creating stack frames, and managing return addresses. For 10^4 characters, this overhead adds up compared to a simple iterative loop.
String concatenation cost: At each operator node, we create a new string by concatenating left + operator + right. In languages without mutable strings, this copies all characters, leading to O(N²) total work in the worst case.

Key insight: We can avoid recursion entirely by observing that scanning the prefix expression from right to left allows us to use an iterative approach with an explicit stack. Operands appear first (from the right), and operators combine them — a perfect fit for a stack-based algorithm. This eliminates recursion overhead and the risk of stack overflow.

Optimal Approach - Stack-Based Right-to-Left Traversal

Intuition

Here is a powerful observation: in a prefix expression, operands always appear to the right of their operator. If we scan the expression from right to left, we encounter operands before their operators. This is the perfect setup for a stack!

Think of it like unpacking a gift box from the inside out. The innermost items (operands) are unwrapped first and set aside (pushed onto a stack). When you reach a wrapping layer (operator), you take the last two items you unwrapped (pop from stack), wrap them together with the operator in between (forming an infix sub-expression), and set the combined package aside (push back onto stack).

The algorithm is beautifully simple:

Scan from right to left.
See a letter? Push it onto the stack.
See an operator? Pop two strings from the stack, place the operator between them with parentheses, and push the result back.
When done, the stack holds exactly one element: the complete infix expression.

This avoids recursion entirely — we use an explicit stack data structure that handles arbitrary nesting depth without risking stack overflow.

Step-by-Step Explanation

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

We scan from right to left: D, C, -, B, A, +, *

Step 1: Read 'D' (index 6). It is a letter — an operand.

Push "D" onto the stack.
Stack: ["D"]

Step 2: Read 'C' (index 5). It is a letter — an operand.

Push "C" onto the stack.
Stack: ["D", "C"]

Step 3: Read '-' (index 4). It is an operator.

Pop two operands: first pop = "C" (left operand), second pop = "D" (right operand).
Combine: "(" + "C" + "-" + "D" + ")" = "(C-D)".
Push "(C-D)" back onto the stack.
Stack: ["(C-D)"]

Step 4: Read 'B' (index 3). It is an operand.

Push "B" onto the stack.
Stack: ["(C-D)", "B"]

Step 5: Read 'A' (index 2). It is an operand.

Push "A" onto the stack.
Stack: ["(C-D)", "B", "A"]

Step 6: Read '+' (index 1). It is an operator.

Pop two operands: first pop = "A" (left), second pop = "B" (right).
Combine: "(" + "A" + "+" + "B" + ")" = "(A+B)".
Push "(A+B)" back.
Stack: ["(C-D)", "(A+B)"]

Step 7: Read '*' (index 0). It is an operator.

Pop two operands: first pop = "(A+B)" (left), second pop = "(C-D)" (right).
Combine: "(" + "(A+B)" + "" + "(C-D)" + ")" = "((A+B)(C-D))".
Push result.
Stack: ["((A+B)*(C-D))"]

Result: The stack has one element: "((A+B)*(C-D))".

Prefix to Infix — Stack-Based Right-to-Left Conversion — Watch how scanning the prefix expression from right to left with a stack naturally builds the infix expression. Operands are pushed, and operators combine the top two stack elements into parenthesized infix sub-expressions.

Algorithm

Create an empty stack of strings.
Scan the prefix expression from right to left (from the last character to the first):
- If the current character is a letter (operand): push it onto the stack as a single-character string.
- If the current character is an operator (+, -, *, /, %, ^):
  a. Pop the top element from the stack — this is the left operand.
  b. Pop the next top element — this is the right operand.
  c. Form the string: "(" + left + operator + right + ")".
  d. Push this combined string back onto the stack.
After processing all characters, the stack contains exactly one element — the infix expression. Return it.

Code

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

class Solution {
public:
    string preToInfix(string pre_exp) {
        stack<string> st;
        int n = pre_exp.size();

        // Scan from right to left
        for (int i = n - 1; i >= 0; i--) {
            char ch = pre_exp[i];

            if (isalpha(ch)) {
                // Operand: push as a single-character string
                st.push(string(1, ch));
            } else {
                // Operator: pop two operands, combine, push result
                string left = st.top(); st.pop();
                string right = st.top(); st.pop();
                st.push("(" + left + ch + right + ")");
            }
        }

        return st.top();
    }
};

class Solution:
    def preToInfix(self, pre_exp):
        stack = []

        # Scan from right to left
        for i in range(len(pre_exp) - 1, -1, -1):
            ch = pre_exp[i]

            if ch.isalpha():
                # Operand: push directly
                stack.append(ch)
            else:
                # Operator: pop two operands, combine, push result
                left = stack.pop()
                right = stack.pop()
                stack.append("(" + left + ch + right + ")")

        return stack[-1]

import java.util.Stack;

class Solution {
    String preToInfix(String pre_exp) {
        Stack<String> stack = new Stack<>();
        int n = pre_exp.length();

        // Scan from right to left
        for (int i = n - 1; i >= 0; i--) {
            char ch = pre_exp.charAt(i);

            if (Character.isLetter(ch)) {
                // Operand: push as string
                stack.push(String.valueOf(ch));
            } else {
                // Operator: pop two operands, combine, push result
                String left = stack.pop();
                String right = stack.pop();
                stack.push("(" + left + ch + right + ")");
            }
        }

        return stack.peek();
    }
}

Complexity Analysis

Time Complexity: O(N)

We traverse the string exactly once from right to left, processing each of the N characters in constant time (excluding string concatenation). Each character triggers at most one push and contributes to at most one pop-combine-push operation. The loop itself is O(N).

Note: String concatenation at each operator step creates new strings. In the worst case, the total characters across all concatenations sum to O(N²). However, using a StringBuilder or similar mutable string structure can reduce this. The core algorithmic work (stack operations and character classification) is strictly O(N).

Space Complexity: O(N)

The stack holds at most O(N) elements at any point. In the worst case, all operands are pushed before any operator is encountered (this happens when the rightmost portion of the expression is all operands). Additionally, the intermediate and final strings together occupy O(N) space. No recursion is used, so there is no call stack overhead beyond the iterative loop.

Language Essentials & Syntax

EASY

Pattern-Based Logic Building

EASY

Standard Libraries & Collections

EASY

Essential Mathematics

EASY

MEDIUM

Recursion Fundamentals

EASY

Hashing Essentials

EASY

MEDIUM

Comparison-Based Sorts

EASY

Divide & Conquer Sorts

EASY

MEDIUM

Array Fundamentals

EASY

MEDIUM

Intermediate Array Problems

EASY

MEDIUM

Advanced Array Challenges

EASY

MEDIUM

HARD

Searching in Sorted Arrays

EASY

MEDIUM

Search Space Reduction

EASY

MEDIUM

HARD

Matrix Binary Search

EASY

MEDIUM

HARD

Core String Operations

EASY

MEDIUM

Intermediate String Challenges

EASY

MEDIUM

Singly Linked List Basics

EASY

MEDIUM

Doubly Linked List Basics

EASY

MEDIUM

Linked List Techniques

EASY

MEDIUM

Doubly Linked List Techniques

MEDIUM

HARD

Advanced Linked List Challenges

MEDIUM

HARD

Building Recursive Thinking

EASY

MEDIUM

Generating Subsequences

EASY

MEDIUM

Exhaustive Search & Constraint Solving

MEDIUM

HARD

Bitwise Operations Fundamentals

EASY

MEDIUM

Bit Manipulation Applications

EASY

MEDIUM

Number Theory & Primes

EASY

MEDIUM

HARD