Infix to Postfix Conversion Using Stack in DSA Java - Time & Space Complexity

Time Complexity: Infix to Postfix Conversion Using Stack

O(n)

Understanding Time Complexity

We want to know how the time needed to convert an infix expression to postfix grows as the expression gets longer.

How does the number of steps change when the input expression size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public String infixToPostfix(String expr) {
    Stack<Character> stack = new Stack<>();
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < expr.length(); i++) {
        char c = expr.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());
            stack.pop();
        } else {
            while (!stack.isEmpty() && precedence(c) < precedence(stack.peek()))
                result.append(stack.pop());
            stack.push(c);
        }
    }
    while (!stack.isEmpty())
        result.append(stack.pop());
    return result.toString();
}

private int precedence(char ch) {
    switch (ch) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        case '^': return 3;
    }
    return -1;
}
    

This code converts an infix expression (like "a+b*c") to postfix form (like "abc*+") using a stack to manage operators.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop over each character of the input expression.
• How many times: Exactly once for each character in the input string (n times).
• Inside the loop, stack operations (push/pop) happen but each operator is pushed and popped at most once.

How Execution Grows With Input

As the input expression length grows, the number of steps grows roughly the same way.

Input Size (n)	Approx. Operations
10	About 10 main loop steps plus some stack operations
100	About 100 main loop steps plus stack operations proportional to 100
1000	About 1000 main loop steps plus stack operations proportional to 1000

Pattern observation: The total steps increase linearly with input size; doubling input roughly doubles work.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows directly in proportion to the length of the expression.

Common Mistake

[X] Wrong: "Because of nested while loops inside the main loop, the time complexity is quadratic O(n²)."

[OK] Correct: Each operator is pushed and popped only once, so the inner loops do not multiply the total steps beyond linear growth.

Interview Connect

Understanding this linear time complexity helps you explain how efficient stack-based expression parsing is, a common skill in coding interviews.

Self-Check

"What if the input expression included multi-character operands instead of single characters? How would the time complexity change?"

Practice

1. What is the main purpose of using a stack in converting an infix expression to postfix?

easy

A. To temporarily hold operators and manage their precedence

B. To store operands permanently

C. To reverse the order of operands

D. To count the number of operators

Solution

1. Step 1: Understand the role of stack in infix to postfix

   The stack is used to hold operators temporarily while processing the expression to respect operator precedence and associativity.

2. Step 2: Differentiate stack use from other data structures

   Operands are output immediately, not stored in stack. Stack is not used for counting or reversing operands.

3. Final Answer:

   To temporarily hold operators and manage their precedence -> Option A

4. Quick Check:

   Stack holds operators = A [OK]

Hint: Stack holds operators to manage precedence during conversion [OK]

Common Mistakes:

• Thinking stack stores operands
• Confusing stack with queue
• Believing stack reverses operands

2. Which of the following is the correct way to push an operator onto the stack in Java?

easy

A. stack.push(operator);

B. stack.insert(operator);

C. stack.add(operator);

D. stack.put(operator);

Solution

1. Step 1: Recall Java Stack method for adding elements

   Java's Stack class uses the push() method to add elements to the top of the stack.

2. Step 2: Identify incorrect methods

   Methods add(), insert(), and put() are not standard for Stack push operation in Java.

3. Final Answer:

   stack.push(operator); -> Option A

4. Quick Check:

   Use push() to add to stack [OK]

Hint: Use push() to add elements to Java stack [OK]

Common Mistakes:

• Using add() instead of push()
• Using non-existent methods like insert()
• Confusing stack with other collections

3. What is the postfix expression for the infix expression A + B * C?

medium

A. AB+C*

B. ABC*+

C. A+BC*

D. *ABC+

Solution

1. Step 1: Apply operator precedence in infix to postfix

   Multiplication (*) has higher precedence than addition (+), so B*C is evaluated first.

2. Step 2: Convert expression step-by-step

   Postfix: operands B and C followed by *, then operand A followed by + gives "ABC*+".

3. Final Answer:

   ABC*+ -> Option B

4. Quick Check:

   Multiplication before addition = ABC*+ [OK]

Hint: Multiply before add: operands then operator [OK]

Common Mistakes:

• Ignoring operator precedence
• Placing operators before operands
• Confusing postfix order

4. Given the following code snippet for infix to postfix conversion, what is the error?

if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
    while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(ch)) {
        postfix += stack.pop();
    }
    stack.push(ch);
}

medium

A. The precedence comparison should use > instead of >=

B. The stack should be checked for null before peek()

C. Operands are not handled in this snippet

D. The while loop condition is incorrect for operator associativity

Solution

1. Step 1: Understand operator associativity in infix to postfix

   For left-associative operators like '-', '+', '*', '/', pop operators with precedence >= current operator.

2. Step 2: Identify issue with while condition

   Using >= causes right-associative operators like '^' to be handled incorrectly; condition should consider associativity.

3. Final Answer:

   The while loop condition is incorrect for operator associativity -> Option D

4. Quick Check:

   Associativity affects while condition [OK]

Hint: Check operator associativity when comparing precedence [OK]

Common Mistakes:

• Ignoring operator associativity
• Not handling operands separately
• Assuming peek() can be null without check

5. Convert the infix expression (A + B) * (C - D) / E to postfix using stack. What is the correct postfix expression?

hard

A. AB+CD*E-/

B. AB+CD-E*/

C. AB+CD-*E/

D. AB+CD-*E

Solution

1. Step 1: Convert each parenthesis group to postfix

   "(A + B)" becomes "AB+" and "(C - D)" becomes "CD-".

2. Step 2: Combine with multiplication and division respecting precedence

   Multiply results: "AB+CD-*" then divide by E: "AB+CD-*E/".

3. Final Answer:

   AB+CD-*E/ -> Option C

4. Quick Check:

   Parentheses handled first, then * and / [OK]

Hint: Convert inside parentheses first, then apply operators [OK]

Common Mistakes:

• Ignoring parentheses order
• Mixing operator precedence
• Dropping operators or operands