Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Infix to Postfix Using Stack

MEDIUMProblemSolveExternal Links

Description

You are given a string representing a mathematical expression written in infix notation — the familiar format where the operator sits between its two operands, like a + b or x * y.

Your task is to convert this expression into postfix notation (also called Reverse Polish Notation), where the operator comes after its operands: a b + or x y *.

Why does postfix matter? In infix notation, we need parentheses and precedence rules to avoid ambiguity. The expression a + b * c could mean (a + b) * c or a + (b * c) — we rely on the convention that * binds tighter than +. In postfix, there is zero ambiguity: a b c * + unambiguously means "multiply b and c first, then add a." This makes postfix ideal for evaluation by computers and stack-based calculators.

Precedence and associativity rules you must follow:

  • ^ (exponentiation) has the highest precedence and is right-to-left associative. So a ^ b ^ c means a ^ (b ^ c).
  • * and / have the next highest precedence and are left-to-right associative. So a * b / c means (a * b) / c.
  • + and - have the lowest precedence and are left-to-right associative.
  • Parentheses override all precedence rules — expressions inside parentheses are evaluated first.

Examples

Example 1

Input: s = "a+b*c"

Output: "abc*+"

Explanation: Multiplication has higher precedence than addition, so b * c is evaluated first. In postfix, b * c becomes bc*. Then a + (bc*) becomes abc*+. The operator * appears before + in the output because it binds tighter.

Example 2

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

Output: "abc+*d/"

Explanation: Parentheses force b + c to be evaluated first, producing bc+. Then a * (bc+) yields abc+. Finally, (abc+) / d yields abc+*d/. The parentheses overrode the default left-to-right evaluation of * and /.

Example 3

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

Output: "ab+cd+*"

Explanation: Both parenthesized groups are evaluated first. (a+b) becomes ab+. (c+d) becomes cd+. Then ab+ * cd+ becomes ab+cd+*. The multiplication comes last in the output because it operates on the results of both additions.

Constraints

  • 1 ≤ s.length ≤ 5 × 10^3
  • s[i] can be an operand (a–z, A–Z, 0–9), an operator (+, -, *, /, ^), or a parenthesis ( (, ) )
  • The input expression is always a valid infix expression
  • Expected Time Complexity: O(n)
  • Expected Auxiliary Space: O(n)

Editorial

Brute Force

Intuition

Think about how you would convert an expression by hand. You would look at the entire expression, identify which operator is applied last (the one with the lowest precedence, not inside any parentheses), and place it at the very end of the postfix output. Then you would repeat the same process for the left and right sub-expressions.

For example, in a + b * c, the last operation is addition (lower precedence than multiplication). So the postfix result is: [postfix of left side] + [postfix of right side] + the operator. The left side is just 'a', and the right side 'bc' converts to 'bc'. Combining: a + bc* + '+' gives abc*+.

This is essentially a recursive divide-and-conquer approach: find the root operator (the one applied last), split the expression, recursively convert each half, and concatenate the results with the operator at the end.

To find which operator is applied last, scan the expression for the operator with the lowest precedence that is not inside any parentheses. For operators with equal precedence and left-to-right associativity (+, -, *, /), the rightmost one is applied last. For right-to-left associativity (^), the leftmost one is applied last.

Step-by-Step Explanation

Let us trace through with s = "a+b*c":

Step 1: Call convert("a+b*c"). Scan for the lowest precedence operator at parenthesis depth 0.

  • '+' at position 1 has precedence 1.
  • '*' at position 3 has precedence 2.
  • '+' has lower precedence, so it is the root — the last operation applied.

Step 2: Split at '+': left = "a", right = "b*c", operator = '+'.

Step 3: Recursively convert the left side: convert("a").

  • "a" is a single operand (base case). Return "a".

Step 4: Recursively convert the right side: convert("b*c").

  • Scan for lowest precedence operator: only '*' at position 1 (precedence 2).

Step 5: Split at '': left = "b", right = "c", operator = ''.

Step 6: convert("b") = "b" (base case). convert("c") = "c" (base case).

Step 7: Combine right subtree result: "b" + "c" + "" = "bc". Return "bc*".

Step 8: Combine root result: "a" + "bc*" + "+" = "abc*+". Return "abc*+".

Result: "abc*+"

Recursive Parsing — Divide and Conquer on "a+b*c" — Watch how the expression is recursively split at the lowest-precedence operator, each sub-expression converts to postfix, and the results combine bottom-up.

