Welcome to W3Courses
 Like Us on Facebook

Infix to Postfix Source Code in C++

Following is the Infix to Postfix Source Code

#include <iostream.h>
#include <stdio.h>
#include <ctype.h>
typedef char data;

template <class Item>
class QUEUE
{
 private:
        struct node
        {
                     Item item; node *next;
                     node(Item x)
                    {
                  item=x; next=0;
                      }
            };

            typedef node *link;
            link head, tail;

 void deletelist()
{
            for(link t=head;t!=0;head=t)
           {
              t=head->next;
             delete head;
           }
  }

 public:
            QUEUE(int)
            {
              head=0;       
             }
  
 QUEUE(const QUEUE& rhs)
  { head=0; *this=rhs;}
 
~QUEUE()
 {
  deletelist();
 }
 QUEUE& operator=(const QUEUE& rhs)
  {
  if(this==&rhs)
 return *this;
 deletelist();
            link t=rhs.head;
 while(t!=0)
 {
             put(t->item);
  t=t->next;
  }
 return *this;
        }

        int empty() const
        {
         return head==0;
        }

        void put(Item x)
        {
         link t=tail;
          tail=new node(x);
          if(head==0)
             head=tail;
         else
t->next=tail;
        }

        Item get()
        {
          Item v=head->item;
          link t=head->next;         
          delete head;
          head=t;
          return v;
        }
 
        Item front()
        {
          return head->item;
         }
};

template<class Item>
class STACK
 {
    private:
 struct node
 {
  Item item;
  node *next;
  node(Item x, node* t)
           { item=x; next=t; }
 };
 typedef node *link;
 link head;

   public:
 STACK(int)
 {
 head=0;
 }
 
  int empty() const
 {
 return head==0;
 }
 
 void push(Item x)
  {
  head=new node(x,head);
  }

 Item pop()
  {
   Item v=head->item;
   link t=head->next;
   delete head;
   head=t;
   return v;
 }
 
 Item top()
 {
  return head->item;
 }
};

bool operator1(data x)    
 {
         if ((x == '=')||(x == '+')||(x == '-')||(x =='*')||(x == '^')||(x=='(')||(x==')')||(x=='/'))
                 return 1;
         else
                 return 0;
 }

 QUEUE<data> get_Qin(void)               
 {
         data ch;
         QUEUE<data> Qin(0);
         ch = getchar();
         while (ch != '\n')
         {
                 if (isalnum(ch)||operator1(ch)||(ch == '(')||(ch ==')'))
                         Qin.put(ch);
                 ch = getchar();
          }
          return (Qin);
 }

 int isp(data x)    //table for comparing operators
 {
         if (x == '=')
                 return 1;
         else if ((x == '+')||(x == '-'))
                 return 4;
         else if ((x == '*')||(x == '/'))
                 return 13;
         else if (x == '^')
                 return 16;
         else if (x == '(')
                 return 2;
 }

 int icp(data x)    //second table for comparing
 {
         if (x == '=')
                 return 2;
         else if ((x == '+')||(x == '-'))
                 return 3;
         else if ((x == '*')||(x == '/'))
                 return 11;
         else if (x == '^')
                 return 19;
         else if (x == '(')
                 return 1;
 }

 QUEUE<data> postfix(QUEUE<data> In)     // infix to postfix form
 
 {
         QUEUE<data> Qout(0);
         STACK<data> stack(0);
         while (!(In.empty()))
         {
                 if (isalnum(In.front()))
                         Qout.put(In.get());
                 else if (In.front() == '(')
                         stack.push(In.get());
                 else if (In.front() == ')')
                 {
                         Qout.put(stack.pop());
                         stack.pop();
                         In.get();
                 }
                 else if (operator1(In.front()))
                 {
                         if (stack.empty())
                                 stack.push(In.get());

                         else if (icp(In.front()) > isp(stack.top()))
                                 stack.push(In.get());
                         else
                                 Qout.put(stack.pop());
                 }
         }
         while (!stack.empty())
                         Qout.put(stack.pop());
         return Qout;
 }

void printQ(QUEUE<data> queue)   //prints the queue
 {
         while (!queue.empty())
                 cout<<queue.get();
         cout<<endl;
 }

 int main(int argc, char* argv[])
 {
         QUEUE<data> Out_queue(0);
         QUEUE<data> In_queue(0);
         cout<<"Type the Infix expression below"<< endl;
         In_queue = get_Qin();
         cout<<"The Postfix expression is "<< endl;
         Out_queue = postfix(In_queue);
         printQ(Out_queue);
         return 0;
 }
 


EXAMPLE USE
Type the Infix expression below
b*c+d
The Postfix expression is
bc*d+


Type the Infix expression below
c=a*(b+c)/d
The Postfix expression is
cabc+*d/=


Type the Infix expression below
a=b*c^f+(c-d)/s
The Postfix expression is
abcf^*cd-s/+=

Share