#include<stdio.h> 
#include<stdlib.h> 
#define WANG 10000 
#define NULL 0
int d=1,count=0,t=1,l=0;
typedef struct node
{ 
	int data; 
	struct node *next; 
}NODE; /*定義鏈表結構*/ 
NODE *insert_after(NODE *x,int num); /*在u結點后插入一個新的NODE，其值為num*/ 
NODE *addint1(NODE *p,NODE *q); /*完成加法操作返回指向*p+*q結果的指針*/ 
void printint(NODE *s); 
NODE *inputint(void); 
void main() 
{ 
	NODE *s1,*s2,*s; 
	NODE *inputint(), *addint(), *insert_after(); 
	printf("Enter S1= "); 
	s1=inputint(); /*輸入被加數*/
	printf("S1=");
	if(count==t){putchar('-');l=1;}
	printint(s1); 
	putchar('\n');  
	printf("Enter S2= "); 
	s2=inputint(); /*輸入加數*/ 
	printf("S2=");
	if(count>t||d==-1)putchar('-');
	printint(s2); putchar('\n'); 
	s=addint1(s1,s2); /*求和*/ 
	printf("S1+S2=");if(count>t)putchar('-'); printint(s); putchar('\n'); 
} 
NODE *insert_after(NODE *x,int num) 
{ 
	NODE *y; 
	y=(NODE *)malloc(sizeof(NODE)); /*申請一個NODE*/ 
	y->data=num; /*賦值*/ 
	x->next=y; /*在u結點后插入一個NODE*/ 
	return y; 
} 
NODE *addint1(NODE *p,NODE *q) /*完成加法操作返回指向*p+*q結果的指針*/ 
{ 
	NODE *pp,*qq,*r,*s,*t; 
	int total,number,carry; 
	pp=p->next; qq=q->next; 
	s=(NODE *)malloc(sizeof(NODE)); /*建立存放和的鏈表表頭*/ 
	s->data=-1; 
	t=s; carry=0; /*carry:進位*/ 
	if (count!=1)
	{
	while(pp->data!=-1&&qq->data!=-1) /*均不是表頭*/ 
	{ 
		total=pp->data+qq->data+carry; /*對應位與前次的進位求和*/ 
		number=total%WANG; /*求出存入鏈中部分的數值 */ 
		carry=total/WANG; /*算出進位*/ 
		t=insert_after(t,number); /*將部分和存入s向的鏈中*/ 
		pp=pp->next; /*分別取后面的加數*/ 
		qq=qq->next; 
	} 
	r=(pp->data!=-1)?pp:qq; /*取尚未自理完畢的鏈指針*/ 
	while(r->data!=-1) /*處理加數中較大的數*/ 
	{ 
		total=r->data+carry; /*與進位相加*/ 
		number=total%WANG; /*求出存入鏈中部分的數值*/ 
		carry=total/WANG; /*算出進位*/ 
		t=insert_after(t,number); /*將部分和存入s指向的鏈中*/ 
		r=r->next; /*取后面的值*/ 
	} 
	if(carry) t=insert_after(t,1); /*處理最后一次進位*/ 
	t->next=s; /*完成和的鏈表*/ 
	return s; /*返回指向和的結構指針*/
	}else 
	{   if(l==0)
	{while(pp->data!=-1&&qq->data!=-1) /*均不是表頭*/ 
	{
		total=pp->data-qq->data-carry;/*對應位與前次的進位求差*/ 
		number=total%WANG; /*求出存入鏈中部分的數值 */ 
		carry=total/WANG; /*算出進位*/ 
		t=insert_after(t,number); /*將部分差存入s向的鏈中*/ 
		pp=pp->next; /*分別取后面的加數*/ 
		qq=qq->next; 
	} 
	r=(pp->data!=-1)?pp:qq; /*取尚未自理完畢的鏈指針*/ 
	while(r->data!=-1) /*處理加數中較大的數*/ 
	{ 
		total=r->data-carry; /*與進位相加*/ 
		number=total%WANG; /*求出存入鏈中部分的數值*/ 
		carry=total/WANG; /*算出進位*/ 
		t=insert_after(t,number); /*將部分和存入s指向的鏈中*/ 
		r=r->next; /*取后面的值*/ 
	} 
	if(carry) t=insert_after(t,1); /*處理最后一次進位*/ 
	t->next=s; /*完成和的鏈表*/ 
	return s; /*返回指向和的結構指針*/
	}
	}
} 
NODE *inputint(void) /*輸入超長正整數*/ 
{ 
	NODE *s,*ps,*qs; 
	struct number {int num; 
	struct number *np; 
	}*p,*q; 
	int i,j,k; 
	long sum; 
	char c; 
	p=NULL; /*指向輸入的整數，鏈道為整數的最低的個位，鏈尾為整數的最高位*/ 
	while((c=getchar())!='\n') /*輸入整數，按字符接收數字*/
	{	if(c=='-'){d*=-1;count++;}
		if(c>='0'&&c<='9') /*若為數字則存入*/ 
		{ 
			q=(struct number *)malloc(sizeof(struct number)); /*申請空間*/ 
			q->num=(c-'0'); /*存入一位整數*/ 
			q->np=p; /*建立指針*/ 
			p=q; 
	} }
		s=(NODE *)malloc(sizeof(NODE)); 
		s->data=-1; /*建立表求超長正整數的鏈頭*/ 
		ps=s; 
		while(p!=NULL) /*將接收的臨時數據鏈中的數據轉換為所要求的標準形式*/ 
		{ 
			sum=0;i=0;k=1; 
			while(i<4&&p!=NULL) /*取出低四位*/ 
			{ 
				sum=sum+k*(p->num); 
				i++; p=p->np; k=k*10; 
			} 
			qs=(NODE *)malloc(sizeof(NODE)); /*申請空間*/ 
			qs->data=sum; /*賦值，建立鏈表*/ 
			ps->next=qs; 
			ps=qs; 
		} 
		ps->next=s; 
		return s; 
} 
void printint(NODE *s) 
{ 
	if(s->next->data!=-1) /*若不是表頭，則輸出*/ 
	{ 
		printint(s->next); /*遞歸輸出*/ 
		if(s->next->next->data==-1) 
			printf("%d,",s->next->data); 
		else{ 
			int i,k=WANG; 
			for(i=1;i<=4;i++,k/=10) 
			{putchar('0'+s->next->data%(k)/(k/10));if(i==4)putchar(',');}
		} 
	} 
}