Algorithm

  1. Base case: If the expression is a single operand (letter or digit), return it directly.
  2. Strip outer parentheses: If the entire expression is wrapped in matching parentheses, remove them and recurse on the inner expression.
  3. Find the split operator: Scan the expression left to right, tracking parenthesis depth. Among all operators at depth 0, find the one with the lowest precedence. For left-to-right associative operators (+, -, *, /), take the rightmost one at the lowest precedence level. For right-to-left associative operators (^), take the leftmost.
  4. Split: Divide the expression into left sub-expression (before the split operator), the operator itself, and the right sub-expression (after it).
  5. Recurse and combine: Recursively convert the left and right sub-expressions. The postfix result is: left_postfix + right_postfix + operator.

Code

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

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

    string convert(string s) {
        // Strip matching outer parentheses
        if (s.size() >= 2 && s[0] == '(') {
            int depth = 0;
            bool wrapsAll = true;
            for (int i = 0; i < (int)s.size(); i++) {
                if (s[i] == '(') depth++;
                else if (s[i] == ')') depth--;
                if (depth == 0 && i < (int)s.size() - 1) {
                    wrapsAll = false;
                    break;
                }
            }
            if (wrapsAll) return convert(s.substr(1, s.size() - 2));
        }

        // Base case: single operand
        if (s.size() == 1) return s;

        // Find the lowest-precedence operator at depth 0
        int minPrec = INT_MAX, splitPos = -1, depth = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] == '(') depth++;
            else if (s[i] == ')') depth--;
            else if (depth == 0 && isOperator(s[i])) {
                int p = precedence(s[i]);
                // Left-assoc: rightmost lowest (<=)
                // Right-assoc (^): leftmost lowest (<)
                if (s[i] == '^') {
                    if (p < minPrec) { minPrec = p; splitPos = i; }
                } else {
                    if (p <= minPrec) { minPrec = p; splitPos = i; }
                }
            }
        }

        string left = convert(s.substr(0, splitPos));
        string right = convert(s.substr(splitPos + 1));
        return left + right + s[splitPos];
    }

public:
    string infixToPostfix(string s) {
        return convert(s);
    }
};
class Solution:
    def infixToPostfix(self, s):
        return self._convert(s)

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

    def _is_operator(self, c):
        return c in '+-*/^'

    def _convert(self, s):
        # Strip matching outer parentheses
        if len(s) >= 2 and s[0] == '(':
            depth = 0
            wraps_all = True
            for i in range(len(s)):
                if s[i] == '(': depth += 1
                elif s[i] == ')': depth -= 1
                if depth == 0 and i < len(s) - 1:
                    wraps_all = False
                    break
            if wraps_all:
                return self._convert(s[1:-1])

        # Base case: single operand
        if len(s) == 1:
            return s

        # Find the lowest-precedence operator at depth 0
        min_prec = float('inf')
        split_pos = -1
        depth = 0

        for i in range(len(s)):
            if s[i] == '(':
                depth += 1
            elif s[i] == ')':
                depth -= 1
            elif depth == 0 and self._is_operator(s[i]):
                p = self._precedence(s[i])
                # Left-assoc: rightmost lowest (<=)
                # Right-assoc (^): leftmost lowest (<)
                if s[i] == '^':
                    if p < min_prec:
                        min_prec = p
                        split_pos = i
                else:
                    if p <= min_prec:
                        min_prec = p
                        split_pos = i

        left = self._convert(s[:split_pos])
        right = self._convert(s[split_pos + 1:])
        return left + right + s[split_pos]
class Solution {
    private int precedence(char c) {
        if (c == '^') return 3;
        if (c == '*' || c == '/') return 2;
        if (c == '+' || c == '-') return 1;
        return 0;
    }

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

    private String convert(String s) {
        // Strip matching outer parentheses
        if (s.length() >= 2 && s.charAt(0) == '(') {
            int depth = 0;
            boolean wrapsAll = true;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') depth++;
                else if (s.charAt(i) == ')') depth--;
                if (depth == 0 && i < s.length() - 1) {
                    wrapsAll = false;
                    break;
                }
            }
            if (wrapsAll) return convert(s.substring(1, s.length() - 1));
        }

        // Base case: single operand
        if (s.length() == 1) return s;

