#include<stdio.h>

#include<malloc.h>
typedef struct linknode
{int data;/*節點的值*/
struct linknode *left,*right;
/*左指針和右指針*/
}dnode;


dnode *r1,*r2,*r3,*head1,*head2,*head3;
dnode *head_temp,*rear_temp;
/*head1為第1個數的頭指針，r1為 為第1個的尾指針*/
/*head2為第2個數的頭指針，r2為 為第2個的尾指針*/
/*head3為結果的頭指針，r3為結果的尾指針*/
/*head_temp為臨時數的頭指針，rear_temp為臨時數的尾指針*/






int flag1,flag2,time1=1,time2=1,time3=1;
/*flag1為第一個數的符號，flag2為第一個數的符號，*/
/*time1，time2，time3為第一個數，第2個數和結果的段數，4個數子為一段*/






/*產生一個長整數*/
dnode* creat()
{dnode *head,*p,*s;
/*head為頭指針，p和s為臨時指針*/
int x,cycle=1;
/*x為輸入的數據，cycle為是否繼續輸入的標志*/
head=(dnode*)malloc(sizeof(dnode));
p=head;
/*指向頭*/
while(cycle)
{scanf("%d",&x);
/*輸入數據*/
if(x>=0)/*輸入正數才有效*/
{s=(dnode*)malloc(sizeof(dnode));
s->data=x;
p->right=s;
s->left=p;
p=s;
/*采用的是頭插法*/
}
else cycle=0;
/*輸入負數就退出*/
}
head=head->right;
/*第一個頭沒有用到*/
head->left=NULL;
p->right=NULL;
return head;
}


dnode *rear(dnode *head,int *time)
/*根據一個數的頭節點，得到尾節點，并得到這個數的段數*/
{dnode *p;
p=head;
while(p->right)
/*向右移*/
{p=p->right;(*time)++;}
return p;
}



int from_char_to_int(char a)
/*把+和-變為1和0*/
{switch(a)
{case '+':return 1;break;
case '-':return 0;break;
}
}



void input_and_init()
/*初始化2個數據的大小*/
{char a;
printf("input (+,-)\n");
/*輸入符號*/
scanf("%c",&a);
scanf("%c",&a);
flag1=from_char_to_int(a);
/*符號變為對應的0或1*/
printf("input the first data,input negative data exit\n");
head1=creat();
/*產生第一個數，得到它的頭指針*/
r1=rear(head1,&time1);
/*得到第一個數的尾指針和段數*/
printf("input (+,-)\n");
/*輸入符號*/
scanf("%c",&a);
scanf("%c",&a);
flag2=from_char_to_int(a);
/*符號變為對應的0或1*/
printf("input the second data,input negative data exit\n");
head2=creat();
/*產生第2個數，得到它的頭指針*/
r2=rear(head2,&time2);
/*得到第一個數的尾指針和段數*/
}

/*打印一個數*/
void print(int data)
{if(data>=1000)
/*含有4個數字*/
printf("%d",data);
else if(data>=100)
/*含有3個數字，補1個零*/
printf("0%d",data);
else if(data>=10)
/*含有2個數字，補2個零*/
printf("00%d",data);
else
/*含有1個數字，補3個零*/
printf("000%d",data);
}

/*顯示一個結果的長整數，從后向前移*/
void display(dnode *rear)
{dnode *p;
p=rear;
while(p)
{print(p->data);
printf(" ");
p=p->left;
/*向左移*/
}
printf("\n");
}




dnode *find_sum()
/*得到2個正數的和*/
{dnode *head,*p,*s,*p1,*p2;
/*head為頭指針，p,s為臨時指針，p1指向第1個數并向左移動，p2指向第2個數并并向左移動*/
int inc=0,sum=0,f1=0,f2=0;
/*inc為進位，sum為和，f1為第一個數是否結束，f2為第一個數是否結束*/

head=(dnode*)malloc(sizeof(dnode));
p=head;
/*開辟空間*/

p1=r1;/*指向第一個數的尾*/
p2=r2;/*指向第二個數的尾*/


while(p1!=NULL&&p2!=NULL)
/*2個數的某一段都不為空時 */
{sum=p1->data+p2->data+inc;
/*和為2個數之和加進位*/
inc=0;
/* 進位回0*/
if(sum>=10000)
/*當超過2位數的大小時，和減去10000，并進位*/
{sum=sum-10000;
inc=1;
}
/*用頭插法建立一個新的節點*/
s=(dnode*)malloc(sizeof(dnode));
s->data=sum;
p->right=s;
s->left=p;
p=s;

/*2個數都向左移*/
p1=p1->left;
p2=p2->left;
}

if(p1==NULL&&p2==NULL)
if(inc==1)
/*當2個數據都完了，但是存在進位時，新建一個節點，值就是進位*/
{s=(dnode*)malloc(sizeof(dnode));
s->data=1;
p->right=s;
s->left=p;
p=s;
}


while(p1!=NULL)
/*當第2個數空，第1個數不為空時，將第一個數剩下的全用新節點產生*/
{f1=1;
s=(dnode*)malloc(sizeof(dnode));
sum=p1->data+inc;
inc=0;
if(sum>=10000)
{sum=sum-10000;
inc=1;
}
s->data=sum;
p->right=s;
s->left=p;
p=s;
/*第1個數都向左移*/
p1=p1->left;
}

/*當第1個數據完了，但是存在進位時，新建一個節點，值就是進位*/
if(f1==1&&inc==1&&!p1)
{
s=(dnode*)malloc(sizeof(dnode));
s->data=1;
p->right=s;
s->left=p;
p=s;
}



/*當第1個數空，第2個數不為空時，將第一個數剩下的全用新節點產生*/
while(p2!=NULL)
{f2=1;
s=(dnode*)malloc(sizeof(dnode));
sum=p2->data+inc;
inc=0;
if(sum>=10000)
{sum=sum-10000;
inc=1;
}
s->data=sum;
p->right=s;
s->left=p;
p=s;
p2=p2->left;
/*第2個數都向左移*/
}



/*當第2個數據完了，但是存在進位時，新建一個節點，值就是進位*/
if(f2==1&&inc==1)
{s=(dnode*)malloc(sizeof(dnode));
s->data=1;
p->right=s;
s->left=p;
p=s;
}


head=head->right;
head->left=NULL;
p->right=NULL;
return head;
/*返回頭節點*/
}




