Infix to Postfix Conversion Using Stack in DSA Python

Mental Model

We change math expressions from normal reading order to a form that computers can easily calculate using a stack.

Analogy: Imagine you have a pile of plates (stack). You put operators on top and take them off in the right order to get the correct math result.

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

Dry Run Walkthrough

Input: infix expression: A + B * C

Goal: Convert the infix expression to postfix form so it can be evaluated easily.

Step 1: Read 'A', which is an operand, add it to postfix

Postfix: A
Stack: empty

Why: Operands go directly to the output.

Step 2: Read '+', push it onto the stack

Postfix: A
Stack: +

Why: Operators go to the stack to wait for their turn.

Step 3: Read 'B', add it to postfix

Postfix: A B
Stack: +

Why: Operands go directly to output.

Step 4: Read '*', push it onto the stack because it has higher precedence than '+'

Postfix: A B
Stack: + -> *

Why: Higher precedence operators go on top of lower ones.

Step 5: Read 'C', add it to postfix

Postfix: A B C
Stack: + -> *

Why: Operands go directly to output.

Step 6: No more input, pop '*' from stack to postfix

Postfix: A B C *
Stack: +

Why: Pop operators after input is done.

Step 7: Pop '+' from stack to postfix

Postfix: A B C * +
Stack: empty

Why: Finish by emptying the stack.

Result:

Postfix: A B C * +

Annotated Code

DSA Python

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop() if self.items else None
    def peek(self):
        return self.items[-1] if self.items else None
    def is_empty(self):
        return len(self.items) == 0

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

def infix_to_postfix(expression):
    stack = Stack()
    postfix = []
    for char in expression:
        if char.isalnum():
            postfix.append(char)  # add operands directly
        elif char == '(':  
            stack.push(char)  # push '(' to stack
        elif char == ')':
            while stack.peek() != '(':
                postfix.append(stack.pop())  # pop until '('
            stack.pop()  # remove '(' from stack
        else:
            while (not stack.is_empty() and precedence(char) <= precedence(stack.peek()) and stack.peek() != '('):
                postfix.append(stack.pop())  # pop higher or equal precedence
            stack.push(char)  # push current operator
    while not stack.is_empty():
        postfix.append(stack.pop())  # pop remaining operators
    return ' '.join(postfix)

# Driver code
expr = "A+B*C"
result = infix_to_postfix(expr)
print(result)

if char.isalnum():

Add operands directly to postfix output

elif char == '(':

Push '(' to stack to mark start of sub-expression

elif char == ')':

Pop from stack to postfix until '(' is found

while (not stack.is_empty() and precedence(char) <= precedence(stack.peek()) and stack.peek() != '('):

Pop operators with higher or equal precedence before pushing current operator, but stop at '('

stack.push(char)

Push current operator onto stack

while not stack.is_empty():

Pop all remaining operators to postfix after input processed

Output

A B C * +

Complexity Analysis

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

Space: O(n) because the stack and output list can hold up to all characters in the expression

vs Alternative: Compared to evaluating infix directly, this method simplifies evaluation by converting to postfix first, avoiding complex precedence checks during calculation

Edge Cases

Empty expression

Returns empty postfix string without error

DSA Python

while not stack.is_empty():

Expression with parentheses

Correctly handles nested parentheses by pushing '(' and popping until '(' on ')'

DSA Python

elif char == ')':

Expression with single operand

Returns the operand itself as postfix

DSA Python

if char.isalnum():

When to Use This Pattern

When you see a math expression with operators and parentheses and need to evaluate or reorder it, use the infix to postfix conversion pattern with a stack to handle operator precedence cleanly.

Common Mistakes

Mistake: Not popping all remaining operators from the stack after processing input
Fix: Add a final loop to pop all remaining operators to postfix after input is done

Mistake: Pushing operators without checking precedence, causing wrong order
Fix: Pop operators from stack while they have higher or equal precedence before pushing new operator

Mistake: Ignoring parentheses and not popping until '(' on encountering ')'
Fix: On reading ')', pop until '(' is found and remove '(' from stack

Summary

Converts a normal math expression into postfix form using a stack to manage operators.

Use when you want to evaluate or simplify expressions by removing the need for precedence rules during calculation.

The key is to use a stack to hold operators and pop them in the correct order based on precedence and parentheses.

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