Infix To Postfix Conversion using Stack in C++

Infix To Postfix Conversion

In the process of Infix To Postfix Converting using Stack in C++, we will use the stack data structure. By scanning the infix expression from left to right, when we will get any operand, simply add them to the postfix form, and for the operator and parenthesis, add them in the stack maintaining the precedence of them.

C++ code for infix to postfix conversion

Basic:-

  • Infix Expression: The operator is in between the two operands like B * D is known as infix expression.
  • Postfix Expression: The operator is after the two operands like B D + is known as postfix expression.

Steps needed for infix to postfix conversion using stack in C++:-

1. Search the Infix string from left to right.

2. Initialize a vacant stack.

3. If the scanned character is an operand add it to the Postfix string.

4. When the scanned character is an operator and if the stack is empty push the character to stack.

5. If a scanned character is an Operator and the stack is not empty, compare the precedence of the character with element on top of the stack.

6. When top Stack has higher precedence over the scanned character pop the stack else push the scanned character to stack. Repeat this procedure till the stack is not empty and top Stack has precedence over the character.

7. Reiterate 4 and 5 steps till all characters are scanned.

8. After all characters are scanned, we have to add any character that the stack may have to the Postfix string.

9. When stack is not empty add top Stack to Postfix string and Pop the stack.

10. Repeat the process as long as stack is not vacant.

Infix to postfix conversion in C++

Postfix expression over infix expression

  • In postfix any formula can be expressed without parenthesis.
  • It is very useful for evaluating formulas on computers with stacks.
  • Infix operators have precedence.

Infix To Postfix Conversion using Stack in C++

// C++ Program infix to postfix expression using stack (array) in data structure
#include<iostream>
#include<string>
#define MAX 20
using namespace std;

char stk[20];
int top=-1;
// Push function here, inserts value in stack and increments stack top by 1
void push(char oper)
{
    if(top==MAX-1)
    {
        cout<<"stackfull!!!!";
    }
   
    else
    {
        top++;
        stk[top]=oper;
    }
}
// Function to remove an item from stack.  It decreases top by 1
char pop()
{
    char ch;
    if(top==-1)
    {
        cout<<"stackempty!!!!";
    }
    else
    {
        ch=stk[top];
        stk[top]='\0';
        top--;
        return(ch);
    }
    return 0;
}
int priority ( char alpha )
{
    if(alpha == '+' || alpha =='-')
    {
        return(1);
    }
 
    if(alpha == '*' || alpha =='/')
    {
        return(2);
    }
 
    if(alpha == '$')
    {
        return(3);
    }
 
    return 0;
}
string convert(string infix)
{
    int i=0;
    string postfix = "";   
    while(infix[i]!='\0')
    {       
        if(infix[i]>='a' && infix[i]<='z'|| infix[i]>='A'&& infix[i]<='Z')          
        {
            postfix.insert(postfix.end(),infix[i]);
            i++;
        }       
        else if(infix[i]=='(' || infix[i]=='{'  || infix[i]=='[')
        {
            push(infix[i]);
            i++;
        }        
        else if(infix[i]==')' || infix[i]=='}'  || infix[i]==']')
        {
            if(infix[i]==')')
            {
                while(stk[top]!='(')
                {               postfix.insert(postfix.end(),pop());
                }
                pop();
                i++;
            }
            if(infix[i]==']')
            {
                while(stk[top]!='[')
                {
                    postfix.insert(postfix.end(),pop());
                }
                pop();
                i++;
            }
 
            if(infix[i]=='}')
            {
                while(stk[top]!='{')
                {
                    postfix.insert(postfix.end(),pop());
                }
                pop();
                i++;
            }
        }
        else            
        {
            if(top==-1)
            {
                push(infix[i]);
                i++;
            }
 
            else if( priority(infix[i]) <= priority(stk[top])) {
                postfix.insert(postfix.end(),pop());
               
                while(priority(stk[top]) == priority(infix[i])){
                    postfix.insert(postfix.end(),pop());
                    if(top < 0) {
                        break;
                    }
                }
                push(infix[i]);
                i++;
            }
            else if(priority(infix[i]) > priority(stk[top])) {
                push(infix[i]);
                i++;
            }
        }
    }
    while(top!=-1)
    {
        postfix.insert(postfix.end(),pop());
    }
    cout<<"The converted postfix string is : "<<postfix; //it will print postfix conversion  
    return postfix;
}

int main()
{
    int cont;
    string infix, postfix;
    cout<<"\nEnter the infix expression : "; //enter the expression
    cin>>infix;
    postfix = convert(infix);
    return 0;
}
Output:-
Enter the infix expression : a=b*2+5
The converted postfix string is : ab*=+25