Infix, Prefix, and Postfix Notations 🎯

Welcome to our deep dive into Infix, Prefix, and Postfix Notations! Let's embark on a journey to understand these important concepts in the world of programming. 📝

What are Infix, Prefix, and Postfix Notations? 💡

Infix, Prefix, and Postfix notations are ways to represent mathematical and logical expressions. They are essential for computer programming because they allow us to write more complex expressions using symbols.

Infix Notation 💡

Infix notation is the most common and familiar way of writing mathematical expressions, using operators like +, -, *, /, ^, and parentheses ().

markdown

Example: 3 + 4

In this example, + is an infix operator, and the operands are 3 and 4.

Prefix Notation 💡

Prefix notation, also known as Polish notation, reverses the order of the operator and the operands. The operator comes first, followed by the operands separated by spaces.

markdown

Example: + 3 4

In this example, + is the operator, and the operands are 3 and 4.

Postfix Notation 💡

Postfix notation, also known as Reverse Polish notation (RPN), is similar to prefix notation but with the operator after the operands. The operator comes last, followed by the operands separated by spaces.

markdown

Example: 3 4 +

In this example, + is the operator, and the operands are 3 and 4.

Why Use Different Notations? 💡

Different notations have various advantages and are used in specific scenarios.

Infix Notation: It is easy to read and write for humans. However, it can be challenging for computers to parse due to the need for parentheses and operator precedence rules.
Prefix and Postfix Notations: They are more suitable for computers because they are simpler to parse and evaluate without the need for parentheses. However, they may be less intuitive for humans to read.

Converting Between Notations 📝

Converting between notations can be useful in certain situations. Here's a simple example of how to convert an infix expression to prefix and postfix notations:

Infix to Prefix Notation

Step 1: Identify all the operators and operands.
Step 2: Move all operators to the left, making sure to place them before their corresponding operands.
Step 3: If there are multiple operators, apply the operator precedence rules to determine the order.

Example: Convert (3 + 4) * 5 to prefix notation.

Operators: +, *
Operands: 3, 4, 5
Move the operators to the left and apply operator precedence: * + 3 4 5

Infix to Postfix Notation

Step 1: Identify all the operators and operands.
Step 2: Place all operands to the right of the corresponding operators.
Step 3: Apply operator precedence rules to determine the order.
Step 4: If there are multiple operators with the same precedence, place them in left-to-right order.

Example: Convert (3 + 4) * 5 to postfix notation.

Operators: +, *
Operands: 3, 4, 5
Move the operands to the right of the operators: 3 4 * 5 +

Implementing Notation Conversion in Code 💡

Here's a simple Python implementation of a function that converts infix expressions to prefix and postfix notations:

python

# Infix to Prefix Notation
def infix_to_prefix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    operators = []
    output = []

    for token in expression.split():
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token.isdigit():
            output.append(token)
        elif token in operators:
            while len(operators) > 0 and precedence[operators[-1]] >= precedence[token]:
                output.append(operators.pop())
            operators.append(token)
        elif token == '(':
            operators.append(token)
        elif token == ')':
            while operators[-1] != '(':
                output.append(operators.pop())
            operators.pop()

    while len(operators) > 0:
        output.append(operators.pop())

    return ' '.join(output)

# Infix to Postfix Notation
def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    operators = []
    output = []

    for token in expression.split():
        if token in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or token.isdigit():
            output.append(token)
        elif token in operators:
            while len(operators) > 0 and precedence[operators[-1]] >= precedence[token]:
                output.append(operators.pop())
            operators.append(token)
        elif token == '(':
            operators.append(token)
        elif token == ')':
            while operators[-1] != '(':
                output.append(operators.pop())
            operators.pop()
            operator = operators.pop()
            while len(operators) > 0 and precedence[operators[-1]] > precedence[operator]:
                output.append(operators.pop())
            operators.append(operator)

    while len(operators) > 0:
        output.append(operators.pop())

    return ' '.join(output)

# Test Cases
print(infix_to_prefix("(3 + 4) * 5"))  # Output: * + 3 4 5
print(infix_to_postfix("(3 + 4) * 5"))  # Output: 3 4 * 5 +

By now, you should have a good understanding of Infix, Prefix, and Postfix notations. Happy coding! 🚀💻