Python Program to Convert Infix to Postfix

In mathematics and computer science, infix and postfix notations are common ways of writing arithmetic expressions. Infix notation is the most familiar notation, where operators are placed between operands (e.g., A + B). Postfix notation (also called Reverse Polish Notation or RPN) places operators after their operands (e.g., A B +), which eliminates the need for parentheses and respects operator precedence without ambiguity.

In this post, we will explore how to convert an infix expression to a postfix expression using Python.

Why Convert Infix to Postfix?

Postfix expressions are easier to evaluate using stacks since there is no need to worry about operator precedence or parentheses. Compilers often convert infix expressions into postfix to simplify the process of evaluating complex arithmetic expressions.

Understanding the Process

To convert an infix expression to a postfix, we use a stack to temporarily hold operators and ensure the correct order of operations. The steps involved are:

1. Operands (numbers or variables) are added directly to the output (postfix expression).

2. Operators are pushed to the stack, but before pushing, check for operator precedence.

• If the operator at the top of the stack has higher or equal precedence than the current operator, pop from the stack and add to the output until this is no longer true.

3. Parentheses:

• When encountering a left parenthesis (, push it onto the stack.
• When encountering a right parenthesis ), pop from the stack to the output until a left parenthesis is found.

4. After traversing the infix expression, pop any remaining operators from the stack to the output.

Operator Precedence and Associativity

We need to consider operator precedence and associativity. Operators like * and / have higher precedence than + and -. Operators with the same precedence (like + and -) are left-associative, meaning we evaluate from left to right.

Python Code

Let’s write a Python program to convert infix expressions to postfix:

# Python program to convert infix to postfix

# Define precedence of operators

def precedence(op):

    if op == + or op == -:

        return 1

    if op == * or op == /:

        return 2

    return 0

# Function to check if a character is an operand

def is_operand(char):

    return char.isalpha() or char.isdigit()

# Function to convert infix expression to postfix

def infix_to_postfix(infix_expr):

    # Initialize an empty stack and an empty list for the result

    stack = []

    postfix = []

    # Traverse the infix expression

    for char in infix_expr:

        # If the character is an operand, add it to the result

        if is_operand(char):

            postfix.append(char)

        # If the character is a left parenthesis, push it to the stack

        elif char == '(':

            stack.append(char)

        # If the character is a right parenthesis

        elif char == ')':

            # Pop from the stack to the result until a left parenthesis is found

            while stack and stack[-1] != '(':

                postfix.append(stack.pop())

            stack.pop()  # Pop the left parenthesis

        # If the character is an operator

        else:

            # Pop from the stack to the result while the precedence of the operator

            # on the stack is greater than or equal to the current operator

            while stack and precedence(stack[-1]) >= precedence(char):

                postfix.append(stack.pop())

            # Push the current operator to the stack

            stack.append(char)

    # Pop all remaining operators from the stack

    while stack:

        postfix.append(stack.pop())

   # Convert the list to a string and return

    return ''.join(postfix)

# Input: Infix expression

infix_expr = "A+B*(C^D-E)"

# Convert infix to postfix

postfix_expr = infix_to_postfix(infix_expr)

# Output the resulting postfix expression

print("Infix Expression:", infix_expr)

print("Postfix Expression:", postfix_expr)

Explanation of the Code

1. precedence() Function:

• This function defines the precedence of operators. Higher precedence means the operator will be evaluated first. For example, * and / have a higher precedence than + and -.

2. is_operand() Function:

• This function checks whether a character is an operand (either a digit or a letter). Operands are directly added to the output (postfix expression).

3. infix_to_postfix() Function:

   We initialize an empty stack and an empty list (postfix) to store the result.

   We traverse each character in the infix expression:

• If the character is an operand, we append it to the postfix list.
• If the character is a left parenthesis (, we push it to the stack.
• If the character is a right parenthesis ), we pop elements from the stack and append them to postfix until we encounter a left parenthesis.
• If the character is an operator, we compare its precedence with the operator at the top of the stack and pop accordingly.
• After the loop, any remaining operators are popped from the stack and added to postfix.
• The function returns the postfix expression as a string.

4. Main Program:

• We take an example infix expression like "A+B*(C^D-E)" and call the infix_to_postfix() function to get the postfix expression.
• The result is then printed.

Output

Infix Expression: A+B*(C^D-E)

Postfix Expression: ABCD^E-*+

Step-by-Step Example

Let’s go through an example to see how the conversion works for the infix expression A + B * (C ^ D - E):

1. Read A: Operand, so add it to postfix → Postfix: A

2. Read +: Operator, push it onto the stack → Stack: +

3. Read B: Operand, add to postfix → Postfix: AB

4. Read *: Higher precedence than +, push it onto the stack → Stack: + *

5. Read (`: Left parenthesis, push onto the stack → Stack: + * (

6. Read C: Operand, add to postfix → Postfix: ABC

7. Read ^: Push it onto the stack → Stack: + * ( ^

8. Read D: Operand, add to postfix → Postfix: ABCD

9. Read -: Pop ^ from the stack to postfix (since ^ has higher precedence) → Postfix: ABCD^ and push - onto the stack → Stack: + * ( -

10. Read E: Operand, add to postfix → Postfix: ABCD^E

11. Read ): Pop everything inside parentheses and add to postfix → Postfix: ABCD^E-* → Stack: +

12. Pop the remaining operators → Postfix: ABCD^E-*+

This is the screenshot of the Jupyter Notebook of the Above Program

Conclusion

Converting an infix expression to a postfix is an essential task in expression evaluation and is widely used in various computing applications. By using a stack and understanding operator precedence, you can efficiently convert complex infix expressions to postfix notation in Python.