Infix to Postfix Conversion Using Stack in DSA C#

Mental Model

We change a math expression from normal form (infix) to a form easy for computers to calculate (postfix) by using a stack to hold operators until they can be placed in the right order.

Analogy: Imagine you are cooking and have ingredients (numbers) and spices (operators). You put spices on a shelf (stack) until it's their turn to be added to the dish (postfix expression) in the correct order.

Infix:  A + B * C
Stack:  [empty]
Postfix: [empty]

Dry Run Walkthrough

Input: infix expression: A + B * C

Goal: Convert the infix expression 'A + B * C' to postfix notation 'A B C * +'.

Step 1: Read 'A', an operand, add to postfix

Postfix: A
Stack: []

Why: Operands go directly to the output

Step 2: Read '+', an operator, push to stack

Postfix: A
Stack: [+]

Why: Operators wait in stack until we know their order

Step 3: Read 'B', an operand, add to postfix

Postfix: A B
Stack: [+]

Why: Operands go directly to output

Step 4: Read '*', an operator, has higher precedence than '+', push to stack

Postfix: A B
Stack: [+ *]

Why: Higher precedence operators go on top of lower ones

Step 5: Read 'C', an operand, add to postfix

Postfix: A B C
Stack: [+ *]

Why: Operands go directly to output

Step 6: End of expression, pop '*' from stack to postfix

Postfix: A B C *
Stack: [+]

Why: Pop remaining operators in correct order

Step 7: Pop '+' from stack to postfix

Postfix: A B C * +
Stack: []

Why: Finish by emptying stack

Result:

Postfix: A B C * +

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class InfixToPostfixConverter
{
    public static string Convert(string infix)
    {
        Stack<char> stack = new Stack<char>();
        string postfix = "";

        int Precedence(char op)
        {
            return op switch
            {
                '+' or '-' => 1,
                '*' or '/' => 2,
                '^' => 3,
                _ => 0
            };
        }

        bool IsOperator(char c) => c == '+' || c == '-' || c == '*' || c == '/' || c == '^';

        foreach (char c in infix)
        {
            if (char.IsLetterOrDigit(c))
            {
                postfix += c + " "; // add operands directly
            }
            else if (c == '(')
            {
                stack.Push(c); // push '(' to stack
            }
            else if (c == ')')
            {
                while (stack.Count > 0 && stack.Peek() != '(')
                {
                    postfix += stack.Pop() + " "; // pop until '('
                }
                if (stack.Count > 0 && stack.Peek() == '(')
                    stack.Pop(); // remove '('
            }
            else if (IsOperator(c))
            {
                while (stack.Count > 0 && Precedence(stack.Peek()) > Precedence(c))
                {
                    postfix += stack.Pop() + " "; // pop higher precedence
                }
                stack.Push(c); // push current operator
            }
        }

        while (stack.Count > 0)
        {
            postfix += stack.Pop() + " "; // pop remaining operators
        }

        return postfix.Trim();
    }

    static void Main()
    {
        string infix = "A+B*C";
        string postfix = Convert(infix);
        Console.WriteLine(postfix);
    }
}

if (char.IsLetterOrDigit(c))

Add operands directly to postfix output

else if (c == '(')

Push '(' to stack to mark start of sub-expression

else if (c == ')')

Pop from stack to postfix until '(' found, then remove '('

else if (IsOperator(c))

Pop operators with higher precedence before pushing current operator

while (stack.Count > 0)

Pop all remaining operators to postfix after processing input

Output

A B C * +

Complexity Analysis

Time: O(n) because we scan the input expression once and each operator is pushed and popped at most once

Space: O(n) because the stack and output string can grow proportional to input size

vs Alternative: Compared to evaluating infix directly with recursion or multiple passes, using a stack for postfix conversion is simpler and more efficient

Edge Cases

Empty input string

Returns empty postfix string without error

DSA C#

foreach (char c in infix)

Expression with parentheses only

Correctly handles '(' and ')' by pushing and popping stack

DSA C#

else if (c == ')')

Expression with multiple operators of same precedence

Operators popped in correct order respecting precedence and associativity

DSA C#

while (stack.Count > 0 && Precedence(stack.Peek()) > Precedence(c))

When to Use This Pattern

When you need to convert a math expression from human-readable form to a form easy for computers to evaluate, use the stack-based infix to postfix conversion pattern.

Common Mistakes

Mistake: Not popping operators with higher or equal precedence before pushing a new operator
Fix: Add a loop to pop from stack while top operator has higher precedence

Mistake: Ignoring parentheses and not popping until '('
Fix: Handle '(' by pushing and ')' by popping until '(' is found

Summary

Converts infix expressions to postfix using a stack to reorder operators.

Use when you want to simplify expression evaluation by computers.

The key is to push operators on a stack and pop them in order of precedence.

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