Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Prefix to Postfix Conversion

MEDIUMProblemSolveExternal Links

Description

You are given a string 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.

Your task is to convert this prefix expression into its equivalent postfix notation (also known as Reverse Polish notation). In postfix notation, the operator appears after its two operands.

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

For example, the prefix expression *+AB-CD means "multiply the sum of A and B by the difference of C and D." In postfix form, this becomes AB+CD-* — the operands come first, followed by their operator.

Examples

Example 1

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

Output: "ABC/-AK/L-*"

Explanation: Breaking down the prefix expression:

  • * operates on two sub-expressions: -A/BC and -/AKL.
  • -A/BC in postfix: A is the left operand, /BC becomes BC/ in postfix, so the subtraction becomes ABC/-.
  • -/AKL in postfix: /AK becomes AK/ in postfix, L is the right operand, so the subtraction becomes AK/L-.
  • The final * combines both: ABC/-AK/L-*.

Example 2

Input: pre_exp = "*+AB-CD"

Output: "AB+CD-*"

Explanation: The + operates on A and B → AB+ in postfix. The - operates on C and D → CD- in postfix. The * combines them → AB+CD-*.

Example 3

Input: pre_exp = "+AB"

Output: "AB+"

Explanation: This is the simplest possible prefix expression — one operator with two operands. In postfix notation, the operands come first followed by the operator: AB+.

Constraints

  • 3 ≤ |pre_exp| ≤ 100
  • The string 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

Just like prefix notation has a recursive structure (an operator followed by two sub-expressions), we can use recursion to parse and convert it.

The key difference between prefix-to-infix and prefix-to-postfix is simply how we reassemble the pieces:

  • In infix: (left operator right) — operator goes between operands.
  • In postfix: left right operator — operator goes after operands.

Imagine reading a recipe written in a strange format: "MIX ADD flour sugar BLEND butter eggs." You need to restructure it as: "flour sugar ADD butter eggs BLEND MIX" — the actions (operators) come at the end of each group.

We maintain a pointer that moves through the prefix string from left to right. At each position:

  • If we see a letter (operand), we return it immediately.
  • If we see an operator, we recursively obtain its left and right operand strings, then concatenate them as left + right + operator.

This recursive parsing naturally handles nested sub-expressions because each recursive call consumes exactly one complete sub-expression from the input.

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. We need its left and right operand sub-expressions in postfix form.
  • Advance idx to 1. Recursively call solve() for the left operand.
  • State: idx = 0, char = '*', type = operator

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

  • + is an operator. Recursively parse its left operand.
  • Advance idx to 2.
  • State: idx = 1, char = '+', type = operator

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

  • A is an operand. Return "A". Advance idx to 3.
  • State: idx = 2 → 3, returns = "A"

Step 4: Back in the + call. Left = "A". Parse right operand at index 3. Character is B.

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

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

  • Postfix combination: left + right + operator = "A" + "B" + "+" = "AB+"
  • Return "AB+".
  • State: combined = "AB+"

Step 6: Back in the * call. Left = "AB+". Parse right operand at index 4. Character is -.

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

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

  • C is an operand. Return "C". Advance idx to 6.
  • State: idx = 5 → 6, 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, returns = "D"

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

  • Postfix combination: "C" + "D" + "-" = "CD-"
  • Return "CD-".
  • State: combined = "CD-"

Step 10: Back in the * call. Left = "AB+", Right = "CD-".

  • Postfix combination: "AB+" + "CD-" + "" = "AB+CD-"
  • Return "AB+CD-*".

Final Result: "AB+CD-*"

Algorithm

  1. Initialize a global index pointer idx = 0.
  2. 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 (in postfix).
    • Recursively call solve() to get the right operand string (in postfix).
    • Return left + right + operator.
  3. 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
        string left = solve(preExp);
        string right = solve(preExp);

        // Postfix: operands first, then operator
        return left + right + ch;
    }

    string preToPost(string pre_exp) {
        idx = 0;
        return solve(pre_exp);
    }
};
class Solution:
    def preToPost(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()

            # Postfix: operands first, then operator
            return left + right + ch

        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
        String left = solve(preExp);
        String right = solve(preExp);

        // Postfix: operands first, then operator
        return left + right + ch;
    }

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

Complexity Analysis

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