/*得到2個正數的差*/
dnode *find_sub(dnode * s1,dnode *t1)
{dnode *head,*p,*s,*p1,*p2;
/*head為頭指針，p,s為臨時指針，p1指向第1個數并向左移動，p2指向第2個數并并向左移動*/
int dec=0,sub=0;
/* dec為減位，sub為差*/
head=(dnode*)malloc(sizeof(dnode));
p=head;
/*開辟空間*/





p1=s1;
/*指向第一個數的尾*/
p2=t1;
/*指向第二個數的尾*/



/*2個數的某一段都不為空時 */
while(p1!=NULL&&p2!=NULL)
{sub=p1->data-p2->data-dec;
/*和為2個數之差減去差位*/
dec=0;
/*差位回0*/
if(sub<0)
/*存在差位，就要加10000，差位變1*/
{sub=sub+10000;
dec=1;
}
/*用頭插法建立一個新的節點*/
s=(dnode*)malloc(sizeof(dnode));
s->data=sub;
p->right=s;
s->left=p;
p=s;




/*2個數都向左移*/
p1=p1->left;
p2=p2->left;
}

/*當第2個數空，第1個數不為空時，將第一個數剩下的全用新節點產生*/
while(p1!=NULL)
{s=(dnode*)malloc(sizeof(dnode));
sub=p1->data-dec;
dec=0;
if(sub<0)
{sub=sub+10000;
dec=1;
}
s->data=sub;
p->right=s;
s->left=p;
p=s;
/*第1個數都向左移*/
p1=p1->left;
}




/*當第1個數空，第2個數不為空時，將第一個數剩下的全用新節點產生*/
while(p2!=NULL)
{s=(dnode*)malloc(sizeof(dnode));
sub=p2->data-dec;
dec=0;
if(sub<0)
{sub=sub+10000;
dec=1;
}
s->data=sub;
p->right=s;
s->left=p;
p=s;
/*第2個數都向左移*/
p2=p2->left;
}



head=head->right;
head->left=NULL;
p->right=NULL;
return head;
/*返回頭節點*/

}



void sub()
/*減法，減法和加法相同，只是首先要把第2個數的符號位變反*/
{dnode *p1,*p2;
if(flag2==1)flag2=0;
else if(flag2==0)flag2=1;
if(flag1==1&&flag2==1)
{head3=find_sum();
r3=rear(head3,&time3);
printf("\n+ ");
display(r3);
}

if(flag1==0&&flag2==0)
{head3=find_sum();
r3=rear(head3,&time3);
printf("\n- ");
display(r3);
} 

if(flag1==1&&flag2==0)
{if(time1>time2||(time1==time2&&head1->data>head2->data))
{
head3=find_sub(r1,r2);
r3=rear(head3,&time3);
printf("\n+ ");
display(r3);
}
if(time1<time2||(time1==time2&&head1->data<head2->data))
{
head3=find_sub(r2,r1);
r3=rear(head3,&time3);
printf("\n- ");
display(r3);
}
if(time1==time2&&head1->data==head2->data)
{
p1=head1;
p2=head2;
while(p1->right&&p2->right&&p1->data==p2->data)
{p1=p1->right;
p2=p2->right;
}
if(p1->data>p2->data)
{
head3=find_sub(r1,r2);
r3=rear(head3,&time3);
printf("\n+ ");
display(r3);
}
else if(p1->data<p2->data)
{
head3=find_sub(r2,r1);
r3=rear(head3,&time3);
printf("\n- ");
display(r3);
}
else
printf("\n0\n");
}
}


if(flag2==1&&flag1==0)
{if(time2>time1||(time1==time2&&head2->data>head1->data))
{
head3=find_sub(r2,r1);
r3=rear(head3,&time3);
printf("\n+ ");
display(r3);
}
if(time2<time1||(time1==time2&&head2->data<head1->data))

{
head3=find_sub(r1,r2);
r3=rear(head3,&time3);
printf("\n- ");
display(r3);
}

if(time1==time2&&head1->data==head2->data)