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

Time Complexity: Infix to Postfix Conversion Using Stack

O(n)

Understanding Time Complexity

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

We want to know how the number of steps changes when the input expression size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void infixToPostfix(char* infix, char* postfix) {
    Stack s;
    initStack(&s);
    int i = 0, k = 0;
    while (infix[i] != '\0') {
        if (isOperand(infix[i])) {
            postfix[k++] = infix[i];
        } else if (infix[i] == '(') {
            push(&s, infix[i]);
        } else if (infix[i] == ')') {
            while (!isEmpty(&s) && peek(&s) != '(') {
                postfix[k++] = pop(&s);
            }
            pop(&s); // remove '('
        } else {
            while (!isEmpty(&s) && precedence(peek(&s)) > precedence(infix[i])) {
                postfix[k++] = pop(&s);
            }
            push(&s, infix[i]);
        }
        i++;
    }
    while (!isEmpty(&s)) {
        postfix[k++] = pop(&s);
    }
    postfix[k] = '\0';
}
    

This code converts an infix expression to postfix using a stack to handle operators and parentheses.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single while loop scanning each character of the input expression once.
• How many times: Once per character in the input (n times), plus popping remaining operators from the stack at the end.

How Execution Grows With Input

As the input expression length grows, the code processes each character once, with some extra steps for operators.

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

Pattern observation: The total steps grow roughly in direct proportion to the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows linearly with the length of the input expression.

Common Mistake

[X] Wrong: "The nested while loops make this algorithm quadratic time O(n²)."

[OK] Correct: Each character is pushed and popped at most once, so total operations stay proportional to n, not n squared.

Interview Connect

Understanding this linear time conversion shows you can handle stack-based parsing efficiently, a useful skill in many coding problems.

Self-Check

"What if the input expression included multi-digit numbers or variables? How would the time complexity change?"

Practice

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

easy

A. To temporarily hold operators and manage 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 conversion

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

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

   Operands are directly added to the postfix output, while operators are pushed to the stack to ensure correct order in the postfix expression.

3. Final Answer:

   To temporarily hold operators and manage precedence -> Option A

4. Quick Check:

   Stack holds operators = A [OK]

Hint: Stack holds operators to manage order and precedence [OK]

Common Mistakes:

• Thinking stack stores operands
• Assuming stack reverses operands
• Believing stack counts operators

2. Which of the following is the correct way to check if the stack is empty in C during infix to postfix conversion?

easy

A. if (stack == NULL)

B. if (top == -1)

C. if (stack->top == 0)

D. if (stack.size == 0)

Solution

1. Step 1: Understand stack implementation in C

   In array-based stack, 'top' is the index of the last pushed element. When empty, top is -1.

2. Step 2: Identify correct empty condition

   Checking if top == -1 correctly indicates the stack is empty.

3. Final Answer:

   if (top == -1) -> Option B

4. Quick Check:

   top == -1 means empty stack [OK]

Hint: Empty stack means top index is -1 [OK]

Common Mistakes:

• Checking stack pointer NULL instead of top
• Using top == 0 which means one element present
• Using struct size field incorrectly

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

medium

A. ABC*+

B. AB+C*

C. A+BC*

D. *ABC+

Solution

1. Step 1: Apply operator precedence rules

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

2. Step 2: Convert to postfix

   Postfix places operands first, then operator: B C * then A + gives ABC*+

3. Final Answer:

   ABC*+ -> Option A

4. Quick Check:

   Infix A + (B * C) = ABC*+ [OK]

Hint: Multiply before add, postfix puts operator after operands [OK]

Common Mistakes:

• Ignoring operator precedence
• Placing operators before operands
• Mixing operand order

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

if (isOperator(ch)) {
  while (!isEmpty(stack) && precedence(peek(stack)) >= precedence(ch)) {
    postfix[j++] = pop(stack);
  }
  push(stack, ch);
}

medium

A. The pop operation should not be inside the while loop

B. The push operation should be outside the if block

C. The condition should use > instead of >= for precedence comparison

D. The isEmpty function is called incorrectly

Solution

1. Step 1: Understand operator precedence handling

   For correct associativity, when precedence is equal and operator is right-associative (like '^'), we should not pop.

2. Step 2: Identify correct comparison operator

   Using >= causes popping on equal precedence, which breaks right-associativity. Using > fixes this.

3. Final Answer:

   The condition should use > instead of >= for precedence comparison -> Option C

4. Quick Check:

   Use > to handle associativity correctly [OK]

Hint: Use >, not >=, to handle right-associative operators [OK]

Common Mistakes:

• Using >= causes wrong operator order
• Pushing outside operator check
• Misusing isEmpty function

5. Convert the infix expression (A + B) * (C - D) / E to postfix notation 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

   Expression becomes (AB+) * (CD-) / E. Multiplication and division are left associative, so postfix is AB+ CD- * E /.

3. Final Answer:

   AB+CD-*E/ -> Option D

4. Quick Check:

   Postfix of (A+B)*(C-D)/E = AB+CD-*E/ [OK]

Hint: Convert parentheses first, then apply operators left to right [OK]

Common Mistakes:

• Ignoring parentheses grouping
• Mixing operator order
• Misplacing division operator