Infix Expression

An infix expression is a mathematical expression in which the operators are placed between the operands. It is the commonly used notation for writing mathematical expressions.

Here's an example of an infix expression:

Expression: A + (B * C) - D

In this example, the operands are letters A, B, C, and D, and the operators are +, *, and -.

Prefix Expression

A prefix expression is a mathematical expression where operators are placed before their corresponding operands. It is also known as prefix notation or Polish Notation.

Here's an example of a prefix expression using letters as operands:

Expression: - + A * B C D

In this example, the operands are letters A, B, C, and D, and the operators are +, *, and -.

How to convert Infix Expression to Prefix Expression?

To convert an infix expression to a prefix expression, you can follow a similar algorithm as infix to postfix conversion, but with a few modifications:

Reverse the infix expression.

Create an empty stack for operators and an empty list for the output (prefix) expression.

Start scanning the reversed infix expression from left to right.

If the scanned element is an operand (letter), add it to the output list.

If the scanned element is an opening parenthesis '(', push it onto the stack.

If the scanned element is a closing parenthesis ')', pop operators from the stack and add them to the output list until an opening parenthesis is found. Discard the opening parenthesis.

If the scanned element is an operator, compare its precedence with the top operator on the stack:

a. If the precedence is lower or equal, pop the top operator from the stack and append it to the output list. Repeat this step until the stack is empty or an operator with lower precedence is encountered.

b. Push the current operator onto the stack.

After scanning the entire expression, pop any remaining operators from the stack and append them to the output list.

Reverse the output list to obtain the prefix expression.

Example1- Infix Expression: A + (B * C) - D

1. Reversed string:   D - (C * B) + A

2. Postfix of D - (C * B) + A:   D C B* - A+  

3. Reversed string of D C B* - A+:   +A - *B C D

Converting Infix Expression to Prefix Expression in C++:

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

bool isOperator(char c)
{
    return (!isalpha(c) && !isdigit(c));
}

int getPriority(char C)
{
    if (C == '-' || C == '+')
        return 1;
    else if (C == '*' || C == '/')
        return 2;
    else if (C == '^')
        return 3;
    return 0;
}

string infixToPostfix(string infix)
{
    infix = '(' + infix + ')';
    int length = infix.size();
    stack<char> operatorStack;
    string postfix;

    for (int i = 0; i < length; i++)
    {
        if (isalpha(infix[i]) || isdigit(infix[i]))
        {
            postfix += infix[i];
        }
        else if (infix[i] == '(')
        {
            operatorStack.push('(');
        }
        else if (infix[i] == ')')
        {
            while (operatorStack.top() != '(')
            {
                postfix += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.pop();
        }
        else
        {
            if (isOperator(operatorStack.top()))
            {
                if (infix[i] == '^')
                {
                    while (getPriority(infix[i]) <= getPriority(operatorStack.top()))
                    {
                        postfix += operatorStack.top();
                        operatorStack.pop();
                    }
                }
                else
                {
                    while (getPriority(infix[i]) < getPriority(operatorStack.top()))
                    {
                        postfix += operatorStack.top();
                        operatorStack.pop();
                    }
                }
                operatorStack.push(infix[i]);
            }
        }
    }

    while (!operatorStack.empty())
    {
        postfix += operatorStack.top();
        operatorStack.pop();
    }

    return postfix;
}

string infixToPrefix(string infix)
{
    reverse(infix.begin(), infix.end());
    int length = infix.size();

    for (int i = 0; i < length; i++)
    {
        if (infix[i] == '(')
        {
            infix[i] = ')';
        }
        else if (infix[i] == ')')
        {
            infix[i] = '(';
        }
    }

    string postfix = infixToPostfix(infix);
    reverse(postfix.begin(), postfix.end());

    return postfix;
}

int main()
{
    string infixExpression;
    cout << "Enter the infix expression: ";
    getline(cin, infixExpression);

    string prefixExpression = infixToPrefix(infixExpression);
    cout << "Prefix expression: " << prefixExpression << endl;

    return 0;
}

Output:

Enter the infix expression: A+(B*C)-D
Prefix expression: +A-*B C D

Why do we need Prefix Expression?

1. Operator Priority: When using prefix notation, the priority of the operations is indicated without the use of parentheses. Parentheses are frequently used in infix expressions to specify the evaluation order. Prefix notation eliminates the uncertainty of parentheses, making it simpler to evaluate expressions because the order of operations is simply controlled by the position of the operators.
2. No Ambiguity: Any ambiguity that may emerge from infix phrases is eliminated by prefix notation. It could be unclear whether to add or multiply first in an infix phrase like "2 + 3 * 4," for instance. This statement would be expressed as "+ 2 * 3 4," eliminating any possibility of ambiguity, in prefix notation.
3. Expression Manipulation: Expressions in prefix notation can be easily changed and manipulated. The expression structure can easily be changed and reconfigured without altering the meaning or order of operations because the operators come before the operands.