// Adding two polynomials
#include<iostream.h>
#include<conio.h>
class node
{ public:
   int coe,exp;
   node *next;
};
class polynomial
{
    public:
     void get_poly();
     void show();
     void add(polynomial p1,polynomial p2);
     node *start,*ptrn,*ptrp;
};
void polynomial::get_poly()      //  Get Polynomial
{
   char c='y';
   ptrn=ptrp=start=NULL;
   while(c=='y' || c=='Y')
   {
      ptrn=new node;
      ptrp->next=ptrn;
      if(start==NULL)
        start=ptrn;
      ptrp=ptrn;
      cout<<"	Coefficient: ";
      cin>>ptrn->coe;
      cout<<"	Exponent: ";
      cin>>ptrn->exp;
      ptrn->next=NULL;
      cout<<"Do you want to add ?(y/n):";
      cin>>c;
   }
}
void polynomial::show()  // Show Polynomial
{
    node *ptr;
    ptr=start;
    while(ptr!=NULL)
    {
       cout<<ptr->coe<<"X^"<<ptr->exp<<" + ";
       ptr=ptr->next;
    }
}
void polynomial::add(polynomial p1,polynomial p2)  // Add Polynomials
{
   node *p1ptr,*p2ptr;
   int coe,exp;
   ptrn=ptrp=start=NULL;
   p1ptr=p1.start;
   p2ptr=p2.start;
   while(p1ptr!=NULL && p2ptr!=NULL)
   {
      if(p1ptr->exp==p2ptr->exp) // If coefficients are equal
      {
	 coe=p1ptr->coe+p2ptr->coe;
	 exp=p1ptr->exp;
	 p1ptr=p1ptr->next;
	 p2ptr=p2ptr->next;
      }
      else if(p1ptr->exp > p2ptr->exp)
      {
	 coe=p1ptr->coe;
	 exp=p1ptr->exp;
	 p1ptr=p1ptr->next;
      }
      else if(p1ptr->exp < p2ptr->exp)
      {
	 coe=p2ptr->coe;
	 exp=p2ptr->exp;
	 p2ptr=p2ptr->next;
      }
      ptrn=new node;
      if(start==NULL)
	 start=ptrn;
      ptrn->coe=coe;
      ptrn->exp=exp;
      ptrn->next=NULL;
      ptrp->next=ptrn;
      ptrp=ptrn;
   } // End of While
   if(p1ptr==NULL)
   {
      while(p2ptr!=NULL)
      {
	 coe=p2ptr->coe;
	 exp=p2ptr->exp;
	 p2ptr=p2ptr->next;
	 ptrn=new node;
	 if(start==NULL)
	    start=ptrn;
	 ptrn->coe=coe;
	 ptrn->exp=exp;
	 ptrn->next=NULL;
	 ptrp->next=ptrn;
	 ptrp=ptrn;
      }
   }
   else if(p2ptr==NULL)
   {
      while(p1ptr!=NULL)
      {
	 coe=p1ptr->coe;
	 exp=p1ptr->exp;
	 p1ptr=p1ptr->next;
	 ptrn=new node;
	 if(start==NULL)
	    start=ptrn;
	 ptrn->coe=coe;
	 ptrn->exp=exp;
	 ptrn->next=NULL;
	 ptrp->next=ptrn;
	 ptrp=ptrn;
      }
   }
}
int main()
{
   polynomial p1,p2,sum;
   clrscr();
   cout<<"First Polynomial:\n";
   p1.get_poly();
   cout<<"Second polynomial:\n";
   p2.get_poly();
   cout<<"The First polynomial is: \n";
   p1.show();
   cout<<"\n The second polynomial is: \n";
   p2.show();
   cout<<"\n The sum of two polynomials is:\n ";
   sum.add(p1,p2);
   sum.show();
   getch();
   return 0;
}