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 -.

Postfix Expression

A postfix expression is a mathematical expression where operators are placed after their corresponding operands. also It is known as a postfix notation or Reverse Polish Notation (RPN).

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

Expression: ABC*+D-

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

How to convert Infix Expression to Postfix Expression?

To convert an infix expression to a postfix expression you can follow the algorithm below. A step-by-step example using the infix expression is mentioned below:

1. Create an empty stack for operators and an empty list for the output (postfix) expression. Stack: [ ] Postfix: [ ]

2. Start scanning the infix expression from left to right. Expression: A + (B * C) - D

3. If the scanned element is an operand (in this case, a letter), add it to the output list. Stack: [ ] Postfix: [A]

4. If the scanned element is an operator, check the precedence of the operator with the operator at the top of the stack. 

a. If the stack is empty or the top operator has lower precedence than the scanned operator, push the scanned operator       onto the stack. Stack: [+] Postfix: [A].

b. If the top operator has higher or equal precedence, pop operators from the stack and add them to the output list until the top operator has lower precedence or the stack is empty. Then, push the scanned operator onto the stack. Stack: [+] Postfix: [A]. 

c. Repeat step 4b until all operators have been processed.

5. After scanning the entire expression, pop any remaining operators from the stack and add them to the output list. Stack: [-] Postfix: [A, B, C, *, +]

                                            Example 1: Expression: A + (B * C) - D

                                              Example 2: Expression: (A + B) * (C - D) / E^F

Converting Infix Expression to Postfix Expression in C++:

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

bool isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}

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

string infixToPostfix(const string& infix) {
    string postfix;
    stack<char> operatorStack;

    for (char c : infix) {
        if (isalnum(c)) {
            postfix += c;
        } else if (c == '(') {
            operatorStack.push(c);
        } else if (c == ')') {
            while (!operatorStack.empty() && operatorStack.top() != '(') {
                postfix += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.pop(); // Discard the '('
        } else if (isOperator(c)) {
            while (!operatorStack.empty() && precedence(operatorStack.top()) >= precedence(c)) {
                postfix += operatorStack.top();
                operatorStack.pop();
            }
            operatorStack.push(c);
        }
    }

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

    return postfix;
}

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

    string postfixExpression = infixToPostfix(infixExpression);
    cout << "Postfix expression: " << postfixExpression << endl;

    return 0;
}

Output1:

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

Output2:

Enter the infix expression: (A + B) * (C - D) / E^F
Postfix expression: AB+CD-*EF^/

Why do we need Postfix Expression?

There are several reasons why postfix expressions are useful and why they are used in certain scenarios:

1. Operator Precedence: Postfix notation eliminates the need for parentheses to indicate the order of operations. In infix expressions, parentheses are often used to clarify the order of evaluation. In postfix notation, the order of operations is determined solely by the position of the operators, making it easier to evaluate expressions without the ambiguity of parentheses.
2. No Ambiguity: Postfix notation removes any ambiguity that may arise from infix expressions. For example, in an infix expression like "2 + 3 * 4," there might be confusion about whether to perform the addition or multiplication first. In postfix notation, this expression would be written as "2 3 4 * +," leaving no room for confusion.
3. Ease of Evaluation: Postfix expressions can be evaluated more easily using a stack-based approach. The evaluation process involves pushing operands onto a stack and performing operations when encountering an operator. This method simplifies the evaluation process and eliminates the need for complex parsing algorithms.
4. Efficiency: Postfix expressions can be evaluated more efficiently by computers because they do not require the use of parentheses or complex parsing algorithms. The evaluation process becomes a straightforward iterative process, making it easier to implement in computer programs.