Log inSign up
mediumGeeksforGeeksNot Started

Prefix to Infix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on GeeksforGeeks
Lesson

Problem Statement

You are given a string prefix representing a Prefix expression. Convert it into an Infix expression.

Infix expression: An expression where operators are placed between operands (e.g. ((A+B)*(C-D))). Prefix expression: An expression where operators precede operands (e.g. *+AB-CD).

Example 1 · Standard Prefix:

Input: prefix = "*-A/BC-/AKL"
Output: "((A-(B/C))*((A/K)-L))"
Explanation: Converted following standard right-to-left operand pairing with parentheses.

Example 2 · Simple Arithmetic:

Input: prefix = "*+AB-CD"
Output: "((A+B)*(C-D))"
Explanation: +AB becomes (A+B), -CD becomes (C-D), and * joins them into ((A+B)*(C-D)).

Constraints:

  • 1 <= prefix.length <= 104
  • prefix contains lowercase and uppercase alphabets and operators (+, -, *, /, ^).

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why right-to-left traversal is optimal for prefix expressions.
  • Recognize operand order invariance: under right-to-left scan, first popped is left operand, second popped is right operand.
  • Construct parenthesized AST expressions without explicit tree node allocation.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Algorithmic Decision Tree:

  • Loop i from prefix.length - 1 down to 0.
  • If character is alphanumeric -> push to string stack.
  • If character is an operator op:
  • Pop op1 = stack.pop() (left operand).
  • Pop op2 = stack.pop() (right operand).
  • Push "(" + op1 + op + op2 + ")".
  • Return stack.top() at the end.

Connected Patterns:

Postfix to InfixPrefix to PostfixInfix to Postfix

1. Recursive Expression Subtree Parsing

Intuition

Use recursive descent: an expression is either an operand or an operator followed by two valid subexpressions.

Algorithm

  1. Step 1: Track current index pointer in prefix string.
  2. Step 2: If current character is operand, return it.
  3. Step 3: If operator, recursively parse left child, then right child.
  4. Step 4: Return "(" + left + op + right + ")".
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4class Solution {
5 int idx = 0;
6 std::string parse(const std::string& s) {
7 char c = s[idx++];
8 if (isalnum(c)) {
9 return std::string(1, c);
10 }
11 std::string left = parse(s);
12 std::string right = parse(s);
13 return "(" + left + c + right + ")";
14 }
15public:
16 std::string preToInfix(std::string pre_exp) {
17 idx = 0;
18 return parse(pre_exp);
19 }
20};
21
22int main() {
23 Solution solver;
24 std::cout << "Infix: " << solver.preToInfix("*+AB-CD") << std::endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(N^2) — Recursive top-down splitting constructs substrings taking O(N) per node across O(N) operations.
  • Space complexity: O(N) — O(N) recursion call stack.

Why Brute Force Doesn't Scale:

Deep recursion risks call stack limits on long expressions.

Right-to-left stack processes 100,000 characters in <5ms.

2. Deque Right-to-Left Accumulator

Intuition

Iterate right to left, storing intermediate operand chunks in a deque.

Algorithm

  1. Step 1: Loop from N-1 down to 0.
  2. Step 2: Push operands to deque.
  3. Step 3: When operator found, pop two chunks, combine with parentheses, and push back.
  4. Step 4: Return front of deque.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <deque>
4
5class Solution {
6public:
7 std::string preToInfix(std::string pre_exp) {
8 std::deque<std::string> st;
9 for (int i = (int)pre_exp.size() - 1; i >= 0; i--) {
10 char c = pre_exp[i];
11 if (isalnum(c)) {
12 st.push_back(std::string(1, c));
13 } else {
14 std::string op1 = st.back(); st.pop_back();
15 std::string op2 = st.back(); st.pop_back();
16 st.push_back("(" + op1 + c + op2 + ")");
17 }
18 }
19 return st.back();
20 }
21};
22
23int main() {
24 Solution solver;
25 std::cout << "Infix: " << solver.preToInfix("*+AB-CD") << std::endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(N) — Single linear pass from right to left using Deque container.
  • Space complexity: O(N) — O(N) deque space.

3. Optimal Right-to-Left Stack Traversal

Intuition

Scanning prefix notation from right to left processes operands first. When an operator arrives, its two operands are already on top of the stack in correct left-to-right order.

Algorithm

  1. Step 1: Initialize an empty stack st of strings.
  2. Step 2: Iterate i from prefix.length - 1 down to 0.
  3. Step 3: If c = prefix[i] is alphanumeric, push string(c) onto st.
  4. Step 4: If c is an operator, pop op1 = st.top(), pop op2 = st.top(), construct "(" + op1 + c + op2 + ")" and push onto st.
  5. Step 5: Return st.top().

Optimal Prefix to Infix Stack Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Stack: ['D']
Visual state
Values and pointers at this exact step
stack
TOP
'D'
Push adds to the top · Pop removes from the top
Why this step matters

Stack: [D]

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <stack>
4
5class Solution {
6public:
7 std::string preToInfix(std::string pre_exp) {
8 std::stack<std::string> st;
9 for (int i = (int)pre_exp.length() - 1; i >= 0; i--) {
10 char c = pre_exp[i];
11 if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')) {
12 st.push(std::string(1, c));
13 } else {
14 std::string op1 = st.top(); st.pop();
15 std::string op2 = st.top(); st.pop();
16 std::string res = "(" + op1 + c + op2 + ")";
17 st.push(res);
18 }
19 }
20 return st.top();
21 }
22};
23
24int main() {
25 Solution solver;
26 std::cout << "Infix: " << solver.preToInfix("*+AB-CD") << std::endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N) — Single reverse pass across N characters with O(1) push and pop operations.
  • Space complexity: O(N) — O(N) space for operand stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Subtree ParsingO(N^2)O(N)Recursive descent with forward index traversal.Recursive function calls and substring concatenation.
2.Deque Right-to-Left AccumulatorO(N)O(N)Deque buffer right-to-left traversal.None.
3.Optimal Right-to-Left Stack TraversalOptimalO(N)O(N)Reverse linear scan with LIFO stack where op1=left, op2=right.None (Optimal).

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Scanning left to right for prefix without a recursion counter, causing incorrect operand pairing.

Pitfall 2:

Swapping operands: computing (op2 op op1) instead of (op1 op op2).

Pitfall 3:

Omitting parentheses around subexpressions.

Crucial Edge Cases to Validate:

  • Single operand `prefix = 'A'` — Returns 'A'.
  • Deeply nested expression — Parentheses preserve complete evaluation hierarchy.
  • Division and subtraction operators — Non-commutative operators preserve exact left/right ordering.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast Postfix vs Prefix parsing: Postfix scans Left-to-Right; Prefix scans Right-to-Left.
  2. Emphasize the popped operand ordering: under Right-to-Left scan, top() is the LEFT operand op1 and next top() is the RIGHT operand op2.
  3. Derive the O(N) linear time and O(N) auxiliary space complexity.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we traverse the prefix expression from right to left instead of left to right?

2.When scanning right to left, what is the order of popped operands for an operator?

Back to DSA Sheet