#include<iostream>
#include<vector>
#include<list>
#include<string>
#include<cmath>
using namespace std;

/*************************class CNode declaration*************************/ 
class CNode{ 
	/*把CNode的內(nèi)容輸出到os*/
	friend ostream & operator << (ostream &os, const CNode& );
	/*CPolynomial的排序標(biāo)準(zhǔn)*/
	friend bool expnComp(const CNode & A,const CNode & B);
public: 
	/*缺省構(gòu)造函數(shù)*/
	CNode(){_coef = 0.0; _expn = 0;}; 
	CNode(double c, int e): _coef(c), _expn(e){ }; 
	~CNode(){}; 

	int expn() const {return _expn;}; 
	double coef() const {return _coef;}; 
private: 
	double _coef;	//多項式item的系數(shù)域 
	int _expn;	//多項式item的指數(shù)域 
}; 

ostream & operator << (ostream & os,const CNode & cp){
	if(cp._coef!=0 && cp._expn!=1)
		os<<cp._coef<<"x^"<<cp._expn;
	else if(cp._coef!=0 && cp._expn==1)
		os<<cp._coef<<"x";

	return os;
}

bool expnComp(const CNode & A,const CNode & B){
	if(A.expn()>B.expn())	return true;
	else return false;
}

/*************************class CPolynomial declaration*************************/ 
class CPolynomial { 
	/*2個多項式的+法*/ 
	friend CPolynomial operator+( const CPolynomial& A, const CPolynomial& B ); 
	/*按照項的指數(shù)遞減順序輸出一元稀疏多項式到os*/ 
	friend ostream& operator <<( ostream& os , const CPolynomial& ); 
public: 
	/*多項式對象的缺省構(gòu)造函數(shù)*/ 
	CPolynomial(){}; 
	/*用系數(shù)向量和指數(shù)向量構(gòu)造多項式*/ 
	CPolynomial(const vector<double>& , const vector<int>& ); 
	/*多項式的copy構(gòu)造函數(shù)*/ 
	CPolynomial(const CPolynomial& rpln); 
	/*釋放一元多項式占用的存儲空間*/ 
	~CPolynomial(); 
	/*將值代入多項式,計算多項式的值*/ 
	double operator()(double x) const; 
	/*多項式的賦值操作*/ 
	CPolynomial& operator=(const CPolynomial& rpln); 
	void print(); 
private: 
	list<CNode> _polyList; 
};
int find_pos(const vector<int>& expn_vec, int val);
//用系數(shù)向量和指數(shù)向量構(gòu)造多項式 
CPolynomial::CPolynomial(const vector<double>& coef, const vector<int>& expn){
	for(unsigned int i=0;i<expn.size();i++){
		double dval=coef[i];
		int val=expn[i]; 
		unsigned int temp=expn.size();
		for(unsigned int n=0;n<expn.size();n++){
			if(n=temp)  continue;
			int pos=find_pos(expn,val);
			if(pos!=i && pos!=expn.size()){
				dval=dval+coef[pos];
				temp=pos;
			}
		}
		CNode tempnode(coef[i],expn[i]);

		//將新生成的節(jié)點從鏈表頭部插入
		this->_polyList.push_back(tempnode);
		
		//將生成的一元多項式鏈表按指數(shù)進(jìn)行排序
		this->_polyList.sort(expnComp);
	}
}

int find_pos(const vector<int>& expn_vec, int val){
	int pos=expn_vec.size();
	for(unsigned int i=0;i<expn_vec.size();++i){
		if(expn_vec[i]==val){
			pos=i;
			return pos;
		}
	}
	return pos;
}


//釋放一元多項式占用的存儲空間
CPolynomial::~CPolynomial(){}; 

