Understanding Infix, Postfix, and Prefix Expressions/Notations in DSA

Math expressions often deal with complicated expressions that the reader or the software has to make sense of in terms of the precedence of the operations involved. There are several ways to represent expressions using different notations; each representation has its relative advantages and disadvantages. In this paper, we are going to discuss three popular notations of expressions: infix, prefix, and postfix.

Infix Expressions

Infix expressions are mathematical expressions where the operator is between its operands. This is the most common mathematical notation used by human beings. For example, the expression 5 + 7 is an infix expression. In the above expression, the operator + is between the two operands 5 and 7. These notations are indicative and relatively easy to handle by human beings, but sometimes it creates complexity for a computer to evaluate the result efficiently. This is because there is a precedence that must be followed, and parentheses change the default precedence.

Common Way of Writing Infix Expressions

• Infix notation is the notation that people are most accustomed to. For example, A + B is in infix notation.
• The operands are placed on either side of the operator between them. In the expression A + B, the plus operator + is between the operands A and B.
• The precedence of operations is specified within infix notation by the use of parenthesis. For example, given (A + B) * C, the parentheses enforce the rule that addition should be performed before multiplication.

Operator Precedence Rules

Each of the operators used in the infix expressions has precedence rules associated with it, which specify the order of evaluating the operators appearing in such an expression. Multiplication and division operations have increased precedence over addition and subtraction. Thus, in the expression A + B * C, the operation of multiplication will be performed prior to that of addition.

• Parentheses: This is when one wants to evaluate the expressions within all sets of parentheses first.
• Exponentiation: this is where exponents are evaluated second.
• Multiplication and division: multiplication and division have to be evaluated ahead of addition and subtraction.
• Addition and subtraction: lastly, addition and subtraction are evaluated at the very end.

Operator	Precedence
Parentheses ()	Highest
Exponents ^	High
Multiplication *	Medium
Division /	Medium
Addition +	Low
Subtraction -	Low

Evaluating Infix Expressions

Evaluating infix expressions requires additional processing to handle the order of operations and parentheses. First, convert the infix expression to postfix notation. This can be done using a stack or a recursive algorithm, after which the postfix expression is evaluated.

Advantages of Infix Expressions

• More natural and easier to read and understand for humans.
• Widely used and supported by most programming languages and calculators.

Disadvantages of Infix Expressions

• Requires parentheses to specify the order of operations.
• It can be difficult to parse and evaluate efficiently.

Prefix Expressions (Polish Notation)

Prefix expressions, also known as Polish notation, are a mathematical notation where the operator precedes its operands. This differs from infix notation, where the operator is placed between its operands. In prefix notation, the operator is written first, followed by its operands. For example, the infix expression A + B would be written as + A B in prefix notation.

Evaluating Prefix Expressions

Prefix expressions are useful in certain scenarios, such as when dealing with expressions that have many nested parentheses or when using a stack-based programming language.

Advantages of Prefix Expressions

• No need for parentheses, as the operator always precedes its operands.
• Easier to parse and evaluate using a stack-based algorithm.
• More efficient in situations involving expressions with many nested parentheses.

Disadvantages of Prefix Expressions

• It can be difficult for humans to read and understand.
• Less commonly used than infix notation.

Example

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

int evaluatePrefixExpression(const string &expression) {
    stack<int> st;  

    for (int i = expression.length() - 1; i >= 0; i--) {
        if (isdigit(expression[i])) {
            st.push(expression[i] - '0');  
        } else {
            if (st.size() < 2) {
                cerr << "Error: Not enough operands for operation." << endl;
                return 0;  
            }
            int op1 = st.top(); st.pop();
            int op2 = st.top(); st.pop();
            switch (expression[i]) {
                case '+':
                    st.push(op1 + op2);
                    break;
                case '-':
                    st.push(op1 - op2);
                    break;
                case '*':
                    st.push(op1 * op2);
                    break;
                case '/':
                    if (op2 != 0) 
                        st.push(op1 / op2);
                    else {
                        cerr << "Error: Division by zero." << endl;
                        return 0;  
                    }
                    break;
                case '^':
                    st.push(pow(op1, op2));
                    break;
                default:
                    cerr << "Error: Invalid operator encountered." << endl;
                    return 0; 
            }
        }
    }
    return st.top();  
}
int main() {
    string expression = "*+45+20";  
    cout << "The result of the prefix expression is: " 
         << evaluatePrefixExpression(expression) << endl;
    return 0;
}
//Output - The result of the prefix expression is: 18

Postfix Expressions (Reverse Polish Notation)

Postfix expressions, also known as Reverse Polish Notation (RPN), are a mathematical notation where the operator follows its operands. This is different from infix notation, where the operator is placed between its operands. In postfix notation, operands are written first, followed by the operator. For example, the infix expression A + B would be written as A B + in postfix notation. We can evaluate postfix expressions from left to right, with each operator being applied to its operands as encountered.

Evaluating Postfix Expressions

Postfix expressions are useful in situations involving many nested parentheses or when working with stack-based programming languages.

Advantages of Postfix Notation

• Eliminates the need for parentheses.
• Easier to read and understand for humans.
• More commonly used than prefix notation.

Disadvantages of Postfix Expressions

• Requires a stack-based algorithm for evaluation.
• It can be less efficient than prefix notation in certain situations.

Example

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

int evaluatePostfixExpression(string str) {
    stack<int> st;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] >= '0' && str[i] <= '9') {
            st.push(str[i] - '0');
        } else {
            int op2 = st.top();
            st.pop();
            int op1 = st.top();
            st.pop();

            switch (str[i]) {
                case '+':
                    st.push(op1 + op2);
                    break;
                case '-':
                    st.push(op1 - op2);
                    break;
                case '*':
                    st.push(op1 * op2);
                    break;  
                case '/':
                    st.push(op1 / op2);
                    break;
                case '^':
                    st.push(pow(op1, op2));
                    break;      
                default:
                    cout << "Invalid operator: " << str[i] << endl;
                    return 0;
            }
        }
    }
    return st.top();
}
                    
int main() {
    string str = "7425/+7*";
    int result = evaluatePostfixExpression(str);
    cout << "The result of the postfix expression is = " << result << endl;
    return 0;
}

//Output - The result of the postfix expression is = 28

Differences between Infix, Prefix, and Postfix Expressions

The key differences between Infix, Prefix, and Postfix Expressions are.

Aspect	Infix Notation	Prefix Notation (Polish Notation)	Postfix Notation (Reverse Polish Notation)
Readability	Easy for humans to understand	Less human-readable, requires familiarity	Less human-readable, requires familiarity
Operator Placement	Between operands	Before operands	After operands
Parentheses Requirement	Frequently necessary	Not necessary	Not necessary
Precedence Handling	Requires tracking via parentheses	Fixed precedence	Fixed precedence
Evaluation Method	Evaluated Left-to-right	Evaluated Right-to-left	Evaluated Left-to-right
Ambiguity Handling	It may require explicit parentheses	Ambiguity rare, straightforward evaluation	Ambiguity rare, straightforward evaluation
Unary Operator Handling	Complex placement	Simplified due to explicit notation	Simplified due to explicit notation
Computer Efficiency	Less efficient due to precedence and parentheses	More efficient due to fixed precedence	More efficient due to fixed precedence
Usage	Widely used in math	Common in computer science and programming	Common in computer science and programming

Conclusion

Infix, prefix, and postfix denote three ways in which expressions can be written and evaluated. Though humans find it quite natural and intuitive to read and write an expression in infix, regarding computational issues, it is quite efficient and useful to write expressions in prefix or postfix notation in order to develop computer programs that are used for the manipulation of expressions. Because we can easily evaluate the postfix expressions using a stack data structure, postfix expressions are appropriate for the implementation of some algorithms.