/* 15. Write a program in C++ to accept two Polynomials and perform addition and 
Subtraction operations on them */

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

struct node
{
    int coef,px,py;
    struct node*link;
};

typedef struct node*NODE;

class polynomial
{
    private:
        NODE first;
    public:
        polynomial();
        void readpoly(int n);
        NODE insert(NODE first,int coef,int px,int py);
        friend void addsub(polynomial p1,polynomial p2,polynomial &p3,polynomial &p4);
        friend ostream&operator<<(ostream&print,polynomial p);                                                        };

polynomial::polynomial()
{
    first=NULL;
}

void polynomial::readpoly(int n)
{
    int coef;
    for(int i=n;i>=0;i--)
    {
        cout<<"\n enter the coefficient of x^"<<i<<"y^"<<i<<":";
        cin>>coef;
        first=insert(first,coef,i,i);
    }
}

NODE polynomial::insert(NODE first,int coef,int px,int py)
{
    NODE temp,newnode;
    newnode=new node;
    newnode->coef=coef;
    newnode->px=px;
    newnode->py=py;
    if(first==NULL)
    {
        first=newnode;
        newnode->link=NULL;
    }
    else
    {
        temp=first;
        while(temp->link!=NULL)
            temp=temp->link;
        temp->link=newnode;
        newnode->link=NULL;
    }
    return first;
}

void addsub(polynomial p1,polynomial p2,polynomial &p3,polynomial &p4)
{
    NODE temp1,temp2;
    int sum,dif;
    temp1=p1.first;
    temp2=p2.first;
    while(temp1!=NULL)
    {
        if(temp1->px==temp2->px)
        {
            sum=temp1->coef+temp2->coef;
            dif=temp1->coef-temp2->coef;
            if (sum)
                p3.first=p3.insert(p3.first,sum,temp1->px,temp1->py);
            if (dif)
                p4.first=p4.insert(p4.first,dif,temp1->px,temp1->py);
            temp1=temp1->link;
            temp2=temp2->link;
        }
        else if((temp1->px)>(temp2->px))
        {
            p3.first=p3.insert(p3.first,temp1->coef,temp1->px,temp1->py);
            p4.first=p4.insert(p4.first,temp1->coef,temp1->px,temp1->py);
            temp1=temp1->link;
        }
        else if((temp2->px)>(temp1->px))
        {
            p3.first=p3.insert(p3.first,(temp2->coef),temp2->px,temp2->py);
            p4.first=p4.insert(p4.first,-(temp2->coef),temp2->px,temp2->py);
            temp2=temp2->link;
        }
    }    
}

ostream&operator<<(ostream&print,polynomial p)
{
    NODE temp;
    temp=p.first;
    while(temp!=NULL)
    {
        print<<" "<<temp->coef<<"x^"<<temp->px<<"y^"<<temp->py<<" ";
        if (temp->link != NULL)
        {
            if (temp->link->coef > 0)
            cout<<"+";
        }
        temp=temp->link;
    }
    return print;
}

void main()
{
    polynomial p1,p2,p3,p4;
    int n;
    cout<<"\n enter the degree of the first polynomial:";
    cin>>n;
    p1.readpoly(n);
    cout<<"\n enter the degree of the second polynomial:";
    cin>>n;
    p2.readpoly(n);
    addsub(p1,p2,p3,p4);
    cout<<"\n-------------------------------------------";
    cout<<"\n sum of the 2 polynomials is:";
    cout<<p3;
    cout<<"\n-------------------------------------------";
    cout<<"\n difference is:";
    cout<<p4;
    getch();
}