#include<iostream>
using namespace std;
struct poly
{
  int cof;
  int pwr;
  poly *next;

};
poly *start1=NULL,*start2=NULL,*start3=NULL;
void menu();
void menu()
{
    cout<<"\n1.add element into first poly";
    cout<<"\n2.add element into second poly";
    cout<<"\n3.add  poly equation and create third";
    cout<<"\n4.display first poly";
    cout<<"\n5.display second poly";
    cout<<"\n6. display third poly";
    cout<<"\n7. exit";




}
poly * createElement()
{
    poly *t=new poly;
    cout<<"\nEnter cofficient value";
    cin>>t->cof;
    cout<<"\nEnter power value";
    cin>>t->pwr;
    t->next=NULL;
    return(t);
}

poly * addElement(poly *start)
{
    poly *temp=createElement();
    if(start==NULL)
    {
        start=temp;
    }
    else
    {
        poly *t=start;
        while(t->next!=NULL)
        {
            t=t->next;
        }
        t->next=temp;

    }
    return(start);

}
void displayPoly(poly *start)
{
        poly *t=start;
        cout<<"\n";
        while(t!=NULL)
        {
            cout<<t->cof<<"x^"<<t->pwr<<" + ";
            t=t->next;
        }
}
poly * addPoly(poly *s1,poly *s2)
{
      poly *s3=NULL;
      while(s1!=NULL || s2!=NULL)
      {
          poly *t=new poly;
          t->next=NULL;
          if(s1->pwr > s2->pwr)
          {
              t->cof=s1->cof;
              t->pwr=s1->pwr;
              s1=s1->next;
          }
          else if(s2->pwr > s1->pwr)
          {
              t->cof=s2->cof;
              t->pwr=s2->pwr;
              s2=s2->next;
          }
         else if(s1->pwr == s2->pwr)
          {
              t->cof=s1->cof + s2->cof;
              t->pwr=s1->pwr;
              s2=s2->next;
              s1=s1->next;
          }
          if(s3==NULL)
            s3=t;
          else
          {
              poly *temp=s3;
              while(temp->next!=NULL)
                temp=temp->next;
              temp->next=t;
          }

         if(s2==NULL)
         {
             poly *temp=s3;
              while(temp->next!=NULL)
                temp=temp->next;

            while(s1!=NULL)
            {
                poly *t=new poly;
               t->next=NULL;
               t->pwr=s1->pwr;
               t->cof=s1->cof;
               temp->next=t;
               temp=temp->next;
               s1=s1->next;

            }

           break;
         }

        if(s1==NULL)
         {
             poly *temp=s3;
              while(temp->next!=NULL)
                temp=temp->next;

            while(s2!=NULL)
            {
                poly *t=new poly;
               t->next=NULL;
               t->pwr=s2->pwr;
               t->cof=s2->cof;
               temp->next=t;
               temp=temp->next;
               s2=s2->next;

            }
           break;
         }



      }
  return(s3);
}


int main()
{
    int ch;
    while(ch!=7)
    {
        menu();
        cout<<"\nEnter your choice";
        cin>>ch;
        switch(ch)
        {
           case 1:
                  start1=addElement(start1);
                  break;
           case 2:
               start2=addElement(start2);
                  break;
           case 3:
                   start3=addPoly(start1,start2);
                   break;
           case 4:
                    displayPoly(start1);
                    break;
           case 5:
                    displayPoly(start2);
                    break;
           case 6:
                    displayPoly(start3);
                    break;
           case 9:
                 break;

        }

    }
}