Convert Infix Expression to Prefix

Steps for converting Infix to Prefix

1. Reverse the infix expression.
2. Replace ( with ) and vice versa.
3. Convert the modified expression to postfix using the same algorithm you would use for infix to postfix conversion.
4. Reverse the postfix expression to get the prefix expression.

Let’s break these steps down further:

• Step 1: Reversing the infix expression.
  • Example: If the infix is A + B * C, after reversing, it becomes C * B + A.
• Step 2: Swap ( and ).
  • If the original expression has parentheses, you’ll need to swap them. This doesn’t apply to our example, but if it did, you’d reverse parentheses.
• Step 3: Convert the reversed expression to postfix.
  • Use the standard algorithm for converting an infix expression to postfix:
    • If the symbol is an operand, add it to the result.
    • If the symbol is an operator, pop operators from the stack that have greater or equal precedence, then push the current operator.
    • If it’s a parenthesis, handle it appropriately (push ( to the stack, and pop when encountering )).
• Step 4: Reverse the resulting postfix expression to get the prefix expression.

Precedence and Associativity Rules:

• Operators like + and - have lower precedence compared to * and /.
• If operators have the same precedence, associativity (left-to-right or right-to-left) comes into play.

Program Implementation in C:

Steps for converting Infix to Prefix:

1. Reverse the infix expression.
2. Replace ( with ) and vice versa.
3. Convert the modified expression to postfix using the same algorithm you would use for infix to postfix conversion.
4. Reverse the postfix expression to get the prefix expression.

Let’s break these steps down further:

• Step 1: Reversing the infix expression.
  • Example: If the infix is A + B * C, after reversing, it becomes C * B + A.
• Step 2: Swap ( and ).
  • If the original expression has parentheses, you’ll need to swap them. This doesn’t apply to our example, but if it did, you’d reverse parentheses.
• Step 3: Convert the reversed expression to postfix.
  • Use the standard algorithm for converting an infix expression to postfix:
    • If the symbol is an operand, add it to the result.
    • If the symbol is an operator, pop operators from the stack that have greater or equal precedence, then push the current operator.
    • If it’s a parenthesis, handle it appropriately (push ( to the stack, and pop when encountering )).
• Step 4: Reverse the resulting postfix expression to get the prefix expression.

Precedence and Associativity Rules:

• Operators like + and - have lower precedence compared to * and /.
• If operators have the same precedence, associativity (left-to-right or right-to-left) comes into play.

Program Implementation in C:

#include<stdio.h>
#include<string.h>
#include<ctype.h>

#define MAX 100

// Stack structure
struct Stack {
    int top;
    char items[MAX];
};

void push(struct Stack *s, char item) 
{
    if (s->top == MAX - 1) 
{
        printf("Stack Overflow\n");
        return;
    }
    s->items[++(s->top)] = item;
}

char pop(struct Stack *s) 
{
    if (s->top == -1) 
{
        printf("Stack Underflow\n");
        return '\0';
    }
    return s->items[(s->top)--];
}

char peek(struct Stack *s) 
{
    return s->items[s->top];
}

int isEmpty(struct Stack *s) 
{
    return s->top == -1;
}

// Function to check if the character is an operator
int is Operator(char ch) 
{
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^');
}

// Function to get precedence of the operators
int precedence(char op) 
{
    switch (op) 
{
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
        default:
            return 0;
    }
}

// Function to reverse the string
void reverse(char *exp) 
{
    int len = strlen(exp);
    for (int i = 0; i < len / 2; i++) 
{
        char temp = exp[i];
        exp[i] = exp[len - i - 1];
        exp[len - i - 1] = temp;
    }
}

// Function to convert infix to postfix
void infixToPostfix(char *exp, char *result) 
{
    struct Stack stack;
    stack.top = -1;
    int k = 0;

    for (int i = 0; exp[i]; i++) 
{
        // If the scanned character is an operand, add it to the result
        if (is a l num(exp[i])) 
{
            result[k++] = exp[i];
        }
        // If the scanned character is '(', push it to the stack
        else if (exp[i] == '(')
{
            push(&stack, exp[i]);
        }
        // If the scanned character is ')', pop and add to result until '(' is encountered
        else if (exp[i] == ')') 
{
            while (!is Empty(&stack) && peek(&stack) != '(') 
{
                result[k++] = pop(&stack);
            }
            pop(&stack); // Remove '(' from stack
        }
        // If the scanned character is an operator
        else if (is Operator(exp[i])) 
{
            while (!is Empty(&stack) && precedence(peek(&stack)) >= precedence(exp[i])) 
{
                result[k++] = pop(&stack);
            }
            push(&stack, exp[i]);
        }
    }

    // Pop all the operators from the stack
    while (!is  Empty(&stack)) 
{
        result[k++] = pop(&stack);
    }
    result[k] = '\0'; // Null-terminate the result string
}

// Function to convert infix to prefix
void infix To Prefix(char *exp, char *result) 
{
    int len = str len(exp);

    // Step 1: Reverse the infix expression
    reverse(exp);

    // Step 2: Replace '(' with ')' and vice versa
    for (int i = 0; i < len; i++) 
{
        if (exp[i] == '(')
            exp[i] = ')';
        else if (exp[i] == ')')
            exp[i] = '(';
    }

    // Step 3: Convert the modified infix expression to postfix
    infix To Postfix(exp, result);

    // Step 4: Reverse the postfix expression to get the prefix expression
    reverse(result);
}

int main() 
{
    char infix[MAX], prefix[MAX];

    printf("Enter an infix expression: ");
    gets(infix); // Read the infix expression

    infix To Prefix(infix, prefix);

    printf("Prefix expression: %s\n", prefix);

    return 0;
}

Explanation of the Code:

• Stack Operations: The stack operations (push, pop, and peek) are used to manage operators while converting the expression.
• Precedence: The precedence() function returns the precedence of operators. Higher numbers indicate higher precedence.
• Reversing and Conversion: The main function infixToPrefix() handles reversing the infix expression and calling the infixToPostfix() function, which uses the stack to convert the expression.
• Final Reversal: After converting to postfix, the result is reversed to get the final prefix expression.

Example Input and Output:

Input: A + B * C
Output: +A*BC

Input: (A - B) * (C + D)
Output: *-AB+CD

Detailed Explanation:

1. The user enters an infix expression like A + B * C.
2. The program reverses it to C * B + A.
3. Then it converts this reversed expression to postfix (CB*A+).
4. Finally, it reverses the postfix result to get the prefix expression +A*BC.

This program efficiently converts any valid infix expression to its corresponding prefix notation using stack operations and string manipulation techniques.