/* ===================================================================*\



  filename:  subtract.C

  THIS PROGRAM ACCEPTS FROM THE STANDARD INPUT TWO POSITIVE INT'S OF

  ARBITRARY LENGTH AND THEN OUTPUTS THE SUBTRACTION OF THESE TWO INTEGERS.



  PROGRAMMER:  RiNN
  INSTRUCTOR:  Dr. Robert Sczech 
  Class:       CS102 S98
  Date:        Monday May 4, 1998 



\*=====================================================================*/

#include                   //iostream Header
#include                     //assert   Header
#include                    //fstream  Header

struct node{
 int digit;
 node* next;
 };
typedef node* stack;

stack A=NULL, B=NULL, M=NULL, P=NULL;

void getinteger(stack &s); 
stack subtract(stack a,stack b);
void printstack(stack s);
void push(stack &s, int n);
int pop(stack &s);
int depth(stack s);
int compare(stack a, stack b);
void flush(stack &s);
void invert(stack &s);        //Invert the stack s


void main()
{ stack A=NULL, B=NULL, M=NULL, P=NULL;
  cout << "\n\n\nHello. I can subtract truly long postive int.\n"
       << "Try me out by entering two positive integers.\n\n"
       << "Please enter the first integer: ";
  getinteger(A); cout << endl;

  cout << "and now enter the second positive integer:";
  getinteger(B); cout << endl;

  int sign =  compare(A, B);
  if (sign >0)
   printstack(subtract(A,B));
  if (sign<0){
   cout << " -"; 
   printstack(subtract(B,A));
  }
  if(sign == 0){ cout << "I'm sorry please input numbers.\n Try again";
  main();
  }
  cout << "\n Thank you for using the program. \n";
}



int compare(stack A, stack B)
{ if(depth(A) > depth(B)) return 1; 
  if(depth(A) < depth(B)) return -1;
  if((depth(A) ==0) && (depth(B) ==0)) return 0;
  if(A->digit > B->digit) return 1;
  if(A->digit < B->digit)return -1;
  compare(A->next, B->next);
}

void getinteger(stack &s)
{ char ch = cin.get();
  int n = ch - '0';
  while((0<=n) && (n <= 9)){
     push(s, n);
     ch = cin.get();
     n = ch - '0';
   }
}

void push(stack &s, int n)
{ stack temp = s;
  s = new node;
  s->next = temp;
  s->digit = n;
}

int pop(stack &s)
{ if (s == NULL)
    return 0;
  int r = s->digit;
  stack temp = s;
  s = s->next;
  delete temp;
  return r;
}

void printstack(stack s)
{ while(s !=NULL){
    cout << s->digit;
    s = s->next;
   }
  cout << endl;
}

void flush(stack &s)
{ while (s !=NULL)
    pop(s);
}

stack subtract(stack a, stack b)
{ int s, c = 0 ; // c = carryover
  stack S=NULL;
  while((a !=NULL) || (b !=NULL)){
  s=c;
  if (a !=NULL){ s = s + a->digit; a=a->next;}
  if (b !=NULL){ s = s - b->digit; b=b->next;}
  if (s < 0){ s = 10 + s; c = -1;}
  else  c = 0;
  push(S, s);
  }
  if (c!=0) push(S,c);
  return S;
}

void invert(stack &s)
{ stack temp = s;
  s = NULL;
  while(temp !=NULL)
    push(s, pop(temp));
}

int depth(stack s)
{ int count = 0;
  while( s !=NULL){
   count ++;
   s = s->next;
  }
  return count;
}