Infix to Postfix Conversion Using Stack in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Postfix Conversion for Simple Expression

What is the output of the postfix conversion for the infix expression a+b*c using a stack?

DSA Go

func infixToPostfix(expression string) string {
    precedence := map[rune]int{'+' : 1, '-' : 1, '*' : 2, '/' : 2}
    stack := []rune{}
    result := ""
    for _, ch := range expression {
        if (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') {
            result += string(ch)
        } else {
            for len(stack) > 0 && precedence[stack[len(stack)-1]] >= precedence[ch] {
                result += string(stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            stack = append(stack, ch)
        }
    }
    for len(stack) > 0 {
        result += string(stack[len(stack)-1])
        stack = stack[:len(stack)-1]
    }
    return result
}

fmt.Println(infixToPostfix("a+b*c"))

A a+bc*

B abc*+

C abc+*

D ab+c*

💡 Hint

Remember that multiplication (*) has higher precedence than addition (+).

In infix expression 'a+b*c', multiplication has higher precedence, so 'b*c' is evaluated first, then added to 'a'. The postfix is 'abc*+'.

❓ Predict Output

intermediate

Postfix Conversion Output with Parentheses

What is the output of the postfix conversion for the infix expression (a+b)*c using a stack?

DSA Go

func infixToPostfix(expression string) string {
    precedence := map[rune]int{'+' : 1, '-' : 1, '*' : 2, '/' : 2}
    stack := []rune{}
    result := ""
    for _, ch := range expression {
        if (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') {
            result += string(ch)
        } else if ch == '(' {
            stack = append(stack, ch)
        } else if ch == ')' {
            for len(stack) > 0 && stack[len(stack)-1] != '(' {
                result += string(stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            stack = stack[:len(stack)-1] // pop '('
        } else {
            for len(stack) > 0 && stack[len(stack)-1] != '(' && precedence[stack[len(stack)-1]] >= precedence[ch] {
                result += string(stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            stack = append(stack, ch)
        }
    }
    for len(stack) > 0 {
        result += string(stack[len(stack)-1])
        stack = stack[:len(stack)-1]
    }
    return result
}

fmt.Println(infixToPostfix("(a+b)*c"))

A abc*+

B a+bc*

C ab+c*

D ab+*c

💡 Hint

Parentheses change the order of operations; evaluate inside parentheses first.

The expression '(a+b)*c' means add 'a' and 'b' first, then multiply by 'c'. The postfix is 'ab+c*'.

🧠 Conceptual

advanced

Understanding Operator Precedence in Postfix Conversion

Which operator precedence rule is correctly applied in the infix to postfix conversion using a stack?

A Operators with higher precedence on the stack are popped before pushing a new operator with lower precedence.

B Operators with lower precedence are popped from the stack before pushing higher precedence operators.

C Operators are popped from the stack only when the stack is empty.

D Operators with higher precedence are pushed on the stack and popped only after lower precedence operators.

💡 Hint

Think about when to pop operators from the stack based on their precedence compared to the incoming operator.

When a new operator arrives, operators on the stack with higher or equal precedence are popped first to maintain correct order.

🔧 Debug

advanced

Identify the Error in Postfix Conversion Code

Given the following code snippet for infix to postfix conversion, what error will it cause when processing the expression a*b/c? func infixToPostfix(expression string) string { precedence := map[rune]int{'+' : 1, '-' : 1, '*' : 2, '/' : 2} stack := []rune{} result := "" for _, ch := range expression { if (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') { result += string(ch) } else { for len(stack) > 0 && precedence[stack[len(stack)-1]] > precedence[ch] { result += string(stack[len(stack)-1]) stack = stack[:len(stack)-1] } stack = append(stack, ch) } } for len(stack) > 0 { result += string(stack[len(stack)-1]) stack = stack[:len(stack)-1] } return result } fmt.Println(infixToPostfix("a*b/c"))

A The output will be 'abc/*' which is incorrect due to wrong precedence handling.

B The code will cause a runtime panic due to empty stack access.

C The output will be 'ab*c/' which is correct.

D The output will be 'ab*/c' which is incorrect due to wrong operator order.

💡 Hint

Check the comparison operator in the while loop condition for popping from stack.

The code uses '>' instead of '>=' in precedence comparison, so it fails to pop operators with equal precedence (like '*' and '/'), causing output 'abc/*' instead of correct 'ab*c/'.

🚀 Application

expert

Postfix Expression Length After Conversion

Given the infix expression (a+b)*(c-d)/e, how many characters will the resulting postfix expression have after conversion using a stack?

A 10

B 8

C 7

D 9

💡 Hint

Count operands and operators carefully after conversion.

The postfix expression is 'ab+cd-*e/', which has 9 characters (5 operands: a,b,c,d,e and 4 operators: +,-,*,/).

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: Identify what is stored in stack

   Operands are directly added to the output, while operators are pushed to the stack to decide their order in postfix.

3. Final Answer:

   To temporarily hold operators and manage their precedence -> Option A

4. Quick Check:

   Stack holds operators for precedence [OK]

Hint: Stack holds operators, output holds operands [OK]

Common Mistakes:

• Thinking stack stores operands
• Confusing stack role with output
• Ignoring operator precedence

2. Which of the following Go code snippets correctly initializes an empty stack for infix to postfix conversion?

easy

A. var stack []rune = []rune{}

B. stack := make([]int, 0)

C. stack := []string{0}

D. var stack []int = nil

Solution

1. Step 1: Identify correct stack type for operators

   Operators are characters, so stack should be a slice of runes (characters) initialized empty.

2. Step 2: Check initialization correctness

   var stack []rune = []rune{} initializes an empty rune slice correctly. stack := make([]int, 0) uses int slice, not suitable. stack := []string{0} has syntax error (cannot use int 0 as string). var stack []int = nil is nil slice, which can cause runtime errors.

3. Final Answer:

   var stack []rune = []rune{} -> Option A

4. Quick Check:

   Empty rune slice for operator stack [OK]

Hint: Use rune slice for operator stack [OK]

Common Mistakes:

• Using int slice for operators
• Initializing with wrong type
• Using nil slice without initialization

3. What is the postfix expression output by the following Go code snippet for input "a+b*c"?

infix := "a+b*c"
// Assume correct infix to postfix conversion function called here
postfix := InfixToPostfix(infix)
fmt.Println(postfix)

medium

A. "a+bc*"

B. "ab+c*"

C. "abc*+"

D. "*abc+"

Solution

1. Step 1: Analyze operator precedence in expression

   Multiplication (*) has higher precedence than addition (+), so 'b*c' is evaluated before adding 'a'.

2. Step 2: Convert infix to postfix step-by-step

   Postfix is formed as 'a' 'b' 'c' '*' '+', which is "abc*+".

3. Final Answer:

   "abc*+" -> Option C

4. Quick Check:

   Multiplication before addition = "abc*+" [OK]

Hint: Multiply before add means * goes before + in postfix [OK]

Common Mistakes:

• Ignoring operator precedence
• Placing + before * in postfix
• Confusing operand order

4. Given this Go function snippet for infix to postfix conversion, what is the bug?

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

// InfixToPostfix function uses precedence(op) to compare operators
// but outputs incorrect postfix for input "a+b^c"

medium

A. Precedence function returns 0 for non-operators causing errors

B. Precedence function returns int instead of float

C. Precedence values for '+' and '-' are swapped

D. Precedence function does not handle '^' operator

Solution

1. Step 1: Check if all operators are handled

   The function handles '+', '-', '*', '/' but misses '^' (exponent) operator which is common in infix expressions.

2. Step 2: Understand impact on output

   If input contains '^', missing precedence causes wrong order in postfix output.

3. Final Answer:

   Precedence function does not handle '^' operator -> Option D

4. Quick Check:

   Missing '^' causes wrong postfix [OK]

Hint: Include all operators in precedence function [OK]

Common Mistakes:

• Ignoring missing operators
• Assuming 0 precedence is error
• Confusing precedence values

5. How would you modify the infix to postfix algorithm to correctly handle parentheses in the expression (a+b)*c?

hard

A. Ignore parentheses and treat them as operands

B. Push '(' onto stack and pop operators until '(' when ')' is found

C. Remove all parentheses before conversion

D. Treat '(' as higher precedence operator and never pop it

Solution

1. Step 1: Understand role of parentheses in infix

   Parentheses change normal precedence by grouping expressions to evaluate first.

2. Step 2: Modify stack operations for parentheses

   Push '(' onto stack when encountered. When ')' is found, pop operators until '(' is popped, discarding both parentheses.

3. Final Answer:

   Push '(' onto stack and pop operators until '(' when ')' is found -> Option B

4. Quick Check:

   Parentheses control stack push/pop [OK]

Hint: Push '(' and pop until '(' on ')' [OK]

Common Mistakes:

• Ignoring parentheses in algorithm
• Treating parentheses as operands
• Not popping until '(' on ')'