Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Infix to Prefix Conversion

MEDIUMProblemSolveExternal Links

Description

You are given a string s representing a mathematical expression written in infix notation — the familiar format where an operator sits between its two operands (e.g., a + b).

Your task is to convert this expression into its equivalent prefix notation (also called Polish notation), where the operator comes before its two operands (e.g., + a b).

Operator Precedence and Associativity:

  • ^ (exponentiation) has the highest precedence and is evaluated right to left.
  • * and / (multiplication and division) have the next highest precedence and are evaluated left to right.
  • + and - (addition and subtraction) have the lowest precedence and are evaluated left to right.

Parentheses () can override the default precedence, forcing a sub-expression to be evaluated first.

Operands are single characters: lowercase letters (a–z), uppercase letters (A–Z), or digits (0–9).

Examples

Example 1

Input: s = "a*(b+c)/d"

Output: "/*a+bcd"

Explanation: First evaluate the parenthesized sub-expression: b + c becomes +bc in prefix. Now the expression looks like a * (+bc) / d. Since * and / have the same precedence and are left-associative, we evaluate left to right: a * (+bc) becomes *a+bc. Finally, (*a+bc) / d becomes /*a+bcd.

Example 2

Input: s = "(a-b/c)*(a/k-l)"

Output: "*-a/bc-/akl"

Explanation: Inside the first group: b/c becomes /bc, then a - /bc becomes -a/bc. Inside the second group: a/k becomes /ak, then /ak - l becomes -/akl. Finally, multiply the two groups: (-a/bc) * (-/akl) becomes *-a/bc-/akl.

Example 3

Input: s = "a+b*c"

Output: "+a*bc"

Explanation: Multiplication has higher precedence than addition, so b*c is evaluated first: *bc. Then a + (*bc) becomes +a*bc. No parentheses are needed because precedence already dictates the correct grouping.

Constraints

  • 3 ≤ s.length ≤ 5 × 10^3
  • Each character s[i] is one of:
    • An operand: a–z, A–Z, 0–9
    • An operator: +, -, *, /, ^
    • A parenthesis: ( or )
  • The input expression is always a valid, fully-formed infix expression.

Editorial

Brute Force

Intuition

Think about how you would evaluate an expression by hand. You would look at the entire expression, figure out which operation should be performed last (the one with the lowest precedence that is not sheltered inside parentheses), and then split the expression at that point into a left part, an operator, and a right part.

For prefix notation, the operator goes first, followed by the prefix form of the left part, then the prefix form of the right part. We can apply this idea recursively until we reach single-character operands, which are already in prefix form.

The key challenge is finding the main operator — the operator that would be evaluated last. We scan the expression while tracking how deep we are inside parentheses. Any operator at depth zero is a candidate. Among all depth-zero operators, we pick the one with the lowest precedence. If there are ties, we pick the rightmost one for left-associative operators (+, -, *, /) and the leftmost one for right-associative operators (^), because that matches the order of evaluation.

Step-by-Step Explanation

Let's trace through with s = "a*(b+c)/d":

Step 1: Start with the full expression "a*(b+c)/d". We need to find the main operator — the lowest-precedence operator outside all parentheses.

Step 2: Scan left to right, tracking parenthesis depth:

  • a at depth 0 → operand, skip
  • * at depth 0 → operator, precedence 2. Record as candidate: * at index 1, bestPrec = 2
  • ( → depth becomes 1
  • b at depth 1 → inside parens, skip
  • + at depth 1 → inside parens, skip
  • c at depth 1 → inside parens, skip
  • ) → depth becomes 0
  • / at depth 0 → operator, precedence 2. Same precedence as *, left-associative, so pick the rightmost: update to / at index 7, bestPrec = 2
  • d at depth 0 → operand, skip

Main operator: / at index 7.

Step 3: Split the expression:

  • Left operand: "a*(b+c)" (indices 0 to 6)
  • Operator: /
  • Right operand: "d" (index 8)

Step 4: Recursively convert the right operand "d". It's a single character → return "d".

Step 5: Recursively convert the left operand "a*(b+c)":

  • Scan for the main operator at depth 0:
    • a → operand
    • * at depth 0 → precedence 2. Record: * at index 1
    • ( through ) → everything inside parens is skipped
  • Main operator: * at index 1
  • Left: "a" → single character → "a"
  • Right: "(b+c)" → strip outer parens → "b+c"
    • Scan "b+c": main operator is + at position 1 (only operator at depth 0)
    • Left: "b" → "b"
    • Right: "c" → "c"
    • Result: "+" + "b" + "c" = "+bc"
  • Result: "*" + "a" + "+bc" = "*a+bc"

Step 6: Combine everything with the main operator /:

  • Result: "/" + "*a+bc" + "d" = "/*a+bcd"

Final answer: "/*a+bcd"

Algorithm

  1. If the expression is a single operand, return it directly.
  2. If the expression is fully wrapped in a matching pair of parentheses, strip them and recurse on the inner expression.
  3. Scan the expression from left to right while maintaining a parenthesis depth counter:
    • Increment depth on (; decrement on ).
    • For every operator at depth 0, compare its precedence with the current best:
      • For left-associative operators (+, -, *, /): update the main operator if precedence is ≤ the best so far (picks the rightmost among equals).
      • For right-associative operators (^): update only if precedence is strictly < the best so far (picks the leftmost among equals).
  4. Split the expression at the main operator into left and right sub-expressions.
  5. Recursively convert both sub-expressions to prefix.
  6. Return: operator + prefix(left) + prefix(right).

Code

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

class Solution {
public:
    string infixToPrefix(string s) {
        return convert(s, 0, s.length() - 1);
    }

private:
    string convert(const string& s, int lo, int hi) {
        // Strip matching outer parentheses
        while (lo <= hi && s[lo] == '(' && findMatch(s, lo) == hi) {
            lo++;
            hi--;
        }
        // Base case: single operand
        if (lo == hi) return string(1, s[lo]);

        // Find main operator (lowest precedence at depth 0)
        int mainPos = -1, mainPrec = INT_MAX, depth = 0;
        for (int i = lo; i <= hi; i++) {
            if (s[i] == '(') depth++;
            else if (s[i] == ')') depth--;
            else if (depth == 0 && isOp(s[i])) {
                int p = prec(s[i]);
                if (s[i] == '^') {
                    if (p < mainPrec) {
                        mainPrec = p;
                        mainPos = i;
                    }
                } else {
                    if (p <= mainPrec) {
                        mainPrec = p;
                        mainPos = i;
                    }
                }
            }
        }

        string left = convert(s, lo, mainPos - 1);
        string right = convert(s, mainPos + 1, hi);
        return string(1, s[mainPos]) + left + right;
    }

    int prec(char c) {
        if (c == '+' || c == '-') return 1;
        if (c == '*' || c == '/') return 2;
        if (c == '^') return 3;
        return 0;
    }

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

    int findMatch(const string& s, int i) {
        int depth = 0;
        for (int j = i; j < (int)s.length(); j++) {
            if (s[j] == '(') depth++;
            else if (s[j] == ')') depth--;
            if (depth == 0) return j;
        }
        return -1;
    }
};
class Solution:
    def infixToPrefix(self, s: str) -> str:
        return self._convert(s, 0, len(s) - 1)

    def _convert(self, s, lo, hi):
        # Strip matching outer parentheses
        while lo <= hi and s[lo] == '(' and self._findMatch(s, lo) == hi:
            lo += 1
            hi -= 1

        # Base case: single operand
        if lo == hi:
            return s[lo]

        # Find main operator (lowest precedence at depth 0)
        main_pos = -1
        main_prec = float('inf')
        depth = 0

        for i in range(lo, hi + 1):
            if s[i] == '(':
                depth += 1
            elif s[i] == ')':
                depth -= 1
            elif depth == 0 and s[i] in '+-*/^':
                p = self._prec(s[i])
                if s[i] == '^':  # right-associative: pick leftmost
                    if p < main_prec:
                        main_prec = p
                        main_pos = i
                else:  # left-associative: pick rightmost
                    if p <= main_prec:
                        main_prec = p
                        main_pos = i

        left = self._convert(s, lo, main_pos - 1)
        right = self._convert(s, main_pos + 1, hi)
        return s[main_pos] + left + right

    def _prec(self, c):
        if c in '+-': return 1
        if c in '*/': return 2
        if c == '^': return 3
        return 0

    def _findMatch(self, s, i):
        depth = 0
        for j in range(i, len(s)):
            if s[j] == '(': depth += 1
            elif s[j] == ')': depth -= 1
            if depth == 0: return j
        return -1
