#include<iostream.h>
#include<string.h>
#include<stdio.h>
#include<math.h>
class multinomial;
class term
{
friend class multinomial;
	int ceof;
	int exp;
	term *next;
};
class multinomial
{
  public:
	  multinomial();
	  insert(term *ps);//插入項
	  del();//刪除結點
	  input();//輸入多項式,并把多項式存放到鏈表中
	  del_zero();//清鏈,把多項式中系數為零的相刪除掉;
	  term *getMax();//找到多項式中有最大指數的項
	  multinomial add(multinomial b);//加法
	  multinomial sub(multinomial b);//減法
      multinomial term_mul_poly(term *b);//項與多項式相乘，為乘法做準備
	  multinomial multiply(multinomial b);//乘法
	  void divide(multinomial &a);//除法
	  output();//輸出多項式
	  int iszero();

 private:
	  int termnumber;
	  term *newterm;//用于指向新建結點，引導其插入多項式中
	  term *head,*end;//頭指針、末指針
	  term *first;//頭結點，不放數據，用以簡化插入、刪除操作
};
multinomial::multinomial()//構造
{  	
	first=new term;
	first->ceof=first->exp=0;
	head=first;	
	first->next=NULL;
	end=first;
	termnumber=0;

}
multinomial::del_zero()//把鏈表中的零項清除掉
{
	term *p=first;
	for(;p->next;p=p->next)
	{
		for(;(p->next!=NULL)&&(p->next->ceof==0);)
		{
			newterm=p->next;
			p->next=newterm->next;
			delete newterm;
		}
		if(p->next==NULL) break;
	}
}
multinomial::insert(term *ps)//插入項
{
  if(first->next==NULL)//當多項式是空時,插入first后面
	{
      ps->next=first->next;
	  first->next=ps;
	  end=ps;
	}
  else
  {
   for(term *guard=first->next;guard;guard=guard->next)//按指數的大小從大到小插入
	{
	   if(guard->exp==ps->exp)//如果插入項的指數與多項式中某一項指數相等,系數相加就可以了
	   {
		   guard->ceof+=ps->ceof;
		   break;
	   }
	   if(guard->exp>ps->exp&&guard->next==NULL)//如果插入項的指數小于最后一項的指數,插到后面
	   {
            ps->next=guard->next;
			guard->next=ps;
			end=ps;
			break; 
	   }
	   if(guard->exp>ps->exp&&guard->next->exp<ps->exp)//插到中間適當位置
		{
			ps->next=guard->next;
			guard->next=ps;
			break;
	   }  	  
	   if(guard->exp<ps->exp)//如果插入項指數是最大的，插到最前面
	   {
		   ps->next=first->next;
		   first->next=ps;
		   break;
	   }
	   
	}
  }
}
term *multinomial::getMax()//取具有最大指數的項
{
	term *p=first->next,*q=first;
	for(;p;p=p->next)
		if(p->exp>=q->exp) q=p;	
	return q;
}
multinomial::input()//輸入函數,把輸入的多項式系數、指數辨認出來，存到多項式類中
{
    cout<<"(X表示變量，常數項后面要加X^0,回車結束輸入):"<<endl;
	char poly[100];	
	char *p=gets(poly);
    
	newterm=new term;
	newterm->ceof=newterm->exp=0;
	int len=strlen(p);

	for(int j=0;j<=len;j++)
		if(p[j]=='^') termnumber++;
	int mark=0,ceofmark=0,sign=1;
	for(j=0;j<=len;j++,p++)
	{
		if((*p>='0')&&(*p<='9'))
		{
			if(mark==0)
			{
				ceofmark*=10;
				ceofmark+=sign*(*p-'0');
			}
			if(mark==1)
			{
				newterm->exp*=10;
				newterm->exp+=sign*(*p-'0');
			}
		}
		if(*p=='x'||*p=='X')
		{
			if(*(p-1)=='+'||(*(p-1)=='-')||j==0) ceofmark=sign;
			newterm->ceof=ceofmark;
			mark=1;
			ceofmark=0;
			sign=1;
		}
		if((*p=='+')||(*p=='-')||(*p=='\0'))
		{
            if(*(p-1)=='x'||*(p-1)=='X') 
			{
				newterm->exp=1;
			}		
			if(j!=0)
			{
			 insert(newterm);
             newterm=new term;
		     termnumber++;
			  newterm->exp=newterm->ceof=0;				
			}
			mark=0;
			if(*p=='-')  
			sign=-1;
			else sign=1;	
		}
	} 
	del_zero();
}
multinomial::output()//輸出
{ 
	if(first->next==NULL) cout<<'0';
	else 
	{
	int i=0;//用于標示是否是要輸出的第一項，因為第一項的系數如果是正的話不用輸出'+'號
	term *p=first->next;
	//cout<<"p->next->ceof="<<p->ceof<<endl;
	for(;p;p=p->next)
	{  
			i++;//i為要輸出的第一項，前面不用加'+"號
 	   	if((p->ceof)>0)
		{   
		   if(i==1) 
		   {
			   if(p->ceof==1);
			   else
				   cout<<p->ceof;
		   }
			else
			{
			  if(p->ceof==1) cout<<'+';			               
			       else
				cout<<'+'<<p->ceof;
			}
		}
		else
		{
	    	if(p->ceof==-1) cout<<'-';
					else if(p->ceof!=0) cout<<p->ceof;
		}
		if(p->ceof!=0) cout<<'X'<<'^'<<p->exp;
	}
	}
}
multinomial multinomial::add(multinomial b)//加法(把a加到b中，返回b)
{ 
	newterm=new term;
	term *guard=b.first->next,*q=first->next;
	int mark; //用于標示是否找到指數相同的接結，若有，則系數相加，否則，建一個新結點
	for(;q;q=q->next)
	{
		guard=b.first->next;//指示指針志指向頭結點
		mark=0;
		for(;guard;guard=guard->next)
		{  
		  
		   if(guard->exp==q->exp)
		   { 
			   
			    guard->ceof=q->ceof+guard->ceof;
			    mark=1;
		   }
		}
		if(mark==0)
		{
		   newterm->ceof=q->ceof;
		   newterm->exp=q->exp;
		   b.insert(newterm);
           newterm=new term;
		}
		//cout<<"mark"<<endl;
		//b.output();
	}
	return b;
}
multinomial multinomial::sub(multinomial b)//減法(把b變為-b，然后加a)
{  
    newterm=new term;
	term *guard=(b.first)->next,*q=first->next;
	for(;guard;guard=guard->next)
		guard->ceof=-guard->ceof;
	multinomial result=add(b);
	return result;
}
multinomial multinomial::term_mul_poly(term *b)//項與多項式相乘，其為乘法的基礎
{
	multinomial result;
    newterm=new term;
	term *guard=first->next;
	for(;guard;guard=guard->next)
	{
		newterm->ceof=(guard->ceof)*(b->ceof);
		newterm->exp=guard->exp+b->exp;
		//cout<<"newterm->exp"<<newterm->exp;   //此為編程過程中的測試語句，用于輸出過程中的
        //cout<<"newterm->ceof"<<newterm->ceof; //結果，以便出現錯誤時分析錯誤原因，下同。
		result.insert(newterm);
		newterm=new term;
	}
	return result;

}
multinomial multinomial::multiply(multinomial b)//乘法
{	
	multinomial r;
    if(first->next==NULL||(b.first)->next==NULL)
		 cout<<"error!";
	else
	{
	    term *guard=(b.first)->next; 
		r=term_mul_poly(guard);	
		//cout<<(b.first)->next->exp;
      	for(guard=guard->next;guard;guard=guard->next)
		{
	       r=r.add(term_mul_poly(guard));
		}
	}
	return r;
}
void multinomial::divide(multinomial &a)//除法
{
	if(first->next==NULL) cout<<"Error!!除數多項式不能為零!";
	else
	{
	multinomial quot,remain=a;
	newterm=new term;
	term *A,*B;
	A=a.getMax();
	B=getMax();
	
   if(B->exp>A->exp)//如果除數最高指數大于被除數的最高指數，則商為零，余數等于被除數 
	{
		cout<<"多項式相除結果為:商:"<<'0'<<'\t';
		cout<<"余項:";
		a.output();
	}
    else
	{
	 for(;A->exp>=B->exp;)//如果除數最高指數大于被除數的最高指數，則繼續求商所含的項
	  {
          newterm->ceof=A->ceof/B->ceof;
	      newterm->exp=A->exp-B->exp;
	      quot.insert(newterm);
	      remain=remain.sub(term_mul_poly(newterm));
		  remain.del_zero();
	      A=remain.getMax();
	      //remain.output();
          //cout<<newterm->exp<<endl;
	   	 if((A->exp==0)&&(B->exp==0)) break;
		 newterm=new term;		 
	  }
	  cout<<"<商>為:"<<endl;
	  quot.del_zero();
	  quot.output();
	  cout<<endl;
	  cout<<"<余項>為:";
	  remain.output();
	}
	}
}