C++ program to convert infix to postfix

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.

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 stack to solve the problem. Let us jump to the code and then we will understand the code.

Code (Infix to Postfix)

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.

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 *