Infix to Postfix Conversion Using Stack in DSA Python - Build from Scratch

Infix to Postfix Conversion Using Stack

📖 Scenario: You are building a simple calculator that converts expressions written in the usual way (like 3 + 4) into a form easier for computers to calculate (postfix notation).This helps computers solve math problems step-by-step without confusion about order.

🎯 Goal: Build a program that takes a math expression in infix form (like (A+B)*C) and converts it to postfix form (like AB+C*) using a stack.This shows how stacks help manage order of operations in math.

📋 What You'll Learn

Create a stack using a list to hold operators

Define operator precedence using a dictionary

Write a function to convert infix expression to postfix

Print the postfix expression after conversion

💡 Why This Matters

🌍 Real World

This technique is used in calculators and compilers to process and evaluate math expressions correctly.

💼 Career

Understanding stacks and expression parsing is important for software developers working on interpreters, compilers, and calculators.

1

Create the operator precedence dictionary

Create a dictionary called precedence with these exact entries: '+' with value 1, '-' with value 1, '*' with value 2, and '/' with value 2.

DSA Python

# Create the operator precedence dictionary
# Your code here

Hint

Use curly braces {} to create the dictionary and put operators as keys with their precedence numbers as values.

2

Create an empty stack list

Create an empty list called stack to be used as a stack for operators.

DSA Python

precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
# Create an empty list called stack
# Your code here

Hint

Use square brackets [] to create an empty list.

3

Write the function to convert infix to postfix

Write a function called infix_to_postfix that takes a string expression and returns the postfix string. Use the stack list and precedence dictionary. Use variables postfix as an empty string and iterate over each character char in expression. Push operators to stack and pop them based on precedence. Append operands directly to postfix. Handle parentheses by pushing '(' and popping until '(' when ')' is found. After the loop, pop all remaining operators from stack to postfix. Return postfix.

DSA Python

precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
stack = []
# Write the infix_to_postfix function below
# Your code here

Hint

Use char.isalnum() to check if character is a letter or number (operand). Use stack.append() to push and stack.pop() to pop. Compare precedence using the dictionary.

4

Print the postfix expression for a sample input

Call the function infix_to_postfix with the exact string '(A+B)*C' and print the result.

DSA Python

precedence = {'+': 1, '-': 1, '*': 2, '/': 2}
stack = []

def infix_to_postfix(expression):
    postfix = ''
    for char in expression:
        if char.isalnum():
            postfix += char
        elif char == '(':  
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':  
                postfix += stack.pop()
            stack.pop()  # Remove '('
        else:
            while stack and stack[-1] != '(' and precedence[stack[-1]] >= precedence[char]:
                postfix += stack.pop()
            stack.append(char)
    while stack:
        postfix += stack.pop()
    return postfix

# Call the function with '(A+B)*C' and print the result
# Your code here

Hint

Use print(infix_to_postfix('(A+B)*C')) exactly to show the postfix expression.