Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Based on feedback on an earlier question, I decided to implement the addition of two big ints by putting multiple digits in a node of a linked list. Can somebody take a look at my code and let me know if I am on the right track.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


typedef struct node{
    int data;
    struct node* next;
} LList;

void printList(LList * list);

LList* pushToResult(LList* resultList,int entry){
    LList * temp = malloc(sizeof(LList));
    temp -> data = entry;
    temp -> next = resultList;
    resultList = temp;
    return resultList;
}

char* substr(char const* input,size_t start,size_t len){
    char *nstr = malloc(len+1);
    memcpy(nstr,input+start,len);
    nstr[len] = '\0';
    return nstr;
}

LList* convertToList(char* line){
    int i;
    int strSize = strlen(line);
    //Eight elements in every node
    int maxelem = 8;
    int currentPartition = 0;
    int currentIndex = 0;
    int totalPartitions = strSize/maxelem;
    LList* temp = NULL;

    for(i = 0;i < strSize - 1;i = i+maxelem){
        if(currentPartition >= totalPartitions){
            break;
        }

        char * currStr = substr(line,i,maxelem);
        int number = atoi(currStr);
        if(temp == NULL){
            temp = malloc(sizeof(LList));
            temp -> data = number;
            temp -> next = NULL;
        }else{
            LList * current = malloc(sizeof(LList));
            current -> data = number;
            current -> next = temp;
            temp = current;
        }
        currentIndex = i;
        currentPartition++;
    }
    currentIndex = currentIndex + maxelem;
    if((currentIndex > 0) && (currentIndex < (strSize - 1))){
        char * remainingStr = substr(line,currentIndex,strSize-1);
        int remainingNum = atoi(remainingStr);
        LList * current = malloc(sizeof(LList));
        current -> data = remainingNum;
        current -> next = temp;
        temp = current;
    }
    return temp;
}


void printList(LList * list){
    LList * counter = list;
    while( counter != NULL){
        printf(" %d ",counter -> data);
        counter = counter -> next;
    }
    printf("\n\n");
}

int main(){
    //Read number 1 from the input file into a linked list
    //The unit's place is the head and the most significant number is the tail
    //Read number 2 from the input file into a linked list
    //The unit's place is the head and the most significant number is the tail
    //Create temporary List where the elements will be added
    //Create the carry variable that will consist of the element's carry over after addition


    int counter = 0;
    ssize_t read;
    size_t len = 0;
    char * line = NULL;

    int carry = 0;  
    LList* num1 = NULL;
    LList* num2 = NULL;
    LList* result = NULL;   

    FILE * input = fopen("input.txt","r");
    if(input == NULL){
        exit(EXIT_FAILURE);
    }
    while((read = getline(&line,&len,input)) != -1){
        printf("Read the line %s",line);
        //If it's the first line
        if(counter == 0){
            num1 = convertToList(line);
            printf("Printing the list containing the num1(it will be in reversed order)\n");
            printList(num1);
        }else{
            num2 = convertToList(line);
            printf("Printing the list containing the num2(it will be in reversed order)\n");
            printList(num2);
        }
        counter++;
    }

    fclose(input);  

    while((num1 != NULL) || (num2 != NULL)){
        if(num1 != NULL){
            carry = carry + (num1->data);
            num1 = num1 -> next;
        }
        if(num2 != NULL){
            carry = carry + (num2 -> data);
            num2 = num2 -> next;
        }
        //Get the carry and the left over
        int carryOver = carry / 100000000;
        int leftOver = carry % 100000000;

        //put the left over in the result linked list
        //printf("Pushing the result into the result list");
        result = pushToResult(result,leftOver);
        carry = carryOver;

    }
    //Done with traversing the linked lists,if the carry is zero no need to push the value to the result
    //else push the value to the result
    if(carry != 0){
        result = pushToResult(result,carry);
    }

    //Print the result here
    printf("Printing out the result of the addition\n");
    printList(result);

}
share|improve this question
    
@palacsint I don't think the compiler requires you to type-cast void* from malloc when it's C (not C++). –  ChrisW Mar 15 at 13:19
    
@ChrisW: Thanks, renaming from .cpp to .c makes compilable with gcc. Close vote retracted. –  palacsint Mar 15 at 13:31
add comment

3 Answers 3

up vote 3 down vote accepted

Aside from the glaring bug, the major theme I see is that you can strive to generalize your code.

Examples:

  1. Instead of reading from input.txt, read from stdin. For less work, the user gets more flexibility.

  2. Why limit the program to adding two numbers, when you could add n numbers? It may be counterintuitive, but writing a program to add many lines of numbers would take less code, since you don't have to copy-and-paste the code to handle num1 and num2. (Start with an empty list, which represents an accumulator with an initial 0 value.)

  3. In ConvertToList(), you don't need a special case for if(temp == NULL){ … } — the general case works just fine. Also, it's weird that your temp variable has a longer lifespan than current. Therefore, I would consider temp to be misnamed. I suggest head instead.

share|improve this answer
add comment

By inspection, I see memory leaks everywhere. Every malloc() should have a corresponding free(), and there isn't a single call to free().

share|improve this answer
add comment

Your calculator gives erroneous results due to incorrect partition alignment when converting the input into linked lists. For example:

$ cat input.txt
122223
45555555555555555556
$ ./cr44425
Read the line 122223
Printing the list containing the num1(it will be in reversed order)


Read the line 45555555555555555556
Printing the list containing the num2(it will be in reversed order)
 5556  55555555  45555555 

Printing out the result of the addition
 45555555  55555555  5556

I expect the sum to be

45555555555555555556
+             122223
====================
45555555555555677779

(In my opinion, aggregating the digits to reduce the number of list nodes adds a lot of complication for questionable gains.)

share|improve this answer
    
Thanks for your input. Would it be possible to consolidate all your answers so that I can accept it. –  sc_ray Mar 16 at 4:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.