#include "iostream.h"
 class Term{
public:
Term(int c,int e);
Term(int c,int e,Term *nxt);
Term*InsertAfter(int c,int e);
private:
int coef;
int exp;
Term *link;
friend ostream & operator<<(ostream &,const Term &);
friend class Polynominal;
};
Term::Term(int c,int e):coef(c),exp(e){link=0;}
Term::Term(int c,int e,Term *nxt):coef(c),exp(e)
{
link=nxt;
}
Term *Term::InsertAfter(int c,int e)
{
link=new Term(c,e,link);
return link;
}
ostream &operator<<(ostream &out,const Term & val)
{
if(val.coef==0) return out;
out<<val.coef;
switch(val.exp){
case 0:break;
case 1:out<<"X";break;
default:out<<"X^"<<val.exp;break;
}
return out;
}
 
class Polynominal
{
public:
Polynominal();
~Polynominal(){};
void AddTerms(istream & in);
void Output(ostream &out) const;
void PolyAdd(Polynominal &r);
void operator =(Polynominal &r);
void PolyMul(Polynominal &r);
private:
Term* theList;
friend ostream &operator<< (ostream &,const Polynominal &);
friend istream &operator>> (istream &,Polynominal &);
friend Polynominal operator +(Polynominal &,Polynominal &);
friend Polynominal operator *(Polynominal &,Polynominal &);
};
Polynominal:: Polynominal()
{ 
theList=new Term(0,-1);
theList->link=theList;
}
void Polynominal::AddTerms (istream & in)
{
Term *q=theList;
int c,e;
for(;;)
{cout<<"Input a term (coef, exp) 注意：請按降序輸入，結(jié)束時輸入e為負(fù)值!:\n"<<endl;
in>>c;in>>e;
if(e<0)break;
q=q->InsertAfter (c,e);
}
}
void Polynominal::Output(ostream &out) const
{ 
int first=1;Term *p=theList->link ;
for(;p!=theList;p=p->link ){
if(!first&&(p->coef >0))out<<"+";first=0;
out<<*p;
}
cout<<"\n"<<endl;
}
void Polynominal::operator =(Polynominal &r)
{ 
Term *p1=theList,*p2=r.theList ;
while (r.theList !=theList)
{ while(p2->link->exp>=0)
{ p1=p1->InsertAfter(p2->coef,p2->exp);
p2=p2->link;
}
}
}
 
void Polynominal::PolyAdd(Polynominal &r)
{
Term *q,*q1=theList,*q2,*p;
p=r.theList ;
q=q1->link ;p=p->link ;
while(p->exp >=0){
while(p->exp <q->exp ){
q1=q;q=q->link ;
}
if(p->exp ==q->exp ){
q->coef =q->coef+p->coef ;
if(q->coef ==0){
q2=q;q1->link =q->link ;
q=q->link ;delete(q2);
p=p->link ;
}
else{
q1=q;q=q->link ;p=p->link ;
}
}
else {
q1=q1->InsertAfter (p->coef ,p->exp );
p=p->link ;
}
}
}
void Polynominal::PolyMul(Polynominal &r)
{
Polynominal a1,a2;
Term *q=theList->link,*p=r.theList ->link ,*pa1=a1.theList,*pa2=a2.theList;
int coef,exp;
while(q->exp >=0)
{ 
while(p->exp >=0)
{
exp =q->exp+p->exp;
coef=q->coef*p->coef ;
pa2=pa2->InsertAfter(coef,exp);
p=p->link;
}

q=q->link ;
p=r.theList->link ;
a1.PolyAdd (a2); 

a2.theList->link=a2.theList ;
pa2=a2.theList ; 
}
theList=a1.theList ;

}
ostream & operator<<(ostream &out,const Polynominal &x)
{x.Output (out);
return out;
}
istream &operator >>(istream &in, Polynominal & x )
{
x.AddTerms (in);
return in;
}
Polynominal operator +(Polynominal &a, Polynominal &b)
{
a.PolyAdd (b);
return a;
}
Polynominal operator*(Polynominal &a,Polynominal &b)
{ 
a.PolyMul(b);
return a;

}
void main()
{
char m;
do{
Polynominal p,q;
{
cout<<"*******************兩個多項式的算術(shù)運算程序*****************"<<endl;
cout<<"請您選擇： "<<endl;
cout<<" 1.兩個多項式相加; "<<endl;
cout<<" 2.兩個多項式相乘。 "<<endl;
cout<<" 注意: c,e從左至右輸入。 "<<endl;
cout<<"************************************************************"<<endl;


cin>>m;
switch(m)
{case '1':
cin>>p;cout<<"您輸入的第一個多項式是:\n"<<p;
cin>>q;cout<<"您輸入的第二個多項式是:\n"<<q;
q=q+p;
cout<<"兩個多項式相加的結(jié)果是:\n"<<q;
break;
case '2':
cin>>p;cout<<"您輸入的第一個多項式是:\n"<<p;
cin>>q;cout<<"您輸入的第二個多項式是:\n"<<q;
q=q*p;
cout<<"兩個多項式相乘的結(jié)果是:\n"<<q;
break;
default:cout<<"您的輸入不正確,請正確輸入!"<<endl;break;
}
cout<<"是否繼續(xù)運行本程序?(Y or N) \n";
cin>>m;
}
}
while(m=='y'||m=='Y');
}