class Solution {
    public String infixToPrefix(String s) {
        return convert(s, 0, s.length() - 1);
    }

    private String convert(String s, int lo, int hi) {
        // Strip matching outer parentheses
        while (lo <= hi && s.charAt(lo) == '(' && findMatch(s, lo) == hi) {
            lo++;
            hi--;
        }
        // Base case: single operand
        if (lo == hi) return "" + s.charAt(lo);

        // Find main operator (lowest precedence at depth 0)
        int mainPos = -1, mainPrec = Integer.MAX_VALUE, depth = 0;
        for (int i = lo; i <= hi; i++) {
            char c = s.charAt(i);
            if (c == '(') depth++;
            else if (c == ')') depth--;
            else if (depth == 0 && isOp(c)) {
                int p = prec(c);
                if (c == '^') {
                    if (p < mainPrec) {
                        mainPrec = p;
                        mainPos = i;
                    }
                } else {
                    if (p <= mainPrec) {
                        mainPrec = p;
                        mainPos = i;
                    }
                }
            }
        }

        String left = convert(s, lo, mainPos - 1);
        String right = convert(s, mainPos + 1, hi);
        return "" + s.charAt(mainPos) + left + right;
    }

    private int prec(char c) {
        if (c == '+' || c == '-') return 1;
        if (c == '*' || c == '/') return 2;
        if (c == '^') return 3;
        return 0;
    }

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

