Infix to Postfix Conversion Using Stack in DSA C

Mental Model

We use a stack to reorder operators so that expressions can be evaluated without parentheses.

Analogy: Imagine a chef stacking ingredients in order to prepare a sandwich without needing to look back at the recipe each time.

Infix expression: A + B * C
Stack: empty
Postfix output: empty

Dry Run Walkthrough

Input: infix: A + B * C

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

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

Output: A
Stack: empty

Why: Operands go directly to output

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

Output: A
Stack: +

Why: Operators are stored to decide order later

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

Output: A B
Stack: +

Why: Operands go directly to output

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

Output: A B
Stack: + -> *

Why: Higher precedence operators go on top

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

Output: A B C
Stack: + -> *

Why: Operands go directly to output

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

Output: A B C *
Stack: +

Why: Pop remaining operators in order

Step 7: Pop '+' from stack to output

Output: A B C * +
Stack: empty

Why: Finish by emptying stack

Result:

Output: A B C * +
Stack: empty

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define MAX 100

char stack[MAX];
int top = -1;

void push(char c) {
    if (top < MAX - 1) {
        stack[++top] = c;
    }
}

char pop() {
    if (top >= 0) {
        return stack[top--];
    }
    return '\0';
}

char peek() {
    if (top >= 0) {
        return stack[top];
    }
    return '\0';
}

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

void infixToPostfix(char* infix, char* postfix) {
    int i = 0, j = 0;
    char c;
    while ((c = infix[i++]) != '\0') {
        if (isalnum(c)) {
            postfix[j++] = c; // add operand to output
        } else {
            while (top != -1 && precedence(peek()) >= precedence(c)) {
                postfix[j++] = pop(); // pop higher or equal precedence operators
            }
            push(c); // push current operator
        }
    }
    while (top != -1) {
        postfix[j++] = pop(); // pop remaining operators
    }
    postfix[j] = '\0';
}

int main() {
    char infix[] = "A+B*C";
    char postfix[MAX];
    infixToPostfix(infix, postfix);
    printf("%s\n", postfix);
    return 0;
}

if (isalnum(c)) { postfix[j++] = c; // add operand to output }

Add operands directly to output

while (top != -1 && precedence(peek()) >= precedence(c)) { postfix[j++] = pop(); // pop higher or equal precedence operators }

Pop operators with higher or equal precedence before pushing new operator

push(c); // push current operator

Push current operator onto stack

while (top != -1) { postfix[j++] = pop(); // pop remaining operators }

Pop all remaining operators after processing input

Output

ABC*+

Complexity Analysis

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

Space: O(n) for the stack and output arrays to hold operators and result

vs Alternative: Compared to evaluating infix directly with parentheses, this method simplifies evaluation by reordering operators first, avoiding repeated precedence checks during evaluation

Edge Cases

Empty input string

Output is empty, no operators pushed

DSA C

while ((c = infix[i++]) != '\0')

Expression with single operand

Operand goes directly to output, stack remains empty

DSA C

if (isalnum(c)) {
    postfix[j++] = c;

Expression with multiple operators of same precedence

Operators popped in correct order due to precedence check

DSA C

while (top != -1 && precedence(peek()) >= precedence(c))

When to Use This Pattern

When you see expressions with operators and parentheses and need to evaluate or convert them, use the stack-based infix to postfix conversion to simplify processing order.

Common Mistakes

Mistake: Not popping operators with equal precedence before pushing new operator
Fix: Use >= in precedence comparison to pop operators of equal or higher precedence

Mistake: Adding operators directly to output instead of using stack
Fix: Always push operators to stack and pop based on precedence rules

Summary

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

Use when you want to evaluate or simplify expressions without parentheses.

The key insight is to use a stack to hold operators and pop them based on precedence rules.

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