Infix-Postfix-Prefix

flowchart LR
    subgraph "Expression Notations"
        direction TB
        I["Infix Notation
        (A + B) * C"]
        P["Prefix Notation
        * + A B C"]
        Po["Postfix Notation
        A B + C *"]
    end
    
    subgraph "Conversion Process"
        direction TB
        S1["Stack-based
        Conversion"]
        S2["Reverse Process"]
    end
    
    I -->|"Convert to"| P
    I -->|"Convert to"| Po
    P -->|"Convert to"| I
    Po -->|"Convert to"| I
    
    S1 --> P
    S1 --> Po
    S2 --> I
    
    style I fill:#f9f,stroke:#333,color:#000
    style P fill:#9f9,stroke:#333,color:#000
    style Po fill:#ff9,stroke:#333,color:#000
    style S1 fill:#ddd,stroke:#333,color:#000
    style S2 fill:#ddd,stroke:#333,color:#000

In the diagram above:

• Pink represents infix notation (traditional mathematical notation)
• Green represents prefix notation (operator before operands)
• Yellow represents postfix notation (operator after operands)
• The arrows show possible conversion paths between notations
• The “Stack-based Conversion” box shows how we convert from infix to other notations
• The “Reverse Process” box shows how we convert back to infix notation

Let’s implement a Python class that handles all these conversions:

class ExpressionConverter:
    def __init__(self):
        # Operator precedence table
        self.precedence = {
            '^': 3,
            '*': 2,
            '/': 2,
            '+': 1,
            '-': 1
        }
    
    def infix_to_postfix(self, expression: str) -> str:
        """Convert infix to postfix notation"""
        stack = []
        output = []
        
        # Process each character
        for char in expression:
            if char.isalnum():
                output.append(char)
            elif char == '(':
                stack.append(char)
            elif char == ')':
                while stack and stack[-1] != '(':
                    output.append(stack.pop())
                if stack and stack[-1] == '(':
                    stack.pop()  # Remove '('
            else:
                while (stack and stack[-1] != '(' and 
                       self.precedence.get(stack[-1], 0) >= self.precedence.get(char, 0)):
                    output.append(stack.pop())
                stack.append(char)
        
        # Pop remaining operators
        while stack:
            output.append(stack.pop())
            
        return ' '.join(output)
    
    def infix_to_prefix(self, expression: str) -> str:
        """Convert infix to prefix notation"""
        # Convert to postfix first
        postfix = self.infix_to_postfix(expression)
        
        # Convert postfix to prefix by reversing
        tokens = postfix.split()
        prefix = ' '.join(reversed(tokens))
        return prefix
    
    def postfix_to_infix(self, expression: str) -> str:
        """Convert postfix to infix notation"""
        stack = []
        
        for token in expression.split():
            if token.isalnum():
                stack.append(token)
            else:
                operand2 = stack.pop()
                operand1 = stack.pop()
                stack.append(f"({operand1}{token}{operand2})")
                
        return stack[0]
    
    def prefix_to_infix(self, expression: str) -> str:
        """Convert prefix to infix notation"""
        # Convert prefix to postfix by reversing
        tokens = expression.split()
        postfix = ' '.join(reversed(tokens))
        return self.postfix_to_infix(postfix)
 
# Example usage
converter = ExpressionConverter()
 
# Test infix to postfix
infix_expr = "(A + B) * C"
postfix_expr = converter.infix_to_postfix(infix_expr)
print(f"Infix to Postfix: {infix_expr} → {postfix_expr}")
 
# Test infix to prefix
prefix_expr = converter.infix_to_prefix(infix_expr)
print(f"Infix to Prefix: {infix_expr} → {prefix_expr}")
 
# Test postfix to infix
postfix_expr = "A B + C *"
infix_expr = converter.postfix_to_infix(postfix_expr)
print(f"Postfix to Infix: {postfix_expr} → {infix_expr}")
 
# Test prefix to infix
prefix_expr = "* + A B C"
infix_expr = converter.prefix_to_infix(prefix_expr)
print(f"Prefix to Infix: {prefix_expr} → {infix_expr}")

How the Conversions Work

1. Infix to Postfix 12:2:

• Use a stack to store operators
• Process expression from left to right
• When encountering an operand, add it to output
• For operators, pop higher precedence operators first
• Handle parentheses by pushing ’(’ and popping until ’)’

2. Infix to Prefix:

• Convert to postfix first
• Reverse the postfix expression
• This works because prefix is essentially postfix in reverse order

3. Postfix to Infix:

• Use a stack to build the expression
• When encountering an operand, push to stack
• When encountering an operator, pop two operands and combine
• Add parentheses to maintain correct order

4. Prefix to Infix:

• Convert to postfix first by reversing
• Then convert postfix to infix
• This maintains the correct operator precedence

Time and Space Complexity

• Time Complexity: O(n) where n is the length of the expression
• Space Complexity: O(n) for the stack and output storage

Example Step-by-Step Conversion

Let’s convert “(A + B) * C” to postfix:

1. Initial stack: []
2. Process ’(’: [ ’(’ ]
3. Process ‘A’: Output = [‘A’]
4. Process ’+’: [ ’(’ , ’+’ ]
5. Process ‘B’: Output = [‘A’, ‘B’]
6. Process ’)’: Output = [‘A’, ‘B’, ’+’]
7. Process '': [ ’(’ , ’+’ , '' ]
8. Process ‘C’: Output = [‘A’, ‘B’, ’+’, ‘C’]
9. Final stack pop: Output = [‘A’, ‘B’, ’+’, ‘C’, ’*’]

The final result is “A B + C *”, which represents the same expression in postfix notation.