Topic Wise Lesson Plane

Infix to Postfix Transformation

1. Expression Notations

• Infix: Operator is between operands
  Example: A + B

• Postfix (Reverse Polish): Operator comes after operands
  Example: AB+

2. Operator Precedence

3. Rules for Infix → Postfix Conversion

1. If the symbol is an operand, add it to the postfix expression.

2. If the symbol is (, push it onto the stack.

3. If the symbol is ), pop from the stack and add to postfix until ( is removed.

4. If the symbol is an operator:

   • Pop operators from the stack with higher or equal precedence

   • Then push the current operator onto the stack.

5. After scanning the entire infix expression, pop all remaining operators from the stack and add to postfix.

4. Algorithm

InfixToPostfix(expression):
    create empty stack
    create empty postfix string

    for each symbol in expression:
        if symbol is operand:
            add to postfix
        else if symbol == '(':
            push onto stack
        else if symbol == ')':
            pop from stack and add to postfix until '(' is popped
        else if symbol is operator:
            while stack not empty and
                  precedence(top) >= precedence(symbol):
                pop and add to postfix
            push symbol onto stack

    while stack not empty:
        pop and add to postfix

    return postfix

5. Example Conversion

Infix Expression:

A + B * C

Step-by-Step:

Postfix Expression:

ABC*+

6. Another Example (with parentheses)

Infix:

(A + B) * C

Postfix:

AB+C*

7. Advantages of Using Stack

• Handles operator precedence

• Eliminates parentheses

• Efficient and easy to implement

• Widely used in expression evaluation