Thread: Question on Classic big integer program

  1. #1
    Registered User
    Join Date
    Aug 2010
    Posts
    42

    Question on Classic big integer program

    So I'm doing the one where you have to use linked lists to add integers up to 200 digits long.

    I have the idea of what I want to do to make it happen but I'm struggling with a lot of coding.

    So the numbers are stored in a file. (this isnt the actual sample file just an example [20 long each for this one])

    1 88888888888888888888 11111111111111111111


    So my first problem is getting the input into my linked list. Our instructor said we would want them entered in reverse order so we can start adding at the beginning of the ll rather than the end. Which I know could be accomplished by just repeatedly adding nodes at the beginning of the list (loop)

    So I'm trying to use fgets to get the entire line of input since we dont know how long each number (except for the first will be 1 or 2 for add or subtract) then using strtok(with a space as the delimiter) to determine to use the add function or sub function then strtok again will get me the first big integer.

    we just learned in our lab about fgets and strtok so I'm really unsure of how these would be coded to do what the above paragraph explains.

    then once i have that figured out i would need a method of separating each digit so i can then move it into my linked list. if i understand correctly fgets gives you a pointer so i could use that to get the character and then atoi it to get the integer value then move it into my list?



    Basically I'm asking how do you code fgets and strtok to get this line of input into your program:
    1 88888888888888888888 11111111111111111111


    edit: note that this is the second program in a computer science 1 course so just keep the answers to that level of coding knowledge please.
    Last edited by DaNxTh3xMaNx; 09-04-2010 at 12:14 PM.

  2. #2
    Registered User
    Join Date
    Aug 2010
    Posts
    42
    Code:
        int add_sub;
       char *inputline[405];
     FILE *ifp= fopen("bigint.txt", "r");
     
     fgets(inputline, 405, ifp );

    OK I have the fgets working correctly. i ran it and it printed out the entire line like i wanted. still have trouble with strtok. i used it and it did correctly print out the 1 but how do i use it so i can get to the next section of the string?

    when you strtok it destroys the string right? so we would need to make a copy of the inputline used above? but how would i get that second part rather than just the first part again?

  3. #3
    Registered User
    Join Date
    Aug 2010
    Posts
    42
    So I found a sample program using strtok

    Code:
     
    character_pointer = strtok(inputline, " ");
    
    while (character_pointer != NULL)
    {
    printf ("%s\n", character_pointer);
    character_pointer = strtok(NULL, " ");
    };

    (note i changed the sample code to work in my program and this is the while loop that works for my program)

    so this does get me the 3 separate parts but I really don't understand how it works. Can someone explain this while loop to me? also do I need a loop for my code since i know there will be three numbers always and separated by spaces always?

  4. #4
    Registered User
    Join Date
    Aug 2010
    Posts
    42
    can anyone lend any form of help?

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    When you pass strtok() a NULL as it's first parameter, it continues on from it's last position in the string, is all - no magic involved.

    When strtok() finds no more of the delimiter in the string, it returns NULL, itself, and your while (test) then fails, and the loop stops.

  6. #6
    Registered User
    Join Date
    Aug 2010
    Posts
    35
    Quote Originally Posted by DaNxTh3xMaNx View Post
    So I found a sample program using strtok

    Code:
     
    character_pointer = strtok(inputline, " ");
    
    while (character_pointer != NULL)
    {
    printf ("%s\n", character_pointer);
    character_pointer = strtok(NULL, " ");
    };

    (note i changed the sample code to work in my program and this is the while loop that works for my program)

    so this does get me the 3 separate parts but I really don't understand how it works. Can someone explain this while loop to me? also do I need a loop for my code since i know there will be three numbers always and separated by spaces always?
    Okay, so strtok takes two arguments. The first is either a string - in which case it starts its "scanning" at the start of the specified string - or a null pointer, in which case it starts its scanning from where the previous call to strtok ended. The second argument is a string containing all the "delimiters" by which the string should be split up.

    strtok works by returning a pointer to the first non-delimiter character it finds, having replaced the first delimiter AFTER this point with a null character, thereby creating a null-terminated string. If it doesn't find any such string, it returns a null pointer.

    So, in your example, the first call to strtok returns a pointer to the first token (or "word"), separated by a space. Then (if the first call did not return a null pointer, which would imply that no tokens exist), it continues to loop through the string, pointing to (and printing) the next token each time, until eventually it fails to find a token.

    You should note, also, that because of the way strtok changes delimiters into null pointers, it is destructive to the original string. So, in this case, the inputline string would now be terminated by the null character that strtok placed at the end of the first token.

    You don't need a loop, but your alternative would be:

    Code:
    character_pointer = strtok(inputline, " ");
    printf("%s", character_pointer);
    character_pointer = strtok(NULL, " ");
    printf("%s", character_pointer);
    character_pointer = strtok(NULL, " ");
    printf("%s", character_pointer);
    So there's no real reason not to use a loop, since it's actually easier AND works for an arbitrary number of tokens.
    Last edited by AntP; 09-04-2010 at 02:00 PM.

  7. #7
    Registered User
    Join Date
    Aug 2010
    Posts
    42
    ok thanks. that should help me with the strtok and getting the numbers on their own.

    now i just need to get each character by itself.

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    You will need a loop now to put each digit into a node of your list. I wouldn't use atoi() because it's designed to change the entire string to an integer which 1) is not what you want and 2) would fail with big numbers.
    Code:
    lenString = strlen(longInt);
    
    for(i=0;i<lenString;i++) {
      //in pseudo code: (char - '0' is standard idiom to change char value to integer)
      digit going to your lists ith node = string[i] - '0';
    }
    You may want to change your i starting assignment to lenString and go backwards to 0, depending on your overall logic.

  9. #9
    Registered User
    Join Date
    Aug 2010
    Posts
    42
    ok so i got the above posts code working so i now have each digit individually. but i have a problem. i suck at using functions and when i try to use a function to do it, i get a bunch of errors that i didnt get when i just had it in main.

    Code:
    //the prototype for the real function
    //struct integer* read_integer(char* character_p);
    
    
    //im not far enough to return a struct integer* so i tried just using void and testing out this part
    
    void read_integer(char* character_p)
    {    int lenString;
           
     character_p = strtok(NULL, " ");
     lenString = strlen(character_p);
    
       for(i=0;i<lenString;i++) 
       {
      digit = character_p[i] - '0';
       printf("%d", digit);
       }
    };

    and then using

    read_integer(char* character_p)


    to call it, but i just cant get it to work at all. any ideas of what im doing wrong?

  10. #10
    Registered User
    Join Date
    Aug 2010
    Posts
    35
    Firstly, if you're getting errors, you should post the console output detailing them.

    I see a few problems with your code:

    - You don't want to include 'char*' in your function call. Just the pointer. The type is specified in the function definition.

    - Variables 'i' and 'digit' are undeclared. Add declarations for these as you did with lenString.

    - You don't want a semicolon after your closing brace.

    Also, I would probably do the strtok outside of the function and pass each token in separately.

  11. #11
    Registered User
    Join Date
    Aug 2010
    Posts
    42
    Alright I got the function code working now. My problem was that from my function prototype i just copy and pasted the line so i had the ; when i was trying to code the function.

    Now I'm trying to add the nodes to the list and I think I have it coded right but I'm getting a warning.

    after main i have the function:
    Code:
     struct integer* read_integer(char* character_p)
    {
     lenString = strlen(character_p);
     
      struct integer* bigint;
      bigint = (struct integer*)malloc(lenString*sizeof(struct integer));
      struct integer* mylist;
      mylist = NULL;
    
       for(i=0;i<lenString;i++) 
       {
       bigint[i].digit = character_p[i] - '0';
       next = mylist;
       mylist = &bigint[i].digit;
       printf("%d", bigint[i].digit);
       }
       return mylist;
    }

    there is an assignment from incompatible pointer type on the bolded line. I don't see whats wrong with it. Anyone know what is? and how to fix it? (Note: the function still prints the big integer correctly)

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    What is the type of bigint[i].digit? I would guess that it is not a struct integer.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User
    Join Date
    Aug 2010
    Posts
    42
    Code:
    struct integer{
           int digit;
           struct integer *next;
           };
    that is my structure and this was in the post above

    Code:
     struct integer* bigint;
      bigint = (struct integer*)malloc(lenString*sizeof(struct integer));

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Good. Observe that mylist is a pointer to struct integer. Since bigint[i].digit is an int, &bigint[i].digit is an int*, so you are trying to assign an int* to a struct integer*, hence the assignment from incompatible pointer type.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User
    Join Date
    Aug 2010
    Posts
    42
    Quote Originally Posted by laserlight View Post
    Good. Observe that mylist is a pointer to struct integer. Since bigint[i].digit is an int, &bigint[i].digit is an int*, so you are trying to assign an int* to a struct integer*, hence the assignment from incompatible pointer type.
    ok, well i understand that and it makes sense but I don't really know what to do to fix it.

    my goal is to have mylist be my head pointer to my linked list.

    i just tried to use

    Code:
    mylist = &(struct integer*)bigint[i].digit;
    and got the error invalid l value in unary `&'



    edit: got it. i needed it before the &


    thanks for the help.
    Last edited by DaNxTh3xMaNx; 09-05-2010 at 11:57 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Random Question Assign Program
    By mikeprogram in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2005, 10:04 PM
  2. Help with homework please
    By vleonte in forum C Programming
    Replies: 20
    Last Post: 10-13-2003, 11:16 AM
  3. fopen();
    By GanglyLamb in forum C Programming
    Replies: 8
    Last Post: 11-03-2002, 12:39 PM
  4. Newbies question about the integer type
    By Unregistered in forum C++ Programming
    Replies: 2
    Last Post: 10-17-2001, 08:09 PM