C++ program to convert infix to postfix using stack

Hello. In this tutorial, we are going to learn how to convert an infix notation to postfix notation using the stack data structure in C++ program.

What are infix and postfix notations?

Infix and postfix are different ways to write mathematical operations. In infix notation we write the first operand, then we write the operator and then we write the second operator. For example x + y, x * y etc. In postfix notation, we write the first operand, followed by the second operand and then we write the operator. For example xy+, xy*.  There are two advantages of using a postfix notation over an infix notation. These are

  1. Postfix notation does not require parentheses, precedence rules and associative rules.
  2. We can evaluate the value of the expression in one traversal only.

While converting infix to postfix we use the associative and precedence rule of the operators (BODMAS) which we are familiar with from our school days.

Stack uses the concept of LIFO which means last in first out. This means that the last element in the stack gets popped that is deleted from the stack. The different operations used in the stack are as follows: push operation and pop operation. In a push operation, we try to add the elements inside the stack. While in the pop operation the elements will be deleted from the stack using the concept of LIFO(last in first out).

Let us understand the problem statement. We are given a string denoting infix notation and we need to convert it to its equivalent postfix notation. We are going to use a stack to solve the problem. Let us jump to the code and then we will understand the code.

Before going into the programming section we will try to solve one conversion manually and implement that concept using C++ code.

Priority table:

operator     priority

NOT        6
AND        5
OR         4
∧         3
*,/,%      2
+,-        1

Now we solve an infix expression by taking the above priority table as a reference, let us consider our infix expression is a*b/c-d+e now we need to convert this expression to postfix expression,

a*b/c-d+e
ab*/c-d+e
ab*c/-d+e
ab*c/d-+e
ab*c/d-e+

So the final postfix expression is ab*c/d-e+. So now we implement the conversion using the C++ program code and verify our answer.

C++ Code (Infix to Postfix using stack)

Below is our given C++ code to convert infix into postfix:

#include<bits/stdc++.h> 
using namespace std; 
int precedence(char m) 
{ 
  if(m == '^') 
  return 3; 
  else if(m == '*' || m == '/') 
  return 2; 
  else if(m == '+' || m == '-') 
  return 1; 
} 

void infix_to_postfix(string t) 
{ 
  stack<char> s;
  int l = t.length(); 
  string ans; 
  for(int i = 0; i < l; i++) 
  { 
    if((t[i] >= 'a' && t[i] <= 'z') || (t[i] >= 'A' && t[i] <= 'Z')) 
        ans+=t[i]; 

    else if(t[i] == '(') 
        s.push('('); 
        
    else if(t[i] == ')') 
    { 
      while(s.top() != '(') 
      { 
        char c = s.top(); 
        ans += c;
        s.pop(); 
           
      } 
      if(s.top() == '(') 
      { 
        char c = s.top(); 
        s.pop(); 
      } 
    } 
    else{ 
      while(s.empty()==false && precedence(t[i]) <= precedence(s.top())) 
      { 
        char c = s.top(); 
        ans += c; 
        s.pop(); 
      
      } 
      s.push(t[i]); 
    } 

  } 
  
  while(s.empty() == flase) 
  { 
    char c = s.top(); 
    ans += c; 
    s.pop(); 
    
  } 
  
  cout << ans << endl; 
}

int main() 
{ 
  string s = "a+b*c"; 
  infix_to_postfix(s); 
  return 0; 
} 
 

Output –

abc*+

We use the stack to store the operators. We traverse the string characters one by one. Let x be the character we are traversing. If x is :

  1. Operand: Directly add to the output string.
  2. Left parenthesis[“(“]: Push to the stack.
  3. Right parenthesis[“)”]: Pop the items one by one from the stack till we find left parenthesis. Output the popped characters.
  4. Operator: If the stack is empty then push x else compare the precedence of x with stack top. (1). If the precedence of x > precedence of stack top then push x. (2). Precedence of x < precedence of stack top, pop the stack top one by one and output until a lower precedence operator is found. Then push x to stack.

After this just pop the remaining items from stack one by one and append to the answer.

Another example:

Infix to postfix CPP program

#include<iostream>
using namespace std;
 char stack[20];
 int top=-1;
class infix_to_postfix
{
 public:
void push(char x)
{
    stack[++top]=x;
}
 char pop()
 {
    if(top==-1)
    {
       return -1;
    }
    else
    {
        return stack[top--];
    }
 }
  int priority(char x)
  {
    if(x=='(')
        return 0;
    if(x=='+' || x=='-')
        return 1;
    if(x=='*' || x=='/')
        return 2;
   }
};
 
int main()
{
    infix_to_postfix obj;
    char exp[20];
    char *e, x;
    cout<<"enter the infix expression:";
    cin>>exp;
    e=exp;
    cout<<"postfix expression is:";
    while(*e!='\0')
    {
        if(isalnum(*e))
            cout<<*e;
        else if(*e=='(')
            obj.push(*e);
        else if(*e==')')
        {
            while((x=obj.pop())!='(')
                cout<<x;
        }
        else
        {
            while(obj.priority(stack[top])>=obj.priority(*e))
                cout<<obj.pop();
            obj.push(*e);
        }
        e++;
    }
    while(top!=-1)
    {
        cout<<obj.pop();
    }
    return 0;
}

 

Hope you understood the code. Any doubts are welcomed in the comment section. Thank you.

Check out my other blogs-
Knuth-Morris-Pratt (KMP) Algorithm in C++

Leave a Reply

Your email address will not be published. Required fields are marked *