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.