Data Structure and Algorithm

/*****************************************************************
 APPLICATION : Addition of Very Long Integers (using Linked List)
 CODED BY    : Ankit Pokhrel
 COMPILED ON : Borland C++ Ver 5.02
 DATE     : 2010 - July - 02
******************************************************************/

#include "iostream.h"
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include "string.h"
#include "iomanip.h"

struct Stack //Structure to represent Stack
{
 long int data;
 struct Stack *next,*head,*top; //Pointers to next node,head and top
};

typedef struct Stack node; //Now, node represent Structure Stack

node *New; //Global Variable to represent node

void initialize(node *n)
{
 n -> next = n -> head = n -> top = NULL;
}

void create(node *n)
{
 New = new node; //Create a new node
 New -> data = NULL; //Initialize data
 New -> next = NULL; //Initialize next pointer field
 if(n -> head == NULL) //if first node
  {
  n -> head = New; //Initialize head
   n -> top = New; //Update top
  }
}

void push(node *n,int ITEM)
{
 node *temp = n -> head;
 if(n -> head == NULL) //if First Item is Pushed to Stack
  {
   create(n); //Create a Node
  n -> head -> data = ITEM; //Insert Item to head of List
   return; //Exit from Function
  }

 create(n); //Create a new Node
 New -> data = ITEM; //Insert Item
 while(temp -> next != NULL)
    temp = temp -> next; //Go to Last Node

 temp -> next = New; //Point New node
 n -> top = New; //Update top
}

node* pop(node *n)
{
 node *temp = n -> head,*deleted;
 if(n -> top == NULL) //If the Stack is Empty
  {
    cout << "\nStack Underflow";
    exit(0); //Exit from Program
   }

 if(n -> top == n -> head) //If only one Item
  {
    deleted = n -> head;
    n -> head = n -> top = NULL; //Set head and top to Null
    return deleted; //Return deleted node
   }

 while(temp -> next != n -> top)
  temp = temp -> next; //move pointer temp to second last node

 temp -> next = NULL; //Second last node points to NULL
 deleted = n -> top; //Save topmost node
 n -> top = temp; //Update top
 return deleted; //Return deleted node
}

void display(node *n,int carry)
{
 if(n -> head == NULL) //if no items
  {
    cout << "Stack is empty";
    return;
   }

 node *temp = n -> head;
 if(carry)
  cout << carry;
 cout << setfill('0');
 cout << setw(4) << temp -> data; //Print First Item
 while(temp -> next != NULL)
  {
    temp = temp -> next; //Move to next node
    cout << setfill('0');
    cout << setw(4) << temp -> data; //Print Next Item
   }
}

int count(node *n) //Function to count the number of nodes in a List
{
 if(n == NULL) //if list doesn't exists
  return 0;

 else if(n -> next == NULL) //if only one node
  return 1;

 else
  return (1 + count(n -> next)); //else add 1 and call function count recursively
}

void reverse(node **n) //Function to reverse the List
{
 int N = count((*n) -> head),i = 0;
 long *tempArr = new long[N],*reverse = new long[N]; //Define 2 Arrays
 node *temp = (*n) -> head; //Temp points to node n
 tempArr[i++] = temp -> data; //copy first element to temporary array
 while(temp -> next != NULL) //copy all element to tempArr
  {
    temp = temp -> next;
    tempArr[i++] = temp -> data;
   }

 int j = 0;
 for(i = N - 1;i >= 0;i--)
    reverse[j++] = tempArr[i]; //copy reverse of tempArr to array reverse

//Now copy the elements of array reverse to List  
 i = 0;
 temp = (*n) -> head;
 temp -> data = reverse[i++];
 while(temp -> next != NULL)
  {
    temp = temp -> next;
    temp -> data = reverse[i++];
   }
}

void split(char *opr,node **n) //Function to split the list
{
 int len = strlen(opr);
 int i = len - 1,j;
 char temp[6];
 long value;
 while(i >= 0)
  {
    for(j = 0;j < 4;j++)
     {
     temp[j] = opr[i--];
      if(i < 0)
       {
        j++;
        break;
       }
     }

     temp[j] = '\0';
     strrev(temp);
     value = atol(temp);
     push(*n,value);
   }
}

int main()
{
 node *lint1,*lint2,*result;
 //Allocate memory for lists
 lint1 = new node;
 lint2 = new node;
 result = new node;
 //Initialize all lists to avoid errors
 initialize(lint1);
 initialize(lint2);
 initialize(result);

 char opr1[100],opr2[100];
 long int value;

 //Scan Inputs
 cout << "Enter First Operand : ";
 gets(opr1);
 cout << "Enter Second Operand : ";
 gets(opr2);

 //Divide input into various nodes each containing 1 to 4 characters
 split(opr1,&lint1);
 split(opr2,&lint2);

 //reverse lists lint1 and lint2 because the data is processed from terminal end
 //i.e. Last data will be processed First (LIFO)
 //If we use concept of Queue it is not necessary to reverse the list
 reverse(&lint1);
 reverse(&lint2);

 long data1,data2;
 int carry = 0;
 if(count(lint1 -> head) != 0) //if node exists
    data1 = pop(lint1) -> data; //pop data
 if(count(lint2 -> head) != 0)
    data2 = pop(lint2) -> data;
 value = data1 + data2 + carry;
 carry = value / 10000; //carry can be calculated by dividing value by 10000
 if(carry) //if there is carry
     value = value - carry * 10000; //eliminate carry from value
 push(result,value); //Push value to stack
 int len1,len2,len;
 len1 = count(lint1 -> head);
 len2 = count(lint2 -> head);
 len = (len1 > len2) ? len1 : len2;
 while(len > 0)
  {
    if(count(lint1 -> head) != 0)
     data1 = pop(lint1) -> data;
    else
     data1 = 0;

    if(count(lint2 -> head) != 0)
     data2 = pop(lint2) -> data;
    else
     data2 = 0;
    
    value = data1 + data2 + carry;
    carry = value / 10000;
    if(carry)
     value = value - carry * 10000;
    push(result,value);
    len--;
   }

 cout << endl << endl;
 reverse(&result); //reverse result
 cout << "Result : ";
 display(result,carry); //display result

 getch();
 return 0;
}