Big Int Addition

Primitive int data type handles integers each of which can be stored using 32 bits. Similarly long data type also has a limit. In this assignment you have to implement a data type which handles numbers larger than int , long and long long.

You are given a number in decimal form. You need to build a data structure called BigInt which can store that data, and perform the following basic operations on that data type:

   1.BigInt::add(BigInt A ), returns the result in another BigInt, without altering the numerical value of the caller.

   2.BigInt::print(), this function must print Most significant digit at the beginning and must not print any leading zeroes.

      Ex:     123 (correct )

              0123 (incorrect)

   3.populate(BigInt &A, char * str), populates the List in BigInt using public methods of BigInt.

Note that populate(BigInt &A, char * str) method is not a function of BigInt.

Input:

Input will have two lines, each line contains a single BigInt.

Output:

Output contains the result of the addition in a single line.

Output of the above sample input is as follows.

Constraints:

1 ≤ Input length of BigInt ≤ 40 digits.

Input for BigInt is always positive

#include <iostream>
#include <cstring>
using namespace std;
class ListNode{
 private:
  int data;
  ListNode * next;
 public:
  ListNode(){}
  ListNode(int num){
   data=num;
   next = NULL;
  }
  int getData();
  void setData(int);
  void setNext(ListNode *);
  ListNode* getNext();
};

int ListNode::getData(){

  return data;
}
void ListNode::setData(int x){
  data = x;
}
ListNode * ListNode::getNext(){
  return next;
}
void ListNode::setNext(ListNode * P){
  next = P;
}
class List{
 private:
  ListNode * Head;
 public:  
  List(){
   Head=NULL;
  }
  ~List(){}
  ListNode * getHead();
  void setHead(ListNode *);
  ListNode * last();
  void append(int);
  void prepend(int);
  void popBack();
  void print();
  void copy(List);
  void printReverse();
  ListNode * prevNode(ListNode* P);
  void popFront();      
};
ListNode * List::getHead(){
  return Head;
}
ListNode * List::last(){
  ListNode * temp=Head;
  if(Head==NULL) return NULL;
  while(temp->getNext()!=NULL){
   temp=temp->getNext();
  }
  return temp;
}
void List::setHead(ListNode * P){
  Head = P;
}
void List::append(int num){
  ListNode * new_node = new ListNode(num);
  ListNode * temp=Head;
  if(temp==NULL){
   Head = new_node;
   return;
  }
  while(temp->getNext()!=NULL) temp=temp->getNext();
  temp->setNext(new_node);
}
void List::prepend(int num){
  ListNode * new_node = new ListNode(num);
  new_node->setNext(Head);
  Head = new_node;
}
void List::popBack(){
  ListNode * temp=Head,*prev=NULL;
  //NULL list
  if(Head==NULL){cout<<"List is Empty\n";}
  //single element
  if(Head->getNext()==NULL){
   delete Head;
   Head=NULL;
   return;
  }
  while(temp->getNext()!=NULL){
   prev = temp;
   temp=temp->getNext();
  }
  delete temp;
  prev->setNext(NULL);
}
void List::print(){
  ListNode * temp=Head;
  while(temp!=NULL){
   cout<<temp->getData();
   temp=temp->getNext();
  }
}
void List::copy(List L){
  Head = NULL;
  ListNode * temp = L.Head;
  while(temp!=NULL){
   this->append(temp->getData());
   temp=temp->getNext();
  }
}
void List::printReverse(){
  ListNode * curr=Head;
  ListNode * prev_last=NULL;
  while(Head!=NULL && prev_last!=Head){
   curr = Head;    
   while(curr->getNext()!=prev_last){
    curr = curr->getNext();
   }
   cout<<curr->getData();
   prev_last = curr;
  }
}
class BigInt{
   private: 
     List L;
   public:
    BigInt(){}
    ~BigInt(){}
    void append(int num);
    void prepend(int num);
    BigInt add(BigInt A);
    void print();
    void removeZeroes();
    void copy(BigInt B);

};
List L1,L2,L3;
int y=0;
void populate(BigInt &A, char * str){
 int i,c=0,x=0,j,l=strlen(str);
  for(i=0;i<l;i++)
  {
   c=str[i];
   if( (c==48) && (x==0) )
    {
     for(j=0;j<l;j++)
      str[j]=str[j+1];
    }
   else
    x++; 
  } 
  for(i=strlen(str)-1;i>=0;i--)
  { 
     c=str[i];
    if(y==0)
  L1.append(c-48);
    if(y==1)
  L2.append(c-48);
  }
  y++;
}
BigInt BigInt::add(BigInt A)
{
      int a,b,m,n=0;
  ListNode * temp1=L1.getHead(), * temp2=L2.getHead();
  while(temp1!=NULL || temp2!=NULL)
 {
   if(temp1!=NULL)
   {
    a=temp1->getData();
   }
   else
    a=0;
   if(temp2!=NULL)
   {
    b=temp2->getData();
   }
   else
    b=0;
   m=(n+a+b)%10;
   n=(n+a+b)/10;
   L3.append(m);
   if(temp1!=NULL)
    temp1=temp1->getNext();
   if(temp2!=NULL)
    temp2=temp2->getNext();
 }
if(temp1==NULL && temp2==NULL && n!=0)
  L3.append(n);
 return A;
}
void BigInt::print()
{
    L3.printReverse();
}
int main(){
      char str[40];
      BigInt A,B;
      cin>>str;
      populate(A,str);
      cin>>str;
      populate(B,str);
      (A.add(B)).print();
      return 0;
}