typedef struct LNode{
	struct LNode *prior;
	struct LNode *next;
	int data;
	int length;                   //用length來標記存放數(shù)據(jù)的鏈表的節(jié)點總數(shù)
}LNode,*LinkList;

using namespace std;

class Add_operation{
public:
	LinkList CreatLink(string add);              //創(chuàng)建雙向循環(huán)的鏈表，用來存放加數(shù)
	LinkList Insert(LinkList &L,LinkList &p);    //插入操作，用來創(chuàng)建加法結(jié)果的鏈表
	LinkList Add(LinkList L1,LinkList L2);       //實現(xiàn)兩個加數(shù)的相加運算
	void Print(LinkList L);                      //輸出加法操作的結(jié)果
	void Destroy(LinkList L);                    //釋放鏈表空間函數(shù)
};

LinkList Add_operation::CreatLink(string add)
{
	string s(10,'\0');            //設置一個字符串來存放每四位的數(shù)字
	LinkList L=new LNode,p2=NULL;
	L->length=0;            
	int Signal=0,length=strlen(add.c_str());     //Singal作為一個信號，用來標記每段數(shù)字的開始
	for(int it=0;it<length;++it)    //通過一個循環(huán)函數(shù)來將輸入的加數(shù)分配到每個節(jié)點中
	{
		if(it==0)               //先判斷加數(shù)的符號位
		{
			if(add[it]=='-')
			{
				Signal=it+1;
				L->data=1;       //若為負數(shù)，則將頭節(jié)點的數(shù)據(jù)域設為1
			}
			else
			{
				Signal=it;
				L->data=0;       //若為正數(shù)，則將頭節(jié)點的數(shù)據(jù)域設為0
			}
			L->next=L->prior=NULL;
			L->length=1;
		}
		if(add[it]==','||it==length-1)   //遇到，或到字符串結(jié)尾時將字符串轉(zhuǎn)化為數(shù)字后存入相應的數(shù)據(jù)域中
		{
			if(add[it]==',')
				for(int i=0;Signal+i<it;++i)
					s[i]=add[Signal+i];
			if(it==length-1)
				for(int i=0;Signal+i<=it;++i)
					s[i]=add[Signal+i];
			LinkList p1=new LNode;
			p1->data=atoi(s.c_str());
			if(L->length==1)         //以下為設置鏈表節(jié)點之間的指向關系
				p2=L;
			else
				p2=p2->next;
			if(it==length-1)
			{
				p1->next=L;
				L->prior=p1;
			}
			else
				p1->next=NULL;
			p2->next=p1;
			p1->prior=p2;
			L->length++;
			Signal=it+1;
		}
	}
	return L;
}

LinkList Add_operation::Insert(LinkList &L,LinkList &p)
{
	p->next=L->next;
	L->next=p;
	p->prior=L;
	if(L->length==1)
		L->prior=p;
	return L;
}

LinkList Add_operation::Add(LinkList L1,LinkList L2)
{
	LinkList p1=L1->prior,p2=L2->prior,L3=L1,L4=L2,L=new LNode,p3=L1,p4=L2;
	L->length=1;
	L->next=L->prior=L;
	if(L1->length<=L2->length)  //始終使p1指向絕對值較大的數(shù),L3,L4分別指向絕對值大的和小的兩個鏈表
	{
		if(L1->length<L2->length)
		{
			p2=L1->prior;
			p1=L2->prior;
			L3=L2;
			L4=L1;
		}
		else        //當兩個鏈表等長時，通過每個節(jié)點的數(shù)字的大小來判斷整個鏈表中數(shù)字的大小
			while((p3=p3->next)->data==(p4=p4->next)->data&&p3->next!=L1);
			if(p3->data<p4->data)
			{
				p2=L1->prior;
		     	p1=L2->prior;
		     	L3=L2;
	     		L4=L1;
			}
	}
	int sum=0,carry=0,borrow=0;
	if(L1->data==L2->data)      //兩個加數(shù)同號運算
	{
		L->data=L1->data;  //設置符號位
		int p2_data=0;       //由于要求不改變原鏈表，所以定義一個整型數(shù)來存放p2->data的值
	    while(p1!=L3)
		{
			p2_data=p2!=L4?p2->data:0;      //根據(jù)p2所指位置的不同來給p2_data賦值
    		sum=p1->data+p2_data+carry;  
			carry=sum/10000>0?1:0;    //判斷是否有進位產(chǎn)生
    		if(sum/10000>0)     
    			sum-=10000;
			LinkList p=new LNode;    //創(chuàng)建存放相加結(jié)果的鏈表，并將各數(shù)字存入
			p->data=sum;
			L=Insert(L,p);
			L->length++;
    		p1=p1->prior;
            if(p2!=L4)            //當p2循環(huán)結(jié)束后，p2停止循環(huán)操作	
	        	p2=p2->prior;
		}
		if(p1==L3&&p2==L4)     //若兩個加數(shù)等長，則要考慮最高位的進位情況
			if(carry==1)
			{
				LinkList p=new LNode;
		    	p->data=carry;
		    	L=Insert(L,p);
		    	L->length++;
			}
	}
	else                            //兩個加數(shù)異號運算
	{		
		L->data=L3->data==1?1:0;    //判斷做減法時結(jié)果的符號位的情況
		int p2_data=0;
		while(p1!=L3)
		{
			p2_data=p2!=L4?p2->data:0;     //為不破壞鏈表，用p2_data來存放p2中的數(shù)據(jù)
			if(p1->data-borrow>=p2_data)   //進行借位處理后判斷兩個數(shù)的大小再進行相應的操作
			{
				sum=p1->data-p2_data-borrow;
				borrow=0;
			}
			else
			{
				sum=10000+p1->data-borrow-p2_data;
				borrow=1;
			}	
			LinkList p=new LNode;    //同加法一樣，將結(jié)果存入一個重新創(chuàng)建的鏈表中
			p->data=sum;
			L=Insert(L,p);
			L->length++;
    		p1=p1->prior;
	    	if(p2!=L4)            //當p2循環(huán)結(jié)束后，p2停止循環(huán)操作	
	        	p2=p2->prior;
		}
	}	
	return L;
}

void Add_operation::Print(LinkList L)
{
	LinkList p=L;
	int n=1;
	cout << "\nThe result of the operation is : ";
	while((p=p->next)!=L&&p->data==0);   //判斷結(jié)果是否為0，若為0則直接輸出0后退出
	if(p==L)
	{
		cout << "0" << endl;
		return;
	}
	if(L->data==0)    //判斷符號位，并輸出相應的符號
		cout << " ";
	else
		cout << "-";
	p=L;
	while((p=p->next)!=L&&p->data==0);    //對結(jié)果的非零的最高位進行直接輸出
	cout << p->data;
	if(p->next!=L)
		cout << ",";
	p=p->next;
	while(p!=L)    //對結(jié)果的后面尾數(shù)進行相應的處理，對不滿四位的數(shù)字進行加零處理
	{		
		int num=p->data;
		for(int i=3;i>=0;--i)
		{
			int chushu=1;
			for(int b=0;b<i;b++)
				chushu*=10;
			cout << num/chushu;
			num%=chushu;
		}		
		if(p->next!=L)
			cout << ",";
		p=p->next;
	}
	cout << endl;
}

void Add_operation::Destroy(LinkList L)
{
	LinkList p1=L->next,p2;
	if(L->next==NULL)   
	{
		cout << "List Null !" << endl;
		exit(0);
	}
	do
	{
		p2=p1->next;
		delete p1;
		p1=p2;
	}while(p1!=L);
}