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 want to understand 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 infix) {
    Stack<char> stack = new Stack<char>();
    StringBuilder postfix = new StringBuilder();
    foreach (char ch in infix) {
        if (char.IsLetterOrDigit(ch)) {
            postfix.Append(ch);
        } else if (ch == '(') {
            stack.Push(ch);
        } else if (ch == ')') {
            while (stack.Count > 0 && stack.Peek() != '(') {
                postfix.Append(stack.Pop());
            }
            stack.Pop();
        } else {
            while (stack.Count > 0 && Precedence(ch) <= Precedence(stack.Peek())) {
                postfix.Append(stack.Pop());
            }
            stack.Push(ch);
        }
    }
    while (stack.Count > 0) {
        postfix.Append(stack.Pop());
    }
    return postfix.ToString();
}

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One main loop that goes through each character of the input expression once.
• How many times: Exactly once per character, so n times if the expression length is n.
• Inside this loop, some stack operations (push/pop) happen, but each character is pushed and popped at most once.

How Execution Grows With Input

As the input expression gets longer, the number of steps grows roughly in direct proportion to its length.

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

Pattern observation: The total work grows linearly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows in a straight line with the size of the input expression.

Common Mistake

[X] Wrong: "Because there are nested loops inside, the time must be quadratic O(n²)."

[OK] Correct: The inner loops only pop from the stack, and each character is pushed and popped once, so total operations stay proportional to n, not n squared.

Interview Connect

Understanding this linear time complexity helps you explain why stack-based expression parsing is efficient and practical in real coding problems.

Self-Check

"What if the input expression included multi-digit numbers or spaces? 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 their precedence

B. To store the final postfix expression

C. To reverse the infix expression

D. To count the number of operands

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 tasks

   The postfix expression is built separately, and the stack is not used to store operands or reverse the expression.

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 [OK]

Common Mistakes:

• Thinking stack stores operands
• Confusing stack with output storage
• Assuming stack reverses expression

2. Which of the following C# code snippets correctly pushes an operator onto a stack named operatorStack?

easy

A. operatorStack.Push('+');

B. operatorStack.Add('+');

C. operatorStack.Insert('+');

D. operatorStack.Append('+');

Solution

1. Step 1: Recall stack method to add elements

   In C#, the method to add an element to a stack is Push().

2. Step 2: Verify other methods are invalid for Stack

   Add(), Insert(), and Append() are not valid methods for the Stack class.

3. Final Answer:

   operatorStack.Push('+'); -> Option A

4. Quick Check:

   Stack push method = Push() [OK]

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

Common Mistakes:

• Using Add() instead of Push()
• Confusing List methods with Stack methods
• Trying to use Append() on Stack

3. What is the postfix expression output for the infix expression A + B * C using standard operator precedence?

medium

A. *ABC+

B. AB+C*

C. ABC*+

D. A+BC*

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 respecting precedence

   Postfix places operands first, then operator: B C * then A +, resulting in ABC*+.

3. Final Answer:

   ABC*+ -> Option C

4. Quick Check:

   Multiplication before addition = ABC*+ [OK]

Hint: Multiply before add in postfix [OK]

Common Mistakes:

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

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

Stack<char> stack = new Stack<char>();
string infix = "A+B*C";
string postfix = "";
foreach (char ch in infix)
{
  if (char.IsLetter(ch))
    postfix += ch;
  else
    stack.Push(ch);
}
while (stack.Count > 0)
  postfix += stack.Pop();
Console.WriteLine(postfix);

medium

A. Operands are not added to postfix

B. Operators are pushed without checking precedence

C. Stack is not initialized

D. Postfix string is not printed

Solution

1. Step 1: Analyze operator handling in code

   The code pushes operators directly onto the stack without checking precedence or popping higher precedence operators first.

2. Step 2: Understand impact on postfix output

   This causes incorrect postfix order because operator precedence is ignored.

3. Final Answer:

   Operators are pushed without checking precedence -> Option B

4. Quick Check:

   Missing precedence check = B [OK]

Hint: Always check operator precedence before pushing [OK]

Common Mistakes:

• Ignoring operator precedence rules
• Assuming stack auto-sorts operators
• Not popping operators when needed

5. Convert the infix expression (A+B)*(C-D)/E to postfix using stack-based conversion. 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: Handle parentheses and operator precedence

   Parentheses force A+B and C-D to be evaluated first, then multiply results, then divide by E.

2. Step 2: Convert stepwise to postfix

   A+B becomes AB+, C-D becomes CD-, then multiply: AB+CD-*, then divide by E: AB+CD-*E/.

3. Final Answer:

   AB+CD-*E/ -> Option D

4. Quick Check:

   Parentheses first, then multiply, then divide = AB+CD-*E/ [OK]

Hint: Process parentheses first, then operators by precedence [OK]

Common Mistakes:

• Ignoring parentheses order
• Mixing operator precedence
• Placing division before multiplication