Infix to Postfix Conversion Using Stack in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a character is an operator.

DSA C

int isOperator(char c) {
    return (c == '+' || c == '-' || c == '*' || c == [1]);
}

Drag options to blanks, or click blank then click option'

A/

B%

C^

D&

Attempts:

3 left

💡 Hint

Common Mistakes

Using a non-operator symbol like '&' or '%'.

Forgetting to include '/' as an operator.

The division operator '/' is a common operator in infix expressions and must be checked.

2fill in blank

medium

Complete the code to return precedence of operators.

DSA C

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

Drag options to blanks, or click blank then click option'

A-

B/

C^

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' or '-' which have lower precedence.

Using '^' which is not handled here.

Division '/' has the same precedence as multiplication '*', so it should return 2.

3fill in blank

hard

Fix the error in the stack push function to correctly add an element.

DSA C

void push(char stack[], int *top, char value) {
    stack[++[1]] = value;
}

Drag options to blanks, or click blank then click option'

A*top

Btop

C&top

D(*top)

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'top' directly increments the pointer, not the value.

Using '&top' is incorrect as it gives address of pointer.

We must increment the value pointed by top, so ++*top is correct.

4fill in blank

hard

Fill in the blank to correctly pop an element from the stack.

DSA C

char pop(char stack[], int *top) {
    return stack[[1]--];
}

Drag options to blanks, or click blank then click option'

A*top

Btop

C(*top)

D&top

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'top' without dereferencing causes errors.

Using '&top' is incorrect as it is address of pointer.

(*top)-- correctly returns the top element and then decrements the top index.

5fill in blank

hard

Fill both blanks to correctly convert infix to postfix expression.

DSA C

void infixToPostfix(char* infix, char* postfix) {
    char stack[100];
    int top = -1, i = 0, k = 0;
    while (infix[i] != '\0') {
        char c = infix[i];
        if (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) {
            postfix[k++] = c;
        } else if (c == '(') {
            stack[++top] = c;
        } else if (c == ')') {
            while (top != -1 && stack[top] != () {
                postfix[k++] = stack[top--];
            }
            top--;
        } else if (isOperator(c)) {
            while (top != -1 && precedence(stack[top]) >= [1]) {
                postfix[k++] = stack[top--];
            }
            stack[++top] = [2];
        }
        i++;
    }
    while (top != -1) {
        postfix[k++] = stack[top--];
    }
    postfix[k] = '\0';
}

Drag options to blanks, or click blank then click option'

A(

Bc

Ctop

Dprecedence(c)

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong character for '(' in popping loop.

Comparing precedence with stack top instead of current operator.

Pushing wrong character onto stack.

When encountering ')', pop until '(' is found (blank 1 = '(').The operator to push is c (blank 3 = c).

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