20131013

All Basic Calculator Functions on large numbers using linked lists

As promised , here is the classic  Addition/Subtraction/Division/Multiplication
code in c programming language 

program in c for Addition , Subtraction , Division , Multiplication of large integer numbers using singly  linked lists



  1. //blnur aubgl
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. typedef struct node *nodeptr;
  7. struct node{
  8. int data;
  9. nodeptr next;
  10. };
  11.  
  12. list_print(nodeptr s)
  13.    {
  14.  
  15.    if(s->next!=NULL)
  16.    {
  17.  
  18.    list_print(s->next);
  19.    printf("%d",s->data);
  20.    }
  21.    else{printf("%d",s->data);}
  22.  
  23.    }
  24. int num_list_add_leng(nodeptr s ,char str[])
  25. {
  26.  
  27.  int len=strlen(str);
  28.  
  29.  int x=0;
  30.  while(x<len)
  31.  {
  32.                 int d=(int)str[x]-(int)'0';
  33.                 nodeptr temp=NULL;
  34.                 temp=malloc(sizeof(nodeptr));
  35.                 temp->next=s->next;
  36.                 s->next=temp;
  37.                 temp->data=d;
  38.                 x++;
  39.  }
  40.  return (len);
  41.  
  42. }
  43. initialize(nodeptr one,nodeptr two,nodeptr ans)
  44. {
  45.     one->next=NULL;
  46.     two->next=NULL;
  47.     ans->next=NULL;
  48.     one->data=0;
  49.     two->data=0;
  50. }
  51. int bfr=0;
  52.  
  53.  
  54. list_add_front(nodeptr s,int x)
  55. {
  56.  
  57.    nodeptr temp=NULL;
  58.  
  59.    temp=malloc(sizeof(nodeptr));
  60.    temp->data=x;
  61.    while(s->next!=NULL){
  62.    s=s->next;}
  63.    s->next=temp;
  64.    temp->next=NULL;
  65. }
  66.  
  67.  addit(nodeptr one,nodeptr two,nodeptr ans)
  68. {
  69.     bfr=0;
  70.     nodeptr op=NULL;
  71.     int ad1,ad2;
  72.  while(1){
  73.  
  74.     if((one->next!=NULL)&&(two->next!=NULL))
  75.     {
  76.         one=one->next;
  77.         ad1=one->data;
  78.         two=two->next;
  79.         ad2=two->data;
  80.     }
  81.     else{
  82.     if((one->next==NULL)&&(two->next!=NULL))
  83.     {
  84.  
  85.                 ad1=0;
  86.         two=two->next;
  87.         ad2=two->data;
  88.  
  89.     }
  90.  
  91.     else{
  92.     {
  93.         ad2=0;
  94.         one=one->next;
  95.         ad1=one->data;
  96.  
  97.     }
  98.     }
  99.     }
  100.  
  101.         nodeptr temp=NULL;
  102.     temp=malloc(sizeof(nodeptr));
  103.     temp->next=NULL;
  104.     temp->data=(ad1+ad2+bfr)%10;
  105.     ans->next=temp;
  106.     ans=ans->next;
  107.     bfr=(ad1+ad2+bfr)>9?1:0;
  108.     if((one->next==NULL)&&(two->next==NULL))
  109.     break;
  110.     }
  111.     if(bfr)
  112.     {
  113.     nodeptr temp=NULL;
  114.     temp=malloc(sizeof(nodeptr));
  115.     ans->next=temp;
  116.     temp->data=1;
  117.     temp->next=NULL;
  118.  
  119.     }
  120.  
  121.  
  122. }
  123.  
  124. freemem(nodeptr s)
  125. {
  126.     if(s->next!=NULL)
  127.     {
  128.         freemem(s->next);
  129.     }
  130.     free(s);
  131.  
  132. }
  133. int ret=3;
  134.  
  135. int greater(nodeptr one,nodeptr two)
  136. {
  137.     if((one->next!=NULL)&&(two->next!=NULL))
  138.     {
  139.         greater(one->next,two->next);
  140.  
  141.     }
  142.     if(((one->data)>(two->data))&&(ret==3)||((one->next!=NULL)&&(two->next==NULL)))
  143.     ret= 1;
  144.     if(((one->data)<(two->data))&&(ret==3)||((one->next==NULL)&&(two->next!=NULL)))
  145.     ret= 2;
  146.  
  147.     return(ret);
  148.  
  149. }
  150. subthd(nodeptr s)
  151. {
  152.     if(s->next->data==0)
  153.     {
  154.         subthd(s->next);
  155.         s->data=9;
  156.     }
  157.     else{
  158.     s->next->data--;
  159.     }
  160. }
  161.  int on=1,flg=0;
  162.  /*int traverse(nodeptr s)
  163.  {
  164.  
  165.      while(s!=NULL)
  166.      {
  167.          if(s->data!=0)
  168.          {
  169.              return 0;
  170.          }
  171.          s=s->next;
  172.      }
  173.      return 1;
  174.  }
  175.  zero_trim(nodeptr s)
  176.  {
  177.    while(s->next!=NULL)
  178.    {
  179.        if(s->next->data==0)
  180.        {
  181.            if(traverse(s->next))
  182.            s->next=NULL;
  183.        }
  184.        s=s->next;
  185.    }
  186.  
  187.  } */
  188. stripLeadingZeros( nodeptr s )
  189. {
  190.   if(s!=NULL)
  191.   stripLeadingZeros(s->next);
  192.   if((s!=NULL)&&s->data==0&&on)
  193.   flg=1;
  194.   if((s!=NULL)&&(s->data!=0)&&flg)
  195.   on=0,flg=0,s->next=NULL;
  196.   if(flg)
  197.   s->next=NULL;
  198. }
  199.  
  200.  
  201.  
  202. subtract(nodeptr one,nodeptr two,nodeptr ans)
  203. {
  204.     nodeptr tmp;
  205.     int i=1;
  206.     if(greater(one,two)==2)
  207.     {
  208.         tmp=two;
  209.         two=one;
  210.         one=tmp;
  211.     }
  212.     if(greater(one,two)==3)
  213.     {
  214.         tmp=NULL;
  215.         tmp=malloc(sizeof(nodeptr));
  216.         tmp->next=NULL;
  217.         tmp->data=0;
  218.         ans->next=tmp;
  219.         i=0;
  220.     }
  221.  
  222.     int flag =1;
  223.     one=one->next;
  224.     two=two->next;
  225.     while(i){
  226.  
  227.             if((one->data)<(two->data))
  228.             {
  229.  
  230.                 subthd(one);
  231.                 one->data=one->data+10;
  232.                 nodeptr tmp;
  233.                 tmp=malloc(sizeof(nodeptr));
  234.                 tmp->next=NULL;
  235.                 tmp->data=(one->data)-(two->data);
  236.                 ans->next=tmp;
  237.                 ans=ans->next;
  238.  
  239.             }
  240.             else
  241.             {
  242.               nodeptr tmp;
  243.               tmp=malloc(sizeof(nodeptr));
  244.               tmp->next=NULL;
  245.               tmp->data=(one->data)-(two->data);
  246.               ans->next=tmp;
  247.               ans=ans->next;
  248.             }
  249.  
  250.             if((one->next!=NULL)&&(two->next!=NULL))
  251.             {
  252.                 one=one->next;
  253.                 two=two->next;
  254.             }
  255.             else{
  256.                 while(one->next!=NULL){
  257.                 nodeptr tmp;
  258.                 tmp=malloc(sizeof(nodeptr));
  259.                 tmp->next=NULL;
  260.                 tmp->data=one->next->data;
  261.                 ans->next=tmp;
  262.                 ans=ans->next;
  263.                 one=one->next;
  264.                 }
  265.             break;
  266.             }
  267.  
  268.  
  269.     }
  270.  
  271.  
  272.  
  273. }
  274.  
  275.  
  276. divide(nodeptr one,nodeptr two,nodeptr ans){
  277. int i=0;
  278. while(1){
  279.  
  280. if(greater(one,two)==3)
  281. {
  282.     i=i+1;
  283.     break;
  284. }
  285. else{
  286.     if(greater(one,two)==2)
  287.     {
  288.  
  289.         break;
  290.  
  291.     }
  292.     else
  293.     {
  294.         i++;
  295.         subtract(one,two,ans);
  296.         stripLeadingZeros(ans->next);
  297.         one=ans;
  298.     }
  299.  
  300. }
  301. }
  302.  
  303. nodeptr tmp=NULL;
  304. tmp=malloc(sizeof(nodeptr));
  305. tmp->next=NULL;
  306. tmp->data=i;
  307. ans->next=tmp;
  308.  
  309.  
  310. }
  311.  
  312.  
  313. main()
  314. {
  315.     nodeptr one=NULL;
  316.     nodeptr two=NULL;
  317.     nodeptr ans=NULL;
  318.     one=malloc(sizeof(nodeptr));
  319.     two=malloc(sizeof(nodeptr));
  320.     ans=malloc(sizeof(nodeptr));
  321.     initialize(one,two,ans);
  322.     char a[10000];
  323.     printf("first number =");
  324.     scanf("%s",a);
  325.     int l1=num_list_add_leng(one,a);
  326.  
  327.     fflush(stdin);
  328.     printf("\n second number =");
  329.     scanf("%s",a);
  330.     int l2=num_list_add_leng(two,a);
  331.     list_print(one->next);
  332.     printf("\n");
  333.     list_print(two->next);
  334.     printf("\n  */+/-  ? = ");
  335.     char pr;
  336.     scanf(" %c",&pr);
  337.     printf("\n");
  338.     int i=0,j=0,buffer=0;
  339.     nodeptr add[l2];
  340.     int flow=1;
  341.  if((pr=='+')&&flow){
  342.      addit(one,two,ans);
  343.      list_print(ans->next);
  344.      flow=0;
  345.  }
  346.  if((pr=='-')&&flow)
  347.  {
  348.  
  349.      subtract(one,two,ans);
  350.      stripLeadingZeros(ans->next);
  351.      list_print(ans->next);
  352.      flow=0;
  353.  }
  354.  if((pr=='/')&&flow)
  355.  {
  356.      divide(one,two,ans);
  357.      list_print(ans->next);
  358.      flow=0;
  359.  }
  360.  if((pr=='*')&&flow){                                         //note: ans node is useless for addition from here used as temp mem frm here
  361. for(j=0;j<l2;j++)
  362. {
  363.     add[j]=malloc(sizeof(nodeptr));
  364.     add[j]->next=NULL;
  365.     int ts=j;
  366.     while(ts!=0)
  367.     {
  368.        list_add_front(add[j],0);
  369.        ts--;
  370.     }
  371.      ans=one;
  372.     int tmp1=two->next->data;
  373.  for(i=0;i<l1;i++){
  374.       int tmp=one->next->data;
  375.       int tmp3=(tmp1*tmp)+buffer;
  376.       list_add_front(add[j],(tmp3)%10);
  377.       buffer=(tmp3)>9?(tmp3/10):0;
  378.           one=one->next;
  379.                   }
  380.                   one=ans;
  381. if(buffer>=1){
  382. list_add_front(add[j],buffer);
  383.  
  384. }
  385. two=two->next;
  386. buffer=0;
  387. }
  388. i=0;
  389. freemem(ans);
  390. nodeptr ans1;
  391. ans1=malloc(sizeof(nodeptr));
  392. ans1->next=NULL;
  393. j=l2;
  394. while(j>=2){
  395.   addit(add[i],add[i+1],ans1);
  396.   add[i+1]=ans1;
  397.   i++;
  398.   j--;
  399. }
  400.  
  401.  
  402. printf("\n");
  403. list_print(add[l2-1]->next);
  404. }
  405. printf("\n written by Namit Sinha");
  406. getch();
  407. }

you can get the formatted version here   or download .txt from here   


can you help  improve the these  function ?   paste your functions in comments below :) 



1 comment:

  1. its better to implement a RPN style eval which could support random length operators

    ReplyDelete

Share your thoughts