Infix to Postfix Conversion Using Stack in DSA C# - Build from Scratch

Infix to Postfix Conversion Using Stack

📖 Scenario: You are building a simple calculator that converts mathematical expressions written in the usual way (called infix notation) into a form easier for computers to evaluate (called postfix notation).For example, the expression (A + B) * C in infix becomes AB+C* in postfix.

🎯 Goal: Build a program that converts an infix expression string into its postfix form using a stack data structure.

📋 What You'll Learn

Create a string variable called infix with the exact value "A+B*(C-D)".

Create a stack of characters called stack to help with the conversion.

Write a method called IsOperator that returns true if a character is one of + - * / ( ).

Write a method called Precedence that returns an integer priority for operators: + and - have precedence 1, * and / have precedence 2, and parentheses have precedence 0.

Write the core logic to convert the infix expression to postfix using the stack and the helper methods.

Print the final postfix expression exactly as a string.

💡 Why This Matters

🌍 Real World

Converting infix to postfix is a key step in calculators and compilers to evaluate mathematical expressions efficiently.

💼 Career

Understanding stack-based expression parsing is important for software developers working on interpreters, compilers, and calculators.

1

Create the Infix Expression Variable

Create a string variable called infix and set it to the exact value "A+B*(C-D)".

DSA C#

# Create a string variable called infix with value "A+B*(C-D)"
# Your code here

Hint

Use string infix = "A+B*(C-D)"; to create the variable.

2

Create the Stack and Helper Methods

Create a stack of characters called stack. Then write two methods: IsOperator(char c) that returns true if c is one of '+', '-', '*', '/', '(', ')', and Precedence(char c) that returns 1 for '+' and '-', 2 for '*' and '/', and 0 for others.

DSA C#

string infix = "A+B*(C-D)";
// Create a stack of characters called stack
// Write IsOperator(char c) method
// Write Precedence(char c) method
# Your code here

Hint

Use Stack<char> stack = new Stack<char>(); to create the stack.

Write IsOperator to check if a character is an operator or parenthesis.

Write Precedence to assign priority numbers to operators.

3

Convert Infix to Postfix Using Stack

Write the core logic to convert the infix expression to postfix notation. Use a string variable postfix to build the result. Use the stack, IsOperator, and Precedence methods. Iterate over each character in infix. If the character is not an operator, add it to postfix. If it is an operator, use the stack to manage operator precedence and parentheses as per the infix to postfix rules.

DSA C#

using System.Collections.Generic;

string infix = "A+B*(C-D)";
Stack stack = new Stack();

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

int Precedence(char c)
{
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}

// Write code to convert infix to postfix
// Use a string variable postfix to store the result
// Your code here

Hint

Use a loop to check each character in infix.

If it is a letter, add it to postfix.

If it is an operator, use the stack to manage precedence and parentheses.

4

Print the Postfix Expression

Print the postfix string variable to display the converted postfix expression.

DSA C#

using System.Collections.Generic;

string infix = "A+B*(C-D)";
Stack stack = new Stack();

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

int Precedence(char c)
{
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;
}

string postfix = "";

foreach (char c in infix)
{
    if (!IsOperator(c))
    {
        postfix += c;
    }
    else
    {
        if (c == '(')
        {
            stack.Push(c);
        }
        else if (c == ')')
        {
            while (stack.Count > 0 && stack.Peek() != '(')
            {
                postfix += stack.Pop();
            }
            if (stack.Count > 0 && stack.Peek() == '(')
            {
                stack.Pop();
            }
        }
        else
        {
            while (stack.Count > 0 && Precedence(stack.Peek()) >= Precedence(c))
            {
                postfix += stack.Pop();
            }
            stack.Push(c);
        }
    }
}

while (stack.Count > 0)
{
    postfix += stack.Pop();
}

// Print the postfix expression
# Your code here

Hint

Use Console.WriteLine(postfix); to print the result.

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