//多項式的copy構(gòu)造函數(shù)
CPolynomial::CPolynomial(const CPolynomial & rpln){
	//定義遍歷鏈表迭代子
	list<CNode>::const_iterator iter_r=rpln._polyList.begin();
	list<CNode>::const_iterator iter_re=rpln._polyList.end();

	//使用List賦值函數(shù)assign(begin(),end())對鏈表進(jìn)行拷貝
	this->_polyList.assign(iter_r, iter_re);
}

//將值代入多項式,計算多項式的值
double CPolynomial::operator ()(double x) const{
	double result=0;
	//定義遍歷鏈表迭代子
	list<CNode>::const_iterator iter=_polyList.begin();

	while(iter!=_polyList.end()){
		result+=iter->coef() * pow(x, iter->expn());
		iter++;
	}

	return result;
}

//多項式的賦值操作
CPolynomial& CPolynomial:: operator = (const CPolynomial &  rpln){
	//定義遍歷鏈表迭代子
	list<CNode>::const_iterator iter_r = rpln._polyList.begin();
	list<CNode>::const_iterator iter_re = rpln._polyList.end();

	while(iter_r!=iter_re){
		CNode tempnode(iter_r->coef(), iter_r->expn());

		(*this)._polyList.push_back(tempnode);
		iter_r++;
	}

	return (*this);
}

//重載多項式加法操作符
CPolynomial operator+( const CPolynomial& A, const CPolynomial& B ){
	double coef;
	int expn;
	CPolynomial CPSum;

	//定義遍歷鏈表迭代子
	list<CNode>::const_iterator iter_A=A._polyList.begin();
	list<CNode>::const_iterator iter_Ae=A._polyList.end();
	list<CNode>::const_iterator iter_B=B._polyList.begin();
	list<CNode>::const_iterator iter_Be=B._polyList.end();
	
	while((iter_A!=iter_Ae) && (iter_B!=iter_Be)){
		if(iter_A->expn() > iter_B->expn()){
			coef=iter_A->coef();
			expn=iter_A->expn();
			CNode newnode(coef,expn);

			CPSum._polyList.push_back(newnode);
			iter_A++;
		}
		else if(iter_A->expn() < iter_B->expn()){
			coef=iter_B->coef();
			expn=iter_B->expn();
			CNode newnode(coef,expn);

			CPSum._polyList.push_back(newnode);
			iter_B++;
		}
		else{
			coef=iter_A->coef()+iter_B->coef();
			expn=iter_A->expn();
			CNode newnode(coef,expn);

			CPSum._polyList.push_back(newnode);
			iter_A++;	iter_B++;
		}
	}

		//A鏈表還有剩余節(jié)點，直接接到結(jié)果鏈表后面
		while(iter_A!=iter_Ae){
			coef=iter_A->coef();
			expn=iter_A->expn();
			CNode newnode(coef,expn);

			CPSum._polyList.push_back(newnode);
			iter_A++;
		}
		//B鏈表還有剩余節(jié)點，直接接到結(jié)果鏈表后面
		while(iter_B!=iter_Be){
			coef=iter_B->coef();
			expn=iter_B->expn();
			CNode newnode(coef,expn);

			CPSum._polyList.push_back(newnode);
			iter_B++;
		}

	return CPSum;
}

ostream& operator <<( ostream& os , const CPolynomial& P){
	if(P._polyList.empty())
		cout<<"多項式不存在！";
	else{
		//定義遍歷鏈表迭代子
		list<CNode>::const_iterator iter_P=P._polyList.begin();
		list<CNode>::const_iterator iter_Pe=P._polyList.end();

		for(unsigned int i=0;i<P._polyList.size();i++){
			os<<(*iter_P);	//由于CNode中已重載了“<<”輸出多項式的項
											//此處無需再重復(fù)構(gòu)建
			++iter_P;		//指向下一項
			if(i!=(P._polyList.size()-1) &&  iter_P->coef()>=0)	os<<"+";	
																				//如果此項不是最后一項
																				//判斷并輸出符號
		}
		os<<endl;
	}

	return os;
}