    private int findMatch(String s, int i) {
        int depth = 0;
        for (int j = i; j < s.length(); j++) {
            if (s.charAt(j) == '(') depth++;
            else if (s.charAt(j) == ')') depth--;
            if (depth == 0) return j;
        }
        return -1;
    }
}

Complexity Analysis

Time Complexity: O(n²)

At each level of recursion, we scan the sub-expression to find the main operator — that scan is O(n) in the worst case. For a chain of operators at the same precedence level (e.g., a+b+c+...+z), the main operator is always the rightmost, so each recursive call removes only one operand and one operator from the right side. This produces O(n) levels of recursion, each scanning O(n) characters, yielding O(n²) total work.

Space Complexity: O(n)

The recursion stack can be O(n) deep in the worst case (a long chain of same-precedence operators). Additionally, the intermediate prefix strings consume O(n) space through string concatenation.

Why This Approach Is Not Efficient

The recursive approach scans the entire sub-expression at every level of recursion to locate the main operator. With n up to 5,000, the worst case produces roughly 25 million character comparisons — this is sluggish and risks exceeding tight time limits.

The root cause of the inefficiency is repeated scanning: we traverse large portions of the string over and over as we recurse. Each recursive call doesn't remember anything about the positions of operators or parentheses from previous calls.

A better strategy would process every character exactly once, making decisions on the fly. A stack-based approach does precisely this: it reads each character once, uses a stack to enforce operator precedence, and builds the result in a single O(n) pass.

Optimal Approach - Stack-Based Conversion

Intuition

Imagine you are reading a book backwards — from the last word to the first. Each time you encounter a "noun" (operand), you write it down immediately. Each time you encounter a "verb" (operator), you don't write it yet — instead, you place it on a stack of pending verbs. Why? Because you need to wait and see if the next verb has higher priority (precedence). Higher-priority verbs should appear closer to their operands in the final result.

This is exactly how the stack-based algorithm works:

  1. Scan the infix expression from right to left.
  2. Operands go directly into the result string.
  3. Right parenthesis ) gets pushed onto the stack as a boundary marker (since we're reading right-to-left, ) is encountered before ().
  4. Left parenthesis ( triggers popping: pop all operators from the stack into the result until we hit the matching ), then discard that ).
  5. Operators are compared with the stack top:
    • Pop operators that have strictly higher precedence.
    • For operators with equal precedence: pop only if the incoming operator is right-associative (^). Left-associative operators (+, -, *, /) are not popped on equal precedence — this preserves the correct left-to-right evaluation order.
    • Then push the current operator.
  6. After processing all characters, pop all remaining operators from the stack into the result.
  7. Reverse the result — since we scanned right-to-left and appended in that order, the result is backwards.

The entire process visits each character once, giving us O(n) time.

Step-by-Step Explanation

Let's trace through with s = "a*(b+c)/d":

Characters by index: a(0), *(1), ((2), b(3), +(4), c(5), )(6), /(7), d(8)

We scan from index 8 down to 0.

Step 1: Initialize an empty stack and an empty result string.

  • Result: "", Stack: []

Step 2: Read d (index 8). Operand → append to result.

  • Result: "d", Stack: []

Step 3: Read / (index 7). Operator with precedence 2. Stack is empty → push.

  • Result: "d", Stack: [/]

Step 4: Read ) (index 6). Boundary marker → push.

  • Result: "d", Stack: [/, )]

Step 5: Read c (index 5). Operand → append to result.

  • Result: "dc", Stack: [/, )]

Step 6: Read + (index 4). Operator, but stack top is ) (boundary). Cannot pop past boundary → push.

  • Result: "dc", Stack: [/, ), +]

Step 7: Read b (index 3). Operand → append to result.

  • Result: "dcb", Stack: [/, ), +]

Step 8: Read ( (index 2). Pop operators until ): pop + → append to result. Discard ) from stack.

  • Result: "dcb+", Stack: [/]

