Thread: help assignment due tomorrow

  1. #1
    Registered User
    Join Date
    Jan 2010
    Posts
    4

    help assignment due tomorrow

    ok guys this is due tomorrow, i am trying to fix my program in any way i can but it just seems impossible. all i have to do pretty much if you do not feel like reading the problem is read from a file as a string and then those 2 strings get them to either subtract or add, and compare in case of subtraction and then print them out. it seems easy but it is hard for me. i have done a lot, if someone could help me out i would really appreciate it. the code is below.

    Code:
    3
    2 9999999999 10000000000
    2 10000000000 9999999999
    1 8888888888 2222222222

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXLEN 201
        
    struct integer* read_integer(char* stringInt);
    void print(struct integer *p);
    struct integer* add(struct integer *p, struct integer *q);
    struct integer* subtract(struct integer *p, struct integer *q);
    int compare(struct integer *p, struct integer *q);
    
    struct integer{
        int *digits;
        int size;
    };
    
    int main(void){
        int numlines; //Number of lines stored in the file
        char string1[MAXLEN];
        char string2[MAXLEN];
        int i;// loop index
        int opr; //Operator 1 or 2 tells us if we add or subtract
        struct integer *p;
        struct integer *q;
        struct integer *answer;
    
        // Open the file and read from bigint.txt
        FILE *fin;
        fin = fopen("bigint.txt","r");
        fscanf(fin, "%d", &numlines); //Read in how many lines there are in the file
    
         // read a line (\n)
        // read the operator(1 or 2) - forget about this one. 3 fscanf
        //scanf first sting; call read int (1st) function
        //same with the second string
        //if 1 then call add, if 2 then call subtract
        // end of loop
        for(i = 0; i < numlines; i++)
        {
            fscanf(fin, "%d", &opr);  // find out whether its add or subtract
            fscanf(fin, "%s", string1); // scan in 2nd number on the first line of input file
                p = read_integer(string1); 
            fscanf(fin, "%s", string2);// scan in 3rd number on the first line of input file
                q = read_integer(string2);
        
            print(p);//call function to print out information
            printf(" ");
            print(q);
            printf("\n");
    
            if(opr == 1)
            {
             //add
              
              answer = add(p, q);
              print(answer = add(p, q));
            }
            else if(opr == 2)
            {
                printf("subtract here\n");
             // subtract func  
            }
        }
        
    
            
        fclose(fin);
        system("PAUSE");
        return 0;
    }
    
    //Preconditions: the first parameter is string that stores
    //               only contains digits, doesn't start with
    //               0, and is 200 or fewer characters long.
    //Postconditions: The function will read the digits of the
    //	large integer character by character, 
    //	convert them into integers and return a 
    //             pointer to the appropriate struct integer.
    struct integer* read_integer(char* stringInt)
    {
        int len;
        struct integer *myString;//create a new struct
        int i;//loop index
        //allocate memory for the struct
        myString = (struct integer*)(malloc(sizeof(struct integer)));
        
        len = strlen(stringInt); // length of the strinInt in digits
        
        myString->size = len; // length of string assigned to size in struct myString
        
        //allocate memory for digits
        myString->digits = (int*)(malloc(sizeof(int)* len));
        
        // assign number to digits, convert to integers
        for(i = 0; i < len; i++)
        {
            myString->digits[i] = stringInt [len-1-i] - '0';
        }
        return myString;
    }
    
    //Preconditions: p is a pointer to a big integer.
    //Postconditions: The big integer pointed to by p is 
    //                printed out.
    void print(struct integer *p)
    {
    //given pointer, want to print out digits in reverse order...
        int i;
        // no reversing in add or subtract, but want to reverse here
        for(i = p->size-1; i >= 0; i--)
        {
            printf("%d", p->digits[i]);
        }
        
    }
    //Preconditions: p and q are pointers to struct integers.
    //Postconditions: A new struct integer is created that 
    //                stores the sum of the integers pointed to 
    //                by p and q and a pointer to it is 
    //                returned.
    struct integer* add(struct integer *p, struct integer *q)
    {
        int i;
        struct integer *addAnsw; //create new struct for answer
        
        //Allocate memory for the new struct
        addAnsw = (struct integer*)(malloc(sizeof(struct integer)));
        
        //Allocate memory for the digits in the new struct addAnsw
        addAnsw->digits = (int*)(malloc(sizeof(int)* (p->size)));
        
      for(i = 1;i <2; i++)
        {
            printf("%d + %d = %d\n", p->digits[i], q->digits[i], addAnsw->digits[i]);
             addAnsw->digits[i] = p->digits[i] + q->digits[i];
        }
        
        return addAnsw;
    }
    
    //Preconditions: p and q are pointers to struct integers.
    //Postconditions: A new struct integer is created that 
    //                stores the absolute value of the 
    //                difference between the two and a pointer 
    //                to this is returned.
    struct integer* subtract(struct integer *p, struct integer *q)
    {
           struct integer *subtractAnsw;
           
          //Allocate memory for the new struct
          subtractAnsw = (struct integer*)(malloc(sizeof(struct integer)));
          
           if(p->size < q->size)
           {
                subtractAnsw->digits = (int*)(malloc(sizeof(int)*(p->size)));
           }   
    }
    
    //Preconditions: Both parameters of the function are 
    //	  pointers to struct integer. 
    //Postconditions: The function compares the digits of two 
    //	numbers and returns: 
    //    -1 if the first number is smaller than the second, 
    //     0 if the first number is equal to the second number,
    //   1 if the first number is greater than the second.
    Code:
    The Problem
    The unsigned int type in C requires 4 bytes of memory storage. With 4 bytes we can store integers as large as 232-1; but what if we need bigger integers, for example ones having hundreds of digits?  If we want to do arithmetic with such very large numbers we cannot simply use the unsigned data type. One way of dealing with this is to use a different storage structure for integers, such as an array of digits. We can represent an integer as an array of digits, where each digit is stored in a different array index. Since the integers are allowed to be as large as we like, a dynamically-sized array will prevent the possibility of overflows in representation. However we need new functions to add, subtract, compare, read and write these very large integers.  
    
    Write a program that will manipulate such arbitrarily large integers. Each integer should be represented as an array of digits, where the least significant digit is stored in index 0. Your program should we able to read in a string of digits and create a struct that stores the big integer.
    
    Your program should store each decimal digit (0-9) in a separate array element. In order to perform addition and subtraction more easily, it is better to store the digits in the array in the reverse order. For instance, the value 1234567890 would be stored as:
    
    index	0	1	2	3	4	5	6	7	8	9
    array	0	9	8	7	6	5	4	3	2	1
    
    Note: Although this seems counter-intuitive, it makes the code slightly easier, because in all standard mathematical operations, we start with the least significant digit. It also makes sense that the digit at the place 10i is stored in index i.
    
    Your program should include the following functions:
    
    •	a function that will convert a string to a struct integer
    •	a function that will print an integer
    •	a function that will add two integers and return the result
    •	a function that compares two integers and returns -1 if the first is less than the second, 0 if they are equal, and 1 if the first is greater than the second
    •	a function that will subtract one integer from the other and return the result. Since you’ll be dealing with positive integers only, the result should be a positive number. To ensure that the result is integer you should subtract the smaller number from the larger one. If they are equal, 0 should be returned
    
     
    Input/Output Specification
    Your program will read input from the file, “bigint.txt”, which will specify a number of addition and subtraction operations to carry out between pairs of large integers.
    
    The input file format is as follows:
    
    The first line will contain a single positive integer, n, representing the number of operations to carry out. The next n lines will contain one problem each. Each line will have three integers separated by white space. The first integer on each of these lines is guaranteed to either be 1 or 2, indicating addition and subtraction, respectively. The next two integers on the line will be the two operands for the problem. You may assume that these two integers are non-negative, are written with no leading zeros (unless the number itself is 0) and that the number of digits in either of the numbers will never exceed 200. (Note: Thus, the answer of the operation will never exceed 201 digits.)
    
    You should generate your output to the screen. In particular, you should generate one line of output per each input case. Your output should fit one of the two following formats:
    
    X + Y = Z
    X – Y = Z
    
    corresponding to which option was chosen. For the first option, always print the first operand first. For the second option, always print the larger of the two operands first. If the two operands are equal, the same number is printed both times.
    
    Implementation Restrictions
    You must use the following struct:
    
    struct integer {
    	int* digits;
    	int size;
    }
    
    Whenever you store or return a big integer, always make sure not to return it with any leading zeros. Namely, make sure that the value stored in index size-1 is NOT zero. The only exception to this rule is if 0 is being stored. 0 should be stored in an array of size 1.
    
     
    Here are the prototypes of the functions for you to write:
    
    //Preconditions: the first parameter is string that stores
    //               only contains digits, doesn't start with
    //               0, and is 200 or fewer characters long.
    //Postconditions: The function will read the digits of the
    //	large integer character by character, 
    //	convert them into integers and return a 
    //             pointer to the appropriate struct integer.
    struct integer* convert_integer(char* stringInt);
    
    //Preconditions: p is a pointer to a big integer.
    //Postconditions: The big integer pointed to by p is 
    //                printed out.
    void print(struct integer *p);
    
    //Preconditions: p and q are pointers to struct integers.
    //Postconditions: A new struct integer is created that 
    //                stores the sum of the integers pointed to 
    //                by p and q and a pointer to it is 
    //                returned.
    struct integer* add(struct integer *p, struct integer *q);
    
    //Preconditions: p and q are pointers to struct integers.
    //Postconditions: A new struct integer is created that 
    //                stores the absolute value of the 
    //                difference between the two and a pointer 
    //                to this is returned.
    struct integer* subtract(struct integer *p, struct integer *q);
    
    //Preconditions: Both parameters of the function are 
    //	  pointers to struct integer. 
    //Postconditions: The function compares the digits of two 
    //	numbers and returns: 
    //    -1 if the first number is smaller than the second, 
    //     0 if the first number is equal to the second number,
    //   1 if the first number is greater than the second.  
    int compare(struct integer *p, struct integer *q);
    
     
    Sample Input File
    3
    1 8888888888 2222222222
    2 9999999999 10000000000
    2 10000000000 9999999999
    
    Corresponding Output
    8888888888 + 2222222222 = 11111111110
    10000000000 – 9999999999 = 1
    10000000000 – 9999999999 = 1
    
    
    Deliverables
    Turn in a single file, bigint.c, over WebCourses that solves the specified problem. If you decide to make any enhancements to this program, clearly specify them in your header comment so the grader can test your program accordingly.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    The problem isn't doing the arithmetic with the huge integers. The problem is all the *stinking* assignment constraints!

    Hopefully, someone with an "I love pointers and malloc's" bent, will jump in here and assist.

    I can assist with the arithmetic algorithm using arrays for examples, in a similar way. I'll post them up when I'm done coding them.

    This shows some arithmetic code that you might find useful - won't help you with all the constraints the assignment has for you, however.

    This code is NOT tested, beyond a few trial runs, so watch it.
    Code:
    /* implements big number arithmetic - maybe :p :p
    
    status: untested & unknown
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define SIZE 201
    
    void add(char str1[], char str2[], int str1len, int str2len, char answer[]);
    void reset(char answer[], int str1len);
    void showIt(char s1[], int op, char s2[], char answer[]);
    void subtract(char str1[], char str2[], int str1len, int str2len, char answer[]);
    
    int main() {
    
      FILE *fptr;
      int i, j, str1len, str2len, steps, oper;
      char str1[SIZE], str2[SIZE], answer[SIZE];
      printf("\n\n\n\n\n\n");
      answer[0] = '\0';
      fptr=fopen("bigint.txt","r");
      if(fptr==NULL) {
        printf("\nError opening bigint.txt file - terminating program");
        exit(1);
      }
      fscanf(fptr,"%d",&steps);
      printf("\n Number of Steps: %d", steps);
      for(i = 0;i < steps; i++) {
        fscanf(fptr,"%d%s%s",&oper, str1, str2);
        printf("\nThe problem as it was received:");
        showIt(str1, oper, str2, answer);
        printf("\nThe problem as it will be solved:");
        str1len = strlen(str1);		//get it's length
        str2len = strlen(str2);
        if(str1len < str2len) {
          strcpy(answer, str1);
          strcpy(str1, str2);
          strcpy(str2, answer);
          j = str1len;
          str1len = str2len;
          str2len = j;
        }
        if(str1len == str2len) {
          if((strcmp(str1, str2)) < 0) {
            strcpy(answer, str1);
            strcpy(str1, str2);
            strcpy(str2, answer);
          }
        }
        reset(answer, str1len);
        showIt(str1, oper, str2, answer);
        strrev(str1);		          //reverse it
        strrev(str2);
        
        printf("\nThe answer is:");
        if(oper == 1) {
          add(str1, str2, str1len, str2len, answer);
          strrev(answer);
          strrev(str1);
          strrev(str2);
          showIt(str1, oper, str2, answer); 
        }
        if(oper == 2) {
          subtract(str1, str2, str1len, str2len, answer);
          strrev(answer);
          strrev(str1);
          strrev(str2);
          showIt(str1, oper, str2, answer);
        }
        reset(answer, str1len);
    
        if((i % 4) == 0) {
          printf("\n<< press enter to continue >>
          getchar();
        }
      }//next step
    
      fclose(fptr);
      printf("\n\n\t\t\t     press enter when ready");
      i = getchar(); 
      return 0;
    
    }
    
    void add(char str1[], char str2[], int str1len, int str2len, char answer[]) {  //add 
      int carry, d1, d2, i, sum; 
    
      carry = 0;	   	//a flag, 1 means there is a carry
      for (i = 0; i < str1len; i++) { 
        d1 = str1[i] - '0';       //get digit, convert to number
        if(i < str2len)
          d2 = str2[i] - '0';       //ditto
        else
          d2 = 0;
        sum = d1 + d2 + carry;		//sum up
        if (sum > 9) {	    	    //there's a carry
          sum -= 10; 
          carry = 1;              //decrease sum by 10 & set carry
        }
        else
          carry = 0;
        answer[i] = sum + '0';	      //convert back to char and save 
        }
      if (carry==1)			            //carry at end
        answer[i++]= '1';		          //last digit is 1
    
      answer[i] = '\0';		            //terminate string
    }
    void reset(char answer[], int str1len) {
      int i;
      for(i = 0; i <= str1len; i++)
            answer[i] = '\0';
    }
    void subtract(char str1[], char str2[], int str1len, int str2len, char answer[]) {
      char temp[SIZE];
      int d1, d2, d3, i, j;
    
      strcpy(temp, str1);
      for (i = 0; i < str1len; i++) { 
        d1 = str1[i] - '0';       //get digit, convert to number
        if(i < str2len) 
          d2 = str2[i] - '0';       //ditto
        else
          d2 = 0;
        if(d1 < d2) {
          d1 += 10;
          j = i+1;
          while(str1[j] == 0) {
            ++j;
          }
          d3 = str1[j] - '0';                    
          --d3;
          str1[j] = d3 + '0';
        }
        if(d2 < 0)
          d2 = 0;
        answer[i] = (d1 - d2) + '0';
      }
      --i;
      if(answer[i] == '0')
        answer[i] = '\0';
    
      strcpy(str1, temp);
    }
    
    void showIt(char s1[], int op, char s2[], char answer[])	{  
      char ch;
      if(op==1)            //op = 1 for add, 2 for subtract
        ch = '+';
      else if(op==2)
        ch = '-';
      else
        printf("\n The operator isn't recognized!");
      if(answer[0])
        printf("\n%s = %s %c %s", answer, s1, ch, s2);
      else
        printf("\nx = %s %c %s", s1, ch, s2);		
    }
    Last edited by Adak; 01-27-2010 at 05:38 AM.

  3. #3
    Registered User
    Join Date
    Jan 2010
    Posts
    4
    that seems to work great, the only thing i need to do is actually have a struct that my teacher requires me to. i fixed just a small error which was just a printf error so no big deal.

    Code:
    You must use the following struct:
    
    struct integer {
    	int* digits;
    	int size;
    }

  4. #4
    Registered User
    Join Date
    Jan 2010
    Posts
    4
    another problem is that it does not get rid of the 0s, so if we do 1000-999 it equals 0001. so i have to figure out how to get rid of that as well.

  5. #5
    Registered User
    Join Date
    Jan 2010
    Posts
    412
    Quote Originally Posted by wildiv View Post
    another problem is that it does not get rid of the 0s, so if we do 1000-999 it equals 0001. so i have to figure out how to get rid of that as well.
    You could do something like (untested, but the logic seems right to me)
    Code:
    int resultsize = result->size;
    int leading_zero = 1;
    int* tmp;
    while(resultsize && leading_zero)
    {
    	if(result->digits[resultsize] == 0)
    		resultsize--;
    	else
    		leading_zero = 0;
    }
    if(resultsize != result->size)
    {
    	tmp = result->digits;
    	result->digits = malloc(sizeof(int)*resultsize);
    	memcpy(result->digits, tmp, resultsize*sizeof(int));
    	result->size = resultsize;
    	free(tmp);
    }

  6. #6
    Registered User
    Join Date
    Jan 2010
    Posts
    4
    that i do not get at all sorry

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Your logic could be:

    1) Count from the most significant digit, how many 0's there are, before you hit the first non-zero digit. Call that value shiftNum.

    2) When you find the first non-zero digit (again, the program is scanning from the most significant digit to the 1's digit), then shift each digit to the left, shiftNum places.


Popular pages Recent additions subscribe to a feed

Similar Threads

  1. please help..linked list homework assignment due tomorrow..
    By rocketman03 in forum C Programming
    Replies: 2
    Last Post: 11-23-2008, 06:32 PM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. Replies: 1
    Last Post: 10-27-2006, 01:21 PM
  4. Need help with a C assignment due on 9/23 (Friday)
    By JohnnyBoy268 in forum C Programming
    Replies: 6
    Last Post: 09-23-2005, 12:59 AM
  5. need help with assignment due tonite
    By puckett_m in forum C Programming
    Replies: 4
    Last Post: 10-25-2001, 02:29 PM