Infix to Prefix Conversion 🎯

Welcome to a deep dive into the fascinating world of Data Structures and Algorithms! Today, we'll be exploring Infix to Prefix Conversion, a crucial concept that will help you navigate complex mathematical and programming expressions.

Understanding Infix and Prefix Notations 📝

Before we dive into the conversion process, let's familiarize ourselves with Infix and Prefix Notations.

Infix Notation 💡

Infix notation is a way of representing mathematical operations between operands, such as 2 + 3. The operators are placed between the operands.

Prefix Notation 💡

Prefix notation, also known as Polish notation, places the operator before the operands, like + 2 3. This notation simplifies the evaluation order and can be more easily parsed by computers.

The Need for Conversion 💡

Converting infix notation to prefix notation is essential for parsing complex mathematical and programming expressions, especially when dealing with functions and multiple operators.

Conversion Algorithm 💡

We'll be using a simple algorithm for conversion:

Parentheses Balancing: Ensure the parentheses in the infix expression are balanced.
Precedence: Determine the precedence of operators. Operators with higher precedence are evaluated before lower ones (e.g., multiplication before addition).
Associativity: Decide on the associativity of operators if there's more than one of the same operator in a row. Generally, operators are left-associative, meaning they are evaluated from left to right.
Build Prefix Expression: Start building the prefix expression, placing operators before their corresponding operands.

Example: Converting `( 1 + 2 ) * 3` 💡

Let's convert the infix expression ( 1 + 2 ) * 3 to prefix notation using our algorithm.

Parentheses balancing: The parentheses are balanced.
Precedence: * has higher precedence than +, so we'll evaluate the addition first.
Associativity: The operators are left-associative, so we'll evaluate the addition from left to right.
Build Prefix Expression: * ( + 1 2 ) 3

Code Examples 💡

Now, let's implement the conversion algorithm in Python and Java to make it practical.

Python Example 📝

python

def convert_to_prefix(infix):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    prefix = []
    parentheses_stack = []
    operands_stack = []

    for token in infix:
        if token.isalnum():
            operands_stack.append(token)
        elif token in ['(', ')']:
            parentheses_stack.append(token)
            while parentheses_stack and parentheses_stack[-1] == '(':
                operation = parentheses_stack.pop()
                operands_stack.append(operation)
        elif token in ['+', '-', '*', '/', '^']:
            while parentheses_stack and parentheses_stack[-1] != '(' and precedence[parentheses_stack[-1]] >= precedence[token]:
                operation = parentheses_stack.pop()
                right_operand = operands_stack.pop()
                left_operand = operands_stack.pop()
                prefix.append(operation + ' ' + left_operand + ' ' + right_operand)
            parentheses_stack.append(token)

    while parentheses_stack:
        operation = parentheses_stack.pop()
        operands_stack.append(operation)

    while operands_stack:
        prefix.append(operands_stack.pop())

    return ' '.join(prefix)

print(convert_to_prefix('( 1 + 2 ) * 3'))  # Output: * ( + 1 2 ) 3

Java Example 📝

java

import java.util.Stack;

public class InfixToPrefix {
    static int precedence(char op) {
        switch (op) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
            default:
                return -1;
        }
    }

    static String infixToPrefix(String exp) {
        String prefix = "";
        Stack<Character> s = new Stack<>();

        for (int i = 0; i < exp.length(); i++) {
            char symbol = exp.charAt(i);

            if (Character.isLetter(symbol) || Character.isDigit(symbol))
                prefix += symbol + " ";

            if (symbol == '(')
                s.push(symbol);

            else if (symbol == ')') {
                char topSymbol = s.peek();
                while (topSymbol != '(') {
                    prefix += topSymbol + " ";
                    s.pop();
                    topSymbol = s.peek();
                }
                s.pop();
            }

            else if (s.isEmpty() || precedence(s.peek()) < precedence(symbol))
                s.push(symbol);

            else {
                char topSymbol = s.peek();
                while (!s.isEmpty() && precedence(topSymbol) >= precedence(symbol)) {
                    prefix += topSymbol + " ";
                    s.pop();
                    if (!s.isEmpty())
                        topSymbol = s.peek();
                }
                s.push(symbol);
            }
        }

        while (!s.isEmpty()) {
            char topSymbol = s.peek();
            if (topSymbol == '(') break;
            prefix += topSymbol + " ";
            s.pop();
        }

        return prefix;
    }

    public static void main(String[] args) {
        String exp = "( 1 + 2 ) * 3";
        System.out.println(infixToPrefix(exp));  // Output: * ( + 1 2 ) 3
    }
}

Infix to Prefix Conversion 🎯

Infix to Prefix Conversion 🎯

Understanding Infix and Prefix Notations 📝

Infix Notation 💡

Prefix Notation 💡

The Need for Conversion 💡

Conversion Algorithm 💡

Example: Converting ( 1 + 2 ) * 3 💡

Code Examples 💡

Python Example 📝

Java Example 📝

Quiz 💡

Example: Converting `( 1 + 2 ) * 3` 💡