Step 9: Read * (index 1). Operator with precedence 2. Stack top is / with precedence 2. Same precedence, * is left-associative → do NOT pop. Push *.

  • Result: "dcb+", Stack: [/, *]

Step 10: Read a (index 0). Operand → append to result.

  • Result: "dcb+a", Stack: [/, *]

Step 11: Input exhausted. Pop all remaining: pop * → result "dcb+a*". Pop / → result "dcb+a*/".

  • Result: "dcb+a*/", Stack: []

Step 12: Reverse the result: "dcb+a*/" → "/*a+bcd".

Final answer: "/*a+bcd"

Stack-Based Infix to Prefix — Right-to-Left Scan — Watch how we scan the expression from right to left, pushing operators onto a stack and appending operands to the result, then reverse the result to get the prefix expression.

Algorithm

  1. Initialize an empty stack and an empty result string.
  2. Scan the expression from right to left. For each character:
    • Operand (letter or digit): append to result.
    • Right parenthesis ): push onto stack.
    • Left parenthesis (: pop operators from the stack into the result until a ) is found, then discard the ).
    • Operator: while the stack top is an operator (not )) with strictly higher precedence, OR same precedence and the incoming operator is right-associative (^), pop the stack top into the result. Then push the current operator.
  3. After scanning all characters, pop all remaining operators from the stack into the result.
  4. Reverse the result string to obtain the prefix expression.

Code

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

class Solution {
public:
    string infixToPrefix(string s) {
        string result = "";
        stack<char> st;

        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s[i];

            if (isalnum(c)) {
                result += c;
            }
            else if (c == ')') {
                st.push(c);
            }
            else if (c == '(') {
                while (!st.empty() && st.top() != ')') {
                    result += st.top();
                    st.pop();
                }
                if (!st.empty()) st.pop(); // discard ')'
            }
            else { // operator
                while (!st.empty() && st.top() != ')' &&
                       isOperator(st.top()) &&
                       (precedence(st.top()) > precedence(c) ||
                        (precedence(st.top()) == precedence(c) &&
                         c == '^'))) {
                    result += st.top();
                    st.pop();
                }
                st.push(c);
            }
        }

        while (!st.empty()) {
            result += st.top();
            st.pop();
        }

        reverse(result.begin(), result.end());
        return result;
    }

private:
    int precedence(char c) {
        if (c == '+' || c == '-') return 1;
        if (c == '*' || c == '/') return 2;
        if (c == '^') return 3;
        return -1;
    }

    bool isOperator(char c) {
        return c == '+' || c == '-' || c == '*' ||
               c == '/' || c == '^';
    }
};
class Solution:
    def infixToPrefix(self, s: str) -> str:
        result = []
        stack = []

        def precedence(c):
            if c in '+-': return 1
            if c in '*/': return 2
            if c == '^': return 3
            return -1

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

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

            if c.isalnum():
                result.append(c)
            elif c == ')':
                stack.append(c)
            elif c == '(':
                while stack and stack[-1] != ')':
                    result.append(stack.pop())
                if stack:
                    stack.pop()  # discard ')'
            else:
                while (stack and stack[-1] != ')' and
                       is_operator(stack[-1]) and
                       (precedence(stack[-1]) > precedence(c) or
                        (precedence(stack[-1]) == precedence(c)
                         and c == '^'))):
                    result.append(stack.pop())
                stack.append(c)

        while stack:
            result.append(stack.pop())

        return ''.join(reversed(result))
import java.util.Stack;

class Solution {
    public String infixToPrefix(String s) {
        StringBuilder result = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);

            if (Character.isLetterOrDigit(c)) {
                result.append(c);
            }
            else if (c == ')') {
                stack.push(c);
            }
            else if (c == '(') {
                while (!stack.isEmpty() && stack.peek() != ')') {
                    result.append(stack.pop());
                }
                if (!stack.isEmpty()) stack.pop();
            }
            else {
                while (!stack.isEmpty() && stack.peek() != ')' &&
                       isOperator(stack.peek()) &&
                       (precedence(stack.peek()) > precedence(c) ||
                        (precedence(stack.peek()) == precedence(c)
                         && c == '^'))) {
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }

        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.reverse().toString();
    }

    private int precedence(char c) {
        if (c == '+' || c == '-') return 1;
        if (c == '*' || c == '/') return 2;
        if (c == '^') return 3;
        return -1;
    }

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

Complexity Analysis

Time Complexity: O(n)

We scan the expression once from right to left — that is O(n) iterations. Each character is pushed onto the stack at most once and popped at most once, so the total number of stack operations across all iterations is also O(n). The final reversal is O(n). Overall: O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The stack can hold up to O(n) operators in the worst case (e.g., an expression with deeply nested parentheses). The result string also takes O(n) space. Total auxiliary space: O(n).