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



  filename:  sum.C

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

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

  PROGRAMMER:  RiNN
  INSTRUCTOR:  Dr. Robert Sczech 
  Class:       CS102 S98
  Date:        Thursay April 23, 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 sum(stack a, stack b);  //Returns teh sum of the two long int
 			      //returns the product of two int.
stack prod(stack a,stack b);
stack mult(stack s, int n);   //Returns the product of a long int
                              //times a single digit interger
void printstack(stack s);
void push(stack &s, int n);
int pop(stack &s);
void flush(stack &s);
void invert(stack &s);        //Invert the stack s



void main()
{ stack A=NULL, B=NULL, M=NULL, P=NULL;
  cout << "\nHello. I can add and multiply 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;
  cout << "\n"
       << "Please enter + or * to indicate whether I should calculate\n"
       << "the sum or the product of these numbers. \n\n";

  char ch = cin.get(); cout << endl;  

  if(ch == '+')
     printstack(sum(A, B));
  if(ch == '*')
     printstack(prod(A, B));
  else if((ch != '+') && (ch != '*')){
     cout << "I'm sorry that was the wrong command. please try again "
          << "later\n\n";
   }
  cout << "Thank you for using the program. \n";
}

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 sum(stack a, stack b)
{ int d, c = 0; // c = carryover
  stack s=NULL;
  while((a !=NULL) || (b !=NULL)){
  d = c + pop(a) + pop(b);
  push(s, d%10);
  c = d/10;      
  }
  if(c > 0)
    push(s,c);
 return s;
}

stack mult(stack s, int n)
{ flush(M);
  int dig, c = 0;  // c = carry over
  while(s !=NULL){
     dig = n * s->digit + c;
     s = s->next;
     push(M, dig%10);
     c = dig/10;
  }
  if(c !=0)
     push(M, c);
  invert(M);
  return M;
}

stack prod(stack a, stack b)
{ flush(P);       //accumulates the product
  while(b !=NULL){
     invert(P);
     P = sum(P, mult(a, b->digit));
     b = b->next;
     push(a, 0);
   }
   return P;
}

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