// Polymul.cpp : 定義控制臺應用程序的入口點。
//

#include "stdafx.h"


int _tmain(int argc, _TCHAR* argv[])
{
	return 0;
}

#include<iostream>
using namespace std;

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:cout<<"X";break;
		default:out<<"X^"<<val.exp;break;
	}
	return out;
}

class Polynominal {
public:
	Polynominal();
	~Polynominal();                                          //析構函數
	Polynominal(const Polynominal &p);                      //復制構造函數
	void AddTerms(istream &in);
	void AddTerms(int c, int e);							//增加項
	void Output(ostream &out)const;
	void PolyAdd(Polynominal &r);
	Polynominal PolyMul(Polynominal&b);					  //用于進行乘法運算的成員函數
private:
	Term *theList;
	friend ostream &operator<<(ostream &, const Polynominal &);
	friend istream &operator>>(istream &, Polynominal &);
	friend Polynominal operator*(Polynominal &, Polynominal &);    //定義重載運算符*為友元類
};

Polynominal::Polynominal() {
	theList=new Term(0,-1);
	theList->link=theList;
}

Polynominal::Polynominal(const Polynominal& p){                 //調用復制構造函數為使乘法運算結果保存于另一個多項式中，這樣調用析構函數不存在訪問沖突
	theList=new Term(0,-1);
    theList->link=theList;
	Term* q =theList;
	Term* r =p.theList->link;
	while(r!=p.theList){
		q=q->InsertAfter(r->coef,r->exp);
		r=r->link;
	}
}

Polynominal::~Polynominal() {                            //析構函數
		Term *m,*n;
		for(m=this->theList->link;m->exp>=0;) {        //釋放多項式所有節點的空間 
			n=m;
			m=m->link;
			delete(n);
		}
		delete(m);
}

void Polynominal::AddTerms(istream &in) {
	Term *q=theList;
	int c,e;
	for(;;) {
		cout<<"Input a term(coef,exp):"<<endl;
		in>>c>>e;
		if(e<0)break;
		q=q->InsertAfter(c,e);
	}
}

void Polynominal::AddTerms(int c, int e) {				//AddTerms實現
	Term *q=theList;
	q=q->InsertAfter(c,e);
}

void Polynominal::Output(ostream &out) const {
	int first=1;
	Term *p=theList->link;
	cout<<"The polynominal is:"<<endl;
	for(;p!=theList;p=p->link) {
		if(!first&&(p->coef>0)) out<<"+";
		first=0;
		out<<*p;
	}
	cout<<"\n"<<endl;
}

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;
		}
	}
}

Polynominal Polynominal::PolyMul(Polynominal &b) {				 //雖然是傳引用，但函數體中沒有改變b的值，只是使用了。
	Polynominal z;										        //z用于保存相乘的結果，而不是修改當前多項式來保存結果。
	Term *t,*m;
	for(t=this->theList->link;t->exp>=0;t=t->link) {
		Polynominal r;											//r為臨時的多項式，用于保存第一個多項式的每一項和第二個多項式相乘的結果
		for(m=b.theList->link;m->exp>=0;m=m->link) {
			r.AddTerms((t->coef)*(m->coef),(t->exp)+(m->exp));	//系數相乘，指數相加
		}
		z.PolyAdd(r);                                         //將臨時多項式累加到表示最終結果的多項式里去
	}
	return Polynominal(z);                                   //結果返回
}

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,b的值，只是使用了。
	return Polynominal(a.PolyMul(b));
}

int main() {
	Polynominal p,q;
	int a;
	cout<<"Please input the first polynominal:"<<endl;				//根據輸入創建第一個多項式
	cin>>p;cout<<p;
	cout<<"Please input the second polynominal:"<<endl;				//根據輸入創建第二個多項式
	cin>>q;cout<<q;
	cout<<"working on multiplication..."<<endl;
	cout<<q*p;								                     //輸出兩個多項式相乘的結果	
	getchar();
	getchar();
}