        // Find the lowest-precedence operator at depth 0
        int minPrec = Integer.MAX_VALUE;
        int splitPos = -1;
        int depth = 0;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') depth++;
            else if (c == ')') depth--;
            else if (depth == 0 && isOperator(c)) {
                int p = precedence(c);
                if (c == '^') {
                    if (p < minPrec) { minPrec = p; splitPos = i; }
                } else {
                    if (p <= minPrec) { minPrec = p; splitPos = i; }
                }
            }
        }

        String left = convert(s.substring(0, splitPos));
        String right = convert(s.substring(splitPos + 1));
        return left + right + s.charAt(splitPos);
    }

    public String infixToPostfix(String s) {
        return convert(s);
    }
}

Complexity Analysis

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

Each recursive call scans the entire sub-expression to find the split operator, which costs O(k) where k is the length of the sub-expression. For a left-skewed expression like a + b + c + d + ... (all same-precedence, left-associative operators), the rightmost operator is chosen as the split point, leaving a left sub-expression of length n - 2 and a right sub-expression of length 1. This gives a recurrence T(n) = T(n-2) + O(n), which solves to O(n²).

For balanced expressions with parentheses, the recursion depth is O(log n), giving O(n log n). But in the worst case, it is O(n²).

Space Complexity: O(n)

The recursion stack can go O(n) deep in the worst case (one operator per level). Additionally, creating substrings at each level uses O(n) space. Total auxiliary space: O(n).

Why This Approach Is Not Efficient

The recursive approach scans the expression from scratch at every level of recursion to find the split operator. For an expression with n characters and k operators, we perform k recursive splits, each requiring an O(n) scan. In the worst case (all same-precedence operators like a + b + c + d + ...), this gives O(n²) total work.

With n up to 5000, O(n²) means up to 25 million character comparisons — workable but slow. The deeper issue is that we are re-scanning the same characters repeatedly. Each recursive call re-examines parts of the string that previous calls already processed.

Key insight: we do not need to see the entire expression before deciding what to output. If we process characters one by one from left to right, we can use a stack to remember pending operators. When we encounter a new operator, we compare its precedence with operators already on the stack. Operators with higher or equal precedence (respecting associativity) should be output before the new one is pushed. This single-pass approach eliminates all redundant scanning and achieves O(n) time.

Optimal Approach - Stack-Based Conversion (Shunting Yard)

Intuition

Imagine you are a traffic controller at a road junction. Cars (operands) drive straight through to the output lane. But trucks (operators) must wait at a holding area (the stack) because they need to yield to other trucks that arrived earlier and have higher priority (precedence).

When a new truck arrives, you check the holding area. Any truck already waiting that has higher priority (or equal priority with left-to-right rules) gets sent to the output lane before the new truck enters the holding area. If the new truck has higher priority than everything waiting, it simply enters the holding area.

Parentheses are like traffic barriers: an opening parenthesis '(' creates a new section in the holding area. No truck can pass through this barrier. When a closing parenthesis ')' arrives, all trucks between it and the matching '(' are flushed to the output lane, and the barrier is removed.

At the end, any trucks still in the holding area are sent to the output lane in order.

This is the Shunting Yard Algorithm, invented by Edsger Dijkstra. It processes each character exactly once and uses the stack to enforce correct operator ordering — achieving O(n) time.

Step-by-Step Explanation

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

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

  • Stack: [], Result: ""

Step 2: Read 'a'. It is an operand — append directly to result.

  • Stack: [], Result: "a"

Step 3: Read ''. It is an operator. Stack is empty, so push '' onto the stack.

  • Stack: ['*'], Result: "a"

Step 4: Read '('. It is an opening parenthesis — push onto stack. It acts as a barrier.

  • Stack: ['*', '('], Result: "a"

Step 5: Read 'b'. Operand — append to result.

  • Stack: ['*', '('], Result: "ab"

Step 6: Read '+'. Operator. Top of stack is '(' which blocks popping. Push '+' above the barrier.

  • Stack: ['*', '(', '+'], Result: "ab"

Step 7: Read 'c'. Operand — append to result.

  • Stack: ['*', '(', '+'], Result: "abc"

Step 8: Read ')'. Closing parenthesis. Pop operators until we find '(': pop '+' and append to result. Then discard '('.

  • Stack: ['*'], Result: "abc+"

Step 9: Read '/'. Operator with precedence 2. Top of stack is '' with precedence 2. Same precedence and left-to-right associative, so pop '' first and append to result. Then push '/'.

  • Stack: ['/'], Result: "abc+*"

Step 10: Read 'd'. Operand — append to result.

  • Stack: ['/'], Result: "abc+*d"

