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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of postfix expression from given infix

What is the output postfix expression after converting the infix expression (A+B)*C using stack-based infix to postfix conversion?

DSA Python

def infix_to_postfix(expression):
    precedence = {'+':1, '-':1, '*':2, '/':2, '^':3}
    stack = []
    output = []
    for char in expression:
        if char.isalpha():
            output.append(char)
        elif char == '(': 
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(': 
                output.append(stack.pop())
            stack.pop()
        else:
            while stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence.get(char, 0):
                output.append(stack.pop())
            stack.append(char)
    while stack:
        output.append(stack.pop())
    return ''.join(output)

print(infix_to_postfix('(A+B)*C'))

A "AB+*C"

B "ABC+*"

C "AB+C*"

D "A+BC*"

💡 Hint

Remember that operators inside parentheses are handled first and multiplication has higher precedence than addition.

The infix expression (A+B)*C converts to postfix by first converting A+B to AB+, then multiplying by C, resulting in AB+C*.

❓ Predict Output

intermediate

Postfix output for complex infix with multiple operators

What is the postfix expression output for the infix expression A+B*C-D/E using stack-based infix to postfix conversion?

DSA Python

def infix_to_postfix(expression):
    precedence = {'+':1, '-':1, '*':2, '/':2, '^':3}
    stack = []
    output = []
    for char in expression:
        if char.isalpha():
            output.append(char)
        elif char == '(': 
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(': 
                output.append(stack.pop())
            stack.pop()
        else:
            while stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence.get(char, 0):
                output.append(stack.pop())
            stack.append(char)
    while stack:
        output.append(stack.pop())
    return ''.join(output)

print(infix_to_postfix('A+B*C-D/E'))

A "ABC*+DE/-"

B "AB+CD*-E/"

C "-/ED+*CBA"

D "AB+C*DE/-"

💡 Hint

Remember multiplication and division have higher precedence than addition and subtraction.

Multiplication and division are done before addition and subtraction, so B*C becomes BC*, D/E becomes DE/, then addition and subtraction are applied resulting in ABC*+DE/-.

🔧 Debug

advanced

Identify the error in postfix conversion code

Given the following code snippet for infix to postfix conversion, what error will it raise when run with input A+B?

DSA Python

def infix_to_postfix(expression):
    precedence = {'+':1, '-':1, '*':2, '/':2}
    stack = []
    output = []
    for char in expression:
        if char.isalpha():
            output.append(char)
        elif char == '(': 
            stack.append(char)
        elif char == ')':
            while stack[-1] != '(': 
                output.append(stack.pop())
            stack.pop()
        else:
            while stack and stack[-1] != '(' and precedence[stack[-1]] >= precedence[char]:
                output.append(stack.pop())
            stack.append(char)
    while stack:
        output.append(stack.pop())
    return ''.join(output)

print(infix_to_postfix('A+B'))

A KeyError: '('

B IndexError: list index out of range

C TypeError: '>=' not supported between instances of 'str' and 'int'

D No error, outputs 'AB+'

💡 Hint

Check how the code handles the '(' character in the stack during precedence comparison.

The code tries to get precedence[stack[-1]] without checking if stack[-1] is '('. Since '(' is not in precedence dict, KeyError is raised.

🧠 Conceptual

advanced

Operator precedence handling in infix to postfix conversion

In infix to postfix conversion using a stack, why is it important to pop operators from the stack when the incoming operator has lower or equal precedence than the operator on the stack top?

A To delay the evaluation of operators until the end of the expression

B To reverse the order of operands in the postfix expression

C To remove all operators from the stack immediately after reading them

D To ensure operators with higher precedence are applied before lower precedence ones in the postfix expression

💡 Hint

Think about how postfix expressions represent the order of operations.

Popping operators with higher or equal precedence ensures they appear before lower precedence operators in postfix, preserving correct evaluation order.

🚀 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 stack-based infix to postfix conversion?

A 7

B 9

C 11

D 13

💡 Hint

Count all operands and operators in the postfix expression 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 converting an infix expression to postfix?

easy

A. To reverse the order of operands

B. To temporarily hold operators and manage their precedence

C. To store operands permanently

D. To count the number of operators

Solution

1. Step 1: Understand the role of stack in infix to postfix

   The stack is used to hold operators temporarily while processing the expression to respect operator precedence and associativity.

2. Step 2: Clarify what the stack does not do

   The stack does not store operands permanently or reverse operands; it only manages operators.

3. Final Answer:

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

4. Quick Check:

   Stack manages operators [OK]

Hint: Stack holds operators, not operands, during conversion [OK]

Common Mistakes:

• Thinking stack stores operands
• Confusing stack role with reversing expression
• Ignoring operator precedence handling

2. Which of the following is the correct way to push an operator onto a stack in Python?

easy

A. stack.append(operator)

B. stack.push(operator)

C. stack.insert(operator)

D. stack.add(operator)

Solution

1. Step 1: Recall Python list methods for stack operations

   In Python, a list is used as a stack and the method to add an element on top is append().

2. Step 2: Identify incorrect methods

   push() and add() are not valid list methods; insert() inserts at a specific index, not top of stack.

3. Final Answer:

   stack.append(operator) -> Option A

4. Quick Check:

   Use append() to push on stack [OK]

Hint: Use append() to push items on Python list stack [OK]

Common Mistakes:

• Using push() which is not a Python list method
• Using add() which is for sets, not lists
• Using insert() incorrectly for stack push

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 respecting precedence

   Postfix places operands first, then operator: B C * for multiplication, then A and + last, so expression is A B C * +.

3. Final Answer:

   ABC*+ -> Option A

4. Quick Check:

   Multiplication before addition = 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?

def precedence(op):
    if op == '+' or op == '-':
        return 1
    if op == '*' or op == '/':
        return 2
    return 0

stack = []
postfix = ''
expr = 'A+B*C'

for char in expr:
    if char.isalpha():
        postfix += char
    else:
        while stack and precedence(stack[-1]) >= precedence(char):
            postfix += stack.pop()
        stack.append(char)

while stack:
    postfix += stack.pop()

print(postfix)

medium

A. The precedence function returns 0 for unknown operators, causing errors

B. The postfix string is not updated with operands

C. The stack is not initialized properly

D. The code does not handle parentheses in the expression

Solution

1. Step 1: Analyze code handling of operators and operands

   The code correctly appends operands and manages operator precedence using the stack.

2. Step 2: Check for missing features

   The code does not check or handle parentheses, which are common in infix expressions and affect precedence.

3. Final Answer:

   The code does not handle parentheses in the expression -> Option D

4. Quick Check:

   Missing parentheses handling [OK]

Hint: Remember to handle parentheses explicitly in infix to postfix [OK]

Common Mistakes:

• Assuming precedence 0 causes errors (it just means lowest)
• Ignoring parentheses handling
• Thinking stack initialization is wrong

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: Handle parentheses and operator precedence

   Parentheses force A+B and C-D to be evaluated first, so their postfix forms are AB+ and CD- respectively.

2. Step 2: Apply multiplication and division in order

   After parentheses, multiply the two results: AB+ CD- * then divide by E: AB+CD-* E /.

3. Final Answer:

   AB+CD-*E/ -> Option C

4. Quick Check:

   Parentheses first, then * and / = AB+CD-*E/ [OK]

Hint: Convert inside parentheses first, then apply * and / left to right [OK]

Common Mistakes:

• Ignoring parentheses order
• Mixing operator order for * and /
• Placing operators before operands