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 (+, -, *, /).