Step 11: End of input. Pop all remaining operators from the stack: pop '/' and append.

  • Stack: [], Result: "abc+*d/"

Result: "abc+*d/"

Shunting Yard Algorithm — Converting "a*(b+c)/d" — Watch how operands pass straight to the result while operators are held in a stack, popped based on precedence rules, and parentheses create barriers that flush operators when matched.

Algorithm

  1. Initialize an empty stack (for operators) and an empty result string.
  2. For each character c in the input string:
    • If c is an operand (letter or digit): append it to the result.
    • If c is '(': push it onto the stack.
    • If c is ')': pop operators from the stack and append each to the result until '(' is found. Discard the '('.
    • If c is an operator: while the stack is not empty, and the top is not '(', and either the top operator has higher precedence than c, or the top has equal precedence and c is left-associative — pop the top and append to result. Then push c onto the stack.
  3. After processing all characters, pop any remaining operators from the stack and append them to the result.
  4. Return the result string.

Code

class Solution {
public:
    // Returns the precedence of an operator
    int precedence(char c) {
        if (c == '^') return 3;
        if (c == '*' || c == '/') return 2;
        if (c == '+' || c == '-') return 1;
        return -1;
    }

    string infixToPostfix(string s) {
        stack<char> st;
        string result;

        for (int i = 0; i < (int)s.length(); i++) {
            char c = s[i];

            // Operand: append directly to result
            if ((c >= 'a' && c <= 'z') ||
                (c >= 'A' && c <= 'Z') ||
                (c >= '0' && c <= '9')) {
                result += c;
            }
            // Opening parenthesis: push as barrier
            else if (c == '(') {
                st.push(c);
            }
            // Closing parenthesis: pop until matching '('
            else if (c == ')') {
                while (!st.empty() && st.top() != '(') {
                    result += st.top();
                    st.pop();
                }
                st.pop(); // Remove '('
            }
            // Operator: compare precedence with stack top
            else {
                while (!st.empty() && st.top() != '(' &&
                       (precedence(st.top()) > precedence(c) ||
                        (precedence(st.top()) == precedence(c) && c != '^'))) {
                    result += st.top();
                    st.pop();
                }
                st.push(c);
            }
        }

        // Pop all remaining operators
        while (!st.empty()) {
            result += st.top();
            st.pop();
        }

        return result;
    }
};
class Solution:
    def infixToPostfix(self, s):
        def precedence(c):
            if c == '^': return 3
            if c in '*/': return 2
            if c in '+-': return 1
            return -1

        stack = []
        result = []

        for c in s:
            # Operand: append directly to result
            if c.isalnum():
                result.append(c)
            # Opening parenthesis: push as barrier
            elif c == '(':
                stack.append(c)
            # Closing parenthesis: pop until matching '('
            elif c == ')':
                while stack and stack[-1] != '(':
                    result.append(stack.pop())
                stack.pop()  # Remove '('
            # Operator: compare precedence with stack top
            else:
                while (stack and stack[-1] != '(' and
                       (precedence(stack[-1]) > precedence(c) or
                        (precedence(stack[-1]) == precedence(c) and c != '^'))):
                    result.append(stack.pop())
                stack.append(c)

        # Pop all remaining operators
        while stack:
            result.append(stack.pop())

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

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

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            // Operand: append directly to result
            if (Character.isLetterOrDigit(c)) {
                result.append(c);
            }
            // Opening parenthesis: push as barrier
            else if (c == '(') {
                stack.push(c);
            }
            // Closing parenthesis: pop until matching '('
            else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                stack.pop(); // Remove '('
            }
            // Operator: compare precedence with stack top
            else {
                while (!stack.isEmpty() && stack.peek() != '(' &&
                       (precedence(stack.peek()) > precedence(c) ||
                        (precedence(stack.peek()) == precedence(c) && c != '^'))) {
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }

        // Pop all remaining operators
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }
}

Complexity Analysis

Time Complexity: O(n)

We make a single pass through the n characters of the input. Each character is processed in O(1) time for the initial check. For operators, the while loop may pop multiple elements from the stack, but every operator is pushed at most once and popped at most once across the entire execution. By amortized analysis, the total number of push and pop operations over all characters is at most 2n. Therefore the total work is O(n).

Space Complexity: O(n)

In the worst case, all characters could be operators or parentheses pushed onto the stack simultaneously (e.g., deeply nested parentheses like '((((a+b))))'). The result string also uses O(n) space. Total auxiliary space: O(n).