#include <stdio.h>
#include <string.h>

struct integer{
	int digit;
	struct integer *next;
};

struct integer* convert_integer(char* stringInt);
void print(struct integer *p);
struct integer* add(struct integer *p, struct integer *q);
struct integer* subtract(struct integer *p, struct integer *q);
int compare(struct integer *p, struct integer *q);
struct integer* removeZeros(struct integer* p);
void delete(struct integer* p);

int main()
{
    FILE *ifp;
    ifp=fopen("bigint.txt","r");
    if(ifp==NULL)
         return 0;
    int numLines;
    fscanf(ifp,"%d",&numLines);//the first number in the file is the number of equations we have to solve
    while(numLines>0)
    {
       int addOrSubtract;
       fscanf(ifp,"%d",&addOrSubtract);//1 if add and 2 if subtract
       char num1[201];
       fscanf(ifp,"%s",num1);//read in first number
       char num2[201];
       fscanf(ifp,"%s",num2);//read in seconnd number
       struct integer* list1=convert_integer(num1);//convert to linked list
       struct integer* list2=convert_integer(num2);//convert to linked list
       struct integer* end;//what will be the end result of the equation
       if(addOrSubtract==1)
         {
              print(list1);
              printf(" + ");
              print(list2);
              printf(" = ");
              end=add(list1,list2);
              print(end);
         }
         else
         {
             if(compare(list1,list2)>0)//compare will return 1 if list 1 is greater, 0 if they are =, and -1 if list 2 is greater
             {
                 print(list1);
                 printf(" - ");
                 print(list2);
                 printf(" = ");
                 end=subtract(list1,list2);
                 print(end);
             }
             else if(compare(list1,list2)==0)//if they are =
             {
                 print(list1);
                 printf(" - ");
                 print(list2);
                 printf(" = ");
                 printf("0");
             }
             else//if 2 is greater
             {
                 print(list2);
                 printf(" - ");
                 print(list1);
                 printf(" = ");
                 end=subtract(list2,list1);
                 print(end);
             }
         }
		printf("\n");
		numLines--;
		delete(list1);
		delete(list2);
		delete(end);
    }
    fclose(ifp);
    system("pause");
    return 0;
}

struct integer* convert_integer(char* stringInt)
{
    struct integer* reverse=NULL;
	int i;
	for(i=0;i<strlen(stringInt);i++)
    {
       struct integer* temp=NULL;//need temp to keep track of place
       temp=(struct integer*)(malloc(sizeof(struct integer)));//allocate memory
       temp->digit=stringInt[i]-'0';
       temp->next=reverse;//add to front
       reverse=temp;//make reverse = temp so when it adds to front again it will actually add to front
    }
    return reverse;
}

void print(struct integer *p)
{
    if(p!=NULL)
    {
      print(p->next);
      printf("%d",p->digit);
    }
}

struct integer* add(struct integer *p, struct integer *q)
{
     struct integer* end=(struct integer*)(malloc(sizeof(struct integer)));
     struct integer* front = end;
     struct integer* temp=NULL;//need temp to keep track of place
     int carry=0;
     while(p!=NULL&&q!=NULL)
     {
         int sum=p->digit+q->digit;
         //printf("sum %d",sum);
         if(carry==1)sum+=1; //if you needed to carry over then add one to the sum
         carry=0;
         if(sum>9)
         {
            sum-=10;
            carry=1;
         }
         temp=(struct integer*)(malloc(sizeof(struct integer)));//allocate memory
         temp->digit=sum;
         end->next=temp;
         end=end->next;
         p=p->next;
         q=q->next;
     }
     while(p!=NULL&&q==NULL)//make test case for this
     {
       if(carry==0)
         end->next=p;
       if(carry==1&&p->next!=NULL)//if it needs to be carried over
         {
             int sum=p->digit;
             sum+=1;//if you needed to carry over then add one to the sum
             carry=0;
             if(sum>10)
             {
                sum-=10;
                carry=1;
             }
             end->digit=sum;
             end=end->next;
         }
         if(carry==1)
         {
           end->next->digit=1;
         }
        p=p->next;
     }
     while(q!=NULL&&p==NULL)//make test case for this
     {
       if(carry==0)
         end->next=p;
       if(carry==1&&q->next!=NULL)
         {
             int sum=q->digit;
             sum+=1;//if you needed to carry over then add one to the sum
             carry=0;
             if(sum>10)
             {
                sum-=10;
                carry=1;
             }
             end->digit=sum;
             end=end->next;
         }
       if(carry==1)
         {
           end->next->digit=1;
         }
        q=q->next;
     }
     return front;
}
struct integer* subtract(struct integer *p, struct integer *q)
{
    struct integer* end=(struct integer*)(malloc(sizeof(struct integer)));
     struct integer* front = end;
     struct integer* temp=NULL;//need temp to keep track of place
     end->next=NULL;
     int carry=0;
     while(p!=NULL&&q!=NULL)
     {
         int difference;
         difference=p->digit-q->digit;
         if(carry==1)difference-=1;//if you needed to carry over then add one to the sum
         carry=0;
         if(difference<0)
         {
            difference+=10;
            carry=1;
         }
         end->digit=difference;
         if(p->next!=NULL)
         {
             temp = (struct integer*)malloc(sizeof(struct integer));
             temp->next=NULL;
             end->next=temp;
             end=end->next;
         }
         p=p->next;
         q=q->next;
     }
     while(p!=NULL)
     {
         int difference;
         difference=p->digit;
         if(carry==1)difference-=1;//if you needed to carry over then add one to the sum
         carry=0;
         if(difference<0)
         {
            difference+=10;
            carry=1;
         }
         end->digit=difference;
         if(p->next!=NULL)
         {
             temp = (struct integer*)malloc(sizeof(struct integer));
             temp->next=NULL;
             end->next=temp;
             end=end->next;
         }
         p=p->next;
     }
     front=removeZeros(front);
     return front;
}

int compare(struct integer *p, struct integer *q)
{
    if(p==NULL&&q==NULL)
        return 0;
    if(p==NULL)
        return -1;
    if(q==NULL)
        return 1;
    int check = compare(p->next,q->next);
    if(check!=0)
       return check;
    if(p->digit>q->digit)
        return 1;
    if(p->digit<q->digit)
        return -1;
    if(p->digit==q->digit)
       return 0;
}

struct integer* removeZeros(struct integer* p)
{
      struct integer* firstZero=p;
      struct integer* temp=p;
      while(temp!=NULL)
      {
         if(temp->digit!=0)
           firstZero=temp;
         temp=temp->next;
      }
      delete(firstZero->next);
      firstZero->next=NULL;
      return p;
}

void delete(struct integer* p)
{
    if(p!=NULL)
    {
        delete(p->next);
        free(p);
    }
}