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 program that converts mathematical expressions written in the usual way (called infix notation) into a form that computers find easier to evaluate (called postfix notation).For example, the infix expression (A + B) * C becomes AB+C* in postfix.

🎯 Goal: Build a program that reads an infix expression and converts it to postfix using a stack data structure.

📋 What You'll Learn

Create a stack to hold operators

Use a precedence function to compare operator priorities

Process the infix expression character by character

Output the correct postfix expression

💡 Why This Matters

🌍 Real World

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

💼 Career

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

1

Create the stack and input expression

Create a character array called infix initialized with the string "(A+B)*C". Also, declare a character array called stack of size 20 and an integer variable called top initialized to -1.

DSA C

# Declare the infix expression, stack array, and top variable
# Your code here

Hint

Use char infix[] = "(A+B)*C"; to store the expression.

Use char stack[20]; to create the stack.

Initialize top to -1 to indicate the stack is empty.

2

Create the precedence function

Write a function called precedence that takes a character op and returns an integer representing its precedence: return 2 for '*' and '/', 1 for '+' and '-', and 0 for any other character.

DSA C

char infix[] = "(A+B)*C";
char stack[20];
int top = -1;

// Write the precedence function below
// Your code here

Hint

Use if and else if to check the operator.

Return the correct precedence number for each operator.

3

Implement the infix to postfix conversion logic

Write a for loop to iterate over each character in infix. Use variables i for index and j for postfix array index. For each character, if it is an uppercase letter, add it to postfix. If it is '(', push it to stack. If it is ')', pop from stack to postfix until '(' is found. For operators, pop from stack to postfix while the top of stack has higher or equal precedence, then push the current operator. Declare postfix as a character array of size 20 and initialize j to 0.

DSA C

char infix[] = "(A+B)*C";
char stack[20];
int top = -1;

int precedence(char op) {
    if (op == '*' || op == '/')
        return 2;
    else if (op == '+' || op == '-')
        return 1;
    else
        return 0;
}

// Declare postfix array and index j
// Write the for loop to convert infix to postfix
// Your code here

Hint

Use a loop to check each character in infix.

Use conditions to handle letters, parentheses, and operators.

Push and pop from stack as needed.

Build the postfix string step by step.

4

Print the postfix expression

Write a printf statement to print the string postfix with the message "Postfix expression: %s\n".

DSA C

char infix[] = "(A+B)*C";
char stack[20];
int top = -1;

int precedence(char op) {
    if (op == '*' || op == '/')
        return 2;
    else if (op == '+' || op == '-')
        return 1;
    else
        return 0;
}

char postfix[20];
int j = 0;

for (int i = 0; infix[i] != '\0'; i++) {
    char ch = infix[i];
    if (ch >= 'A' && ch = precedence(ch)) {
            postfix[j++] = stack[top--];
        }
        stack[++top] = ch;
    }
}
while (top != -1) {
    postfix[j++] = stack[top--];
}
postfix[j] = '\0';

// Print the postfix expression below
// Your code here

Hint

Use printf("Postfix expression: %s\n", postfix); to display 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 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