Friday, 22 September 2017

C Program to Convert Infix Expression into Postfix

C Program to convert infix expression into postfix expression along with algorithm is given below.


ALGORITHM:

1. For i in range 0 to length(string)-1:
2.       If the scanned operator is character then output it.
3.       else:
3.1          If the precedence of the scanned operator is greater than the 
             precedence of the operator in the stack(or the stack is empty),
             push it.
3.2          Else, Pop the operator from the stack until the precedence of 
             the scanned operator is less-equal to the precedence of the operator 
             residing on the top of the stack. Push the scanned operator to the 
             stack.
4.       If scanned character is '(' Push it to stack.
5.       If the scanned character is an ‘)’, pop and output from the stack 
         until an ‘(‘ is encountered.
6.       Repeat the steps 2 to 6 until the infix expression is scanned.
7.       Pop out the stack and output it.


PROGRAM:

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std; 
int Prec(char ch)
{
   switch(ch)
   {
        case '+':
        case '-':
               return 1;
        case '*':
        case '/':
               return 2;
        case '^':
               return 3;
   }
   return -1;
}
bool check_precedence(char ch,stack<char> &st)
{
      if(st.empty())
      {
           return true;
      }
      if(st.top()=='(')
      {
          return true;
      }
   int pre_ch=Prec(ch);
   int pre_st=Prec(st.top());
   if(pre_ch<=pre_st)
   {
       return false;
   }
   else
   {
       return true;
   }

}
string infixtopostfix(string s)
{
   std::stack<char> st;
   string s2="";
   for(int i=0;i<s.size();i++)
   {
         if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z'))
         {
                 s2=s2+s[i];
         }
         else if(s[i]=='(')
         {
               st.push(s[i]);
         }
         else if(s[i]==')')
         {
               while(st.top()!='(')
               {
                        s2=s2+st.top();
                        st.pop();
               }
               st.pop();
         }
         else
         {
                bool result=check_precedence(s[i],st);
                if(result)
                {
                     st.push(s[i]);
                }
                else
                {
                     while(!check_precedence(s[i],st))
                     {
                           s2=s2+st.top();
                           st.pop();
                     }
                     st.push(s[i]);
                }
         }
   }
   while(!st.empty())
   {
       s2=s2+st.top();
       st.pop();
   }
   return s2;
}
int main()
{
   int t;
   cout<<"\n\nEnter the number of test cases:\n";
   cin>>t;
   while(t--)
   {
        std::string s;
        cout<<"\n\nEnter the string:\n";
        cin>>s;
        string result=infixtopostfix(s);
        cout<<"\nThe postfix expression is: \n";
        cout<<result;
        cout<<"\n";
   }
   return 0;
}


OUTPUT:





EmoticonEmoticon