The recursive parsing visits each character exactly once, which is O(N). However, at every operator node we perform string concatenation of left + right + operator. In languages like Java and Python, each concatenation creates a new string by copying all characters. For a deeply nested expression (e.g., +A+B+C...), the intermediate strings grow progressively, and 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 prefix expression. In the worst case (a completely skewed expression like +A+B+C+D...), the depth is O(N/2) = O(N). Each recursive call uses O(1) stack frame space, giving O(N) total call stack usage.

Why This Approach Is Not Efficient

The recursive approach works correctly but has practical drawbacks:

  1. Recursion depth risk: For a deeply nested prefix expression, the recursion depth can reach O(N/2). While the constraint here is small (N ≤ 100), this approach does not scale well. In Python, the default recursion limit is 1,000, and in competitive programming, expressions can be much longer. A stack overflow would crash the program.

  2. Function call overhead: Each character triggers a function call with its associated overhead — saving/restoring registers, allocating stack frames, and managing return addresses. For an iterative approach, each character is handled in a simple loop iteration, which is significantly faster in practice.

  3. String concatenation cost: At each operator node, a new string is created by copying the left and right operand strings plus the operator. For degenerate expressions, this leads to O(N²) total character copies.

Key insight: By scanning the prefix expression from right to left and using an explicit stack, we can build the postfix expression iteratively. Operands encountered during the right-to-left scan are pushed onto the stack, and operators combine them in postfix order — all without recursion.

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

Intuition

The same right-to-left scanning technique that works for prefix-to-infix conversion works here too, with one small change in how we combine operands.

When scanning a prefix expression from right to left:

  • Operands appear first (they are at the rightmost positions).
  • Operators appear later and need two operands each.

This naturally maps to a stack: push operands, and when you see an operator, pop two operands and combine them.

The only difference from infix conversion is the combination step:

  • Infix: "(" + left + operator + right + ")"
  • Postfix: left + right + operator

Think of it like assembling instructions for a calculator that processes numbers left-to-right and applies operations as they appear. The stack holds partial results (sub-expressions in postfix form), and each operator pops two partial results, merges them with the operator at the end, and pushes the merged result back.

The algorithm is elegant and efficient: one pass through the string, one stack, no recursion.

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 in postfix order: "C" + "D" + "-" = "CD-".
  • Push "CD-" back onto the stack.
  • Stack: ["CD-"]

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

  • Push "B" onto the stack.
  • Stack: ["CD-", "B"]

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

  • Push "A" onto the stack.
  • Stack: ["CD-", "B", "A"]

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

  • Pop two operands: first pop = "A" (left), second pop = "B" (right).
  • Combine in postfix: "A" + "B" + "+" = "AB+".
  • Push "AB+" back.
  • Stack: ["CD-", "AB+"]

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

  • Pop two operands: first pop = "AB+" (left), second pop = "CD-" (right).
  • Combine in postfix: "AB+" + "CD-" + "" = "AB+CD-".
  • Push result.
  • Stack: ["AB+CD-*"]

Result: The stack has one element: "AB+CD-*".

Prefix to Postfix — Stack-Based Right-to-Left Conversion — Watch how scanning from right to left and combining operands in postfix order (left + right + operator) converts the prefix expression to postfix in a single pass.

Algorithm

  1. Create an empty stack of strings.
  2. 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 + right + operator (postfix order — no parentheses needed).
      d. Push this combined string back onto the stack.
  3. After processing all characters, the stack contains exactly one element — the postfix expression. Return it.

Code

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

class Solution {
public:
    string preToPost(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 in postfix order
                string left = st.top(); st.pop();
                string right = st.top(); st.pop();
                st.push(left + right + ch);
            }
        }

        return st.top();
    }
};
class Solution:
    def preToPost(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 in postfix order
                left = stack.pop()
                right = stack.pop()
                stack.append(left + right + ch)

        return stack[-1]
import java.util.Stack;

class Solution {
    String preToPost(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 in postfix order
                String left = stack.pop();
                String right = stack.pop();
                stack.push(left + right + ch);
            }
        }

        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 with constant-time stack operations (push and pop). Each character is involved in at most one push and one pop. The loop itself is O(N).

Note: Similar to prefix-to-infix, string concatenation at operator steps can lead to O(N²) total character copies in the worst case. However, with N ≤ 100 in this problem, this is negligible. For the core algorithm (excluding string building), the work 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). The intermediate strings stored on the stack together occupy O(N) total space. No recursion is used, so there is no call stack overhead.