Infix to Postfix Conversion Using Stack in C++

Last Updated on May 31, 2023 by Prepbytes

An expression can be represented using the notations Infix, Prefix, and Postfix. Every notation corresponds to the same expression when written in a different way. Using the stack data structure, changing from one notation to another is comparatively easy. Let’s explore Infix and Postfix notations in more detail in this post and discover how to convert Infix to Postfix.

There are three different notations—or ways to write an expression with operators, operands, and brackets—depending on the placement of the operators and operands: infix notation, postfix notation, and prefix notation. While postfix notation is simpler for a computer, like a calculator, to evaluate, infix notation is simpler for us to read. This is due to the fact that in a postfix operation, operators are evaluated sequentially from left to right, negating the requirement for brackets and clearing up any doubt regarding operator precedence. In the parts that follow, we shall study more about them in depth.

What is Infix Notation?

Infix notation is a method of writing mathematical expressions where the operators are placed between the operands. It is the most commonly used notation in mathematics and everyday arithmetic. For example, the expression "2 + 3" is written in infix notation, where the plus sign (+) is placed between the operands 2 and 3.

Syntax of Infix Notation

The syntax of infix notation is X op Y.

Example – The ‘+’ operator would be placed between the operands 3 and 4 if we wanted to add the numbers 3 and 4. Infix notation will therefore be 3 + 4.

Problem with Infix Notation

Why do we need different notations for creating expressions, you might be wondering. Although infix notation is easy for us to read, it frequently contains some ambiguity for the following reasons: When assessing an expression, there are two primary aspects taken into account:

Operator precedence – This is the order in which each operator in an expression is given priority.

Associativity– Associativity is used to decide the evaluation order when two operators have the same precedence.

Parentheses are the only method that infix notation addresses the aforementioned issues.
Thus, it became necessary to create notations that would not allow for any ambiguity, would do away with the requirement for operator precedence and associativity constraints, and would greatly simplify the parsing of expressions.

What is Postfix Expression?

The kind of notation known as Postfix Expression, also referred to as Reverse Polish Notation, places the operator after the operand. For instance, if the infix expression is x + y, the postfix notation for that expression is x y +. The process of converting infix to postfix expressions will be thoroughly covered.

Since postfix expressions are simpler to evaluate and without overhead brackets, they are seen as superior than infix expressions.

Conversion of Infix to Postfix

Understanding how to switch between different notations is crucial. We will walk through the process of changing from infix to postfix in this section. For the conversion described above, a stack data structure will be used. We can transform expressions that contain operators, operands, and brackets (‘(‘). All of these will be taken into account when converting the expression.

Rules for the Conversion from Infix to Postfix Expression

We are initially given an infix expression to translate into postfix notation. After being parsed from left to right, the infix notation is changed to postfix. Assuming the postfix expression is initially empty, the following steps will be used to fill it out:

• Initialize an empty stack and an empty string for the postfix expression.
• Scan the infix expression from left to right.
• If the scanned character is an operand (number or variable), append it to the postfix string.
• If the scanned character is an open parenthesis ‘(‘, push it onto the stack.
• If the scanned character is an operator (+, -, *, /, etc.), do the following:
  • a. While the stack is not empty and the top of the stack is an operator with higher or equal precedence to the current operator, pop operators from the stack and append them to the postfix string.
  • b. Push the current operator onto the stack.
• If the scanned character is a close parenthesis ‘)’, do the following:
  • a. Pop operators from the stack and append them to the postfix string until an open parenthesis is encountered (and discard the open parenthesis).
• Repeat steps 3-6 until all characters in the infix expression have been scanned.
• Pop any remaining operators from the stack and append them to the postfix string.
• The resulting string in the postfix notation is the desired output.

Infix Expression:

K + L - M*N + (O^P) * W/U/V * T + Q

Let’s perform a dry run of the aforementioned infix expression to determine the appropriate postfix expression.
Left to right parsing is used for the string above. The table below shows, for each token, the elements in the stack and the corresponding postfix expression up to that point:

The final postfix expression is

KL+MN∗−OPW∗U/V/T∗+Q+

Explanation of the above table:
Since we have an operand (K) in step 1, we are attaching our postfix operation to it. After that, we run into the operator (+) and make sure our stack is empty. The operator is pushed into our stack. We then come across a different operand (L) and add it to our postfix operation. Our postfix expression now contains KL after step 3, and our stack now contains +. The next element is (-), and we verify that +, which has equal precedence as (-), is at the top of the stack. As a result, we create (+) and add it to our equation, which now reads KL+. Since there is nothing inside the stack, (-) enters the stack. Up to the final component of our infix expression, we keep doing this. Refer to the rules for conversion outlined in the preceding section to understand why an element is being added to the postfix expression, the stack, or pushed out of the stack.

Code Implementation

#include 
using namespace std;

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

//Function check whether the given character is Operand or not
bool isOperand (char c) {
    if ((c >= 'a' && c = 'A' && c = '0' && c <= '9')) {
        return true;
    }
    return false;
}

//Function for converting a infix expression to postfix expression
string infixToPostfix (string s) {
    stack st; 
    string postFix;

    for(int i = 0; i < s.length(); i++) {
        if (isOperand(s[i])) {
            postFix += s[i];
        }
        else if (s[i] == '(') {
            st.push('(');
        }
        else if (s[i] == ')') {
            while(st.top() != '(') {
                postFix += st.top();
                st.pop();
            }
            st.pop();
        }
        else {
            while (!st.empty() && precedence(s[i]) <= precedence(st.top())) {
                postFix += st.top();
                st.pop();
            }
            st.push(s[i]);
        }
    }

    while (!st.empty()) {
        postFix += st.top();
        st.pop();
    }

    return postFix;
}



int main()
{
    string exp = "a+b*(c^d-e)^(f+g*h)-i";
  
    // Function call
    cout<<infixToPostfix(exp);
    
    return 0;
}

Output

abcd^e-fgh*+^*+i-

Time Complexity: O(N), where N is the size of the infix expression
Auxiliary Space: O(N), where N is the size of the infix expression

Conclusion
In conclusion, converting an infix expression to postfix notation using a stack is a common and efficient approach in computer science and mathematics. By following the outlined steps and utilizing a stack data structure, we can successfully transform the infix expression into a postfix expression. This conversion simplifies the evaluation of mathematical expressions by removing the need for parentheses and ensuring the correct order of operations.

Implementing the infix to postfix conversion algorithm in C++ involves scanning the infix expression character by character and making use of a stack to handle operators and parentheses. By appending operands to the postfix string and using the stack to handle operators based on their precedence, we can construct the equivalent postfix expression.

FAQ’s

Q1: Are there any libraries or functions in C++ that can help with infix to postfix conversion?
Ans. C++ does not have a built-in function specifically for infix to postfix conversion. However, you can use standard string manipulation and stack operations to implement the algorithm. The < stack > header provides the necessary functionalities to handle the stack, while the < string > header can be used for string manipulation operations.

Q2. Are there any special considerations or edge cases to handle during infix to postfix conversion?
Ans. When implementing infix to postfix conversion, it’s important to consider operator precedence and associativity. Ensure that operators with higher precedence are placed before operators with lower precedence in the postfix expression. In case of equal precedence, the associativity (left-to-right or right-to-left) should be taken into account.

Q3: What is the purpose of converting infix expressions to postfix notation using a stack in C++?
Ans. Converting infix expressions to postfix notation using a stack in C++ is useful for simplifying the evaluation of mathematical expressions. Postfix notation eliminates the need for parentheses and ensures the correct order of operations. By converting infix expressions to postfix, you can easily evaluate them using a stack or other methods.