Polynomial Addition that contains 3 variables in C

Question

This was given as a coding exercise for us. I've seen many examples around but they mostly use only one variable x. For this one, the two polynomials could contain at most 3 variables.

Let me explain the inputs. First line denotes the number of terms (non-zero coefficients) n for the first polynomial. The next n lines represent every term of the first polynomial in the form x exponent y exponent z exponent coefficient. Example: 4x⁵y⁴z² would be 5 4 2 4. The next line would be the same thing, but it will be for the second polynomial. We are to return the resulting sum and print them line by line in canonical order. The coefficient is a real number that may be signed or unsigned. I will provide a test case.

I've researched and formulated all the tasks. In fact, the test case that I will be providing can be answered correctly by my code. My problem is, there are hidden cases where my code gives wrong answers, and I am starting to think that my algorithm missed something.

Anyway, here is my whole code.

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

struct Node
{

    float coeff;
    int powX;
    int powY;
    int powZ;
    struct Node* next;
};


void readPolynomial(struct Node** poly)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    *poly = temp;

    int terms;
    fscanf(stdin, "%d", &terms);
    getchar();

    char entry[999999];
    char *splitter;
    for(int i = 0; i < terms; i++)
    {
        fgets(entry, sizeof(entry), stdin);
        splitter = strtok(entry," ");
        temp->powX = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->powY = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->powZ = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->coeff = atof(splitter);
        temp->next = NULL;
        if(i != terms-1)
        {
            temp->next = (struct Node*)malloc(sizeof(struct Node));
            temp = temp->next;
            temp->next = NULL;
        }
    }
}

int compareTerms(const struct Node *a, const struct Node *b)
{
    int cmp;

    cmp = (a->powX > b->powX) - (a->powX < b->powX);
    if (cmp != 0) {
        return cmp;
    }
    cmp = (a->powY > b->powY) - (a->powY < b->powY);
    if (cmp != 0) {
        return cmp;
    }
    cmp = (a->powZ > b->powZ) - (a->powZ < b->powZ);
    return cmp;
}

void sortPolynomialTerms(struct Node **poly)
{
    struct Node *head;
    unsigned int sublen;

    head = *poly;
    if (!head) {

        return;
    }

    sublen = 1;
    while (1) {
        struct Node *tail;
        struct Node *p;
        struct Node *q;
        struct Node *e;
        unsigned int plen;
        unsigned int qlen;
        unsigned int merges;
        unsigned int i;

        p = head;
        head = NULL;
        tail = NULL;
        merges = 0;
        while (p) {
            merges++;
            q = p;
            plen = 0;
            for (i = 0; i < sublen; i++) {
                plen++;
                q = q->next;
                if (!q) {
                    break;
                }
            }

            qlen = plen;

            while (plen || (qlen && q)) {
                if (!plen || (qlen && q && compareTerms(p, q) < 0)) {
                    e = q;
                    q = q->next;
                    qlen--;
                } else {
                    e = p;
                    p = p->next;
                    plen--;
                }
                if (tail) {
                    tail->next = e;
                } else {
                    head = e;
                }
                tail = e;
            }

            p = q;
        }
        tail->next = NULL;

        if (merges <= 1) {
            break;
        }

        sublen *= 2;
    }

    *poly = head;
}

void printPolynomial(const struct Node *poly)
{
    while (poly)
    {
        if(poly->coeff != 0)
        {
                printf("%d %d %d %.3f\n", poly->powX, poly->powY, poly->powZ, poly->coeff);
        }
        poly = poly->next;
    }
}

void canonicalPolynomial(struct Node **poly)
{
    sortPolynomialTerms(poly);
    printPolynomial(*poly);
}

void addPolynomials(struct Node** result, struct Node* first, struct Node* second)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->next = NULL;
    *result = temp;
    while(first && second)
    {
        if(compareTerms(first, second) < 0)
        {
            temp->coeff = second->coeff;
            temp->powX = second->powX;
            temp->powY = second->powY;
            temp->powZ = second->powZ;
            second = second->next;

        }
        else if(compareTerms(first, second) > 0)
        {
            temp->coeff = first->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
        }
        else
        {
            temp->coeff = first->coeff + second->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
            second = second->next;
        }
        if(first && second)
        {
            temp->next = (struct Node*)malloc(sizeof(struct Node));
            temp = temp->next;
            temp->next = NULL;
        }
    }
    while(first || second)
    {
        temp->next = (struct Node*)malloc(sizeof(struct Node));
        temp = temp->next;
        temp->next = NULL;

        if(second)
        {
            temp->coeff = second->coeff;
            temp->powX = second->powX;
            temp->powY = second->powY;
            temp->powZ = second->powZ;
            second = second->next;
        }

        else if(first)
        {
            temp->coeff = first->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
        }
    }
}

int main()
{
    struct Node* first = NULL;
    struct Node* second = NULL;
    struct Node* result = NULL;

    readPolynomial(&first);
    readPolynomial(&second);
    addPolynomials(&result, first, second);
    canonicalPolynomial(&result);
    return 0;
}

Test Case:

3
1 6 0 -7
0 7 0 -6
7 0 0 1
5
1 0 1 9
0 7 0 -2
5 3 2 4
1 2 3 4
1 3 0 3

Expected Output:

7 0 0 1.000
5 3 2 4.000
1 6 0 -7.000
1 3 0 3.000
1 2 3 4.000
1 0 1 9.000
0 7 0 -8.000

Explanation:

     x⁷           - 7xy⁶                       - 6y⁷
 +        4x⁵y³z²        + 3xy³ + 4xy²z³ + 9xz - 2y⁷

 =   x⁷ + 4x⁵y⁴z² - 7xy⁶ + 3xy³ + 4xy²z³ + 9xz - 8y⁷

Initially, I think there is a problem in my addPolynomial function. I just took it off from the example codes for Polynomial Addition of one variable and made some revisions.

checkTerms traverses the whole Polynomial and adds adjacent terms if they have the same degrees.

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

struct Node
{

    float coeff;
    int powX;
    int powY;
    int powZ;
    struct Node* next;
};


void readPolynomial(struct Node** poly)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    *poly = temp;

    int terms;
    fscanf(stdin, "%d", &terms);
    getchar();

    char entry[30];
    char *splitter;
    for(int i = 0; i < terms; i++)
    {
        fgets(entry, sizeof(entry), stdin);
        splitter = strtok(entry," ");
        temp->powX = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->powY = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->powZ = atoi(splitter);
        splitter = strtok(NULL, " ");
        temp->coeff = atof(splitter);
        temp->next = NULL;
        if(i != terms-1)
        {
            temp->next = (struct Node*)malloc(sizeof(struct Node));
            temp = temp->next;
            temp->next = NULL;
        }
    }
}

int compareTerms(const struct Node *a, const struct Node *b)
{
    int cmp;

    cmp = (a->powX > b->powX) - (a->powX < b->powX);
    if (cmp != 0) {
        return cmp;
    }
    cmp = (a->powY > b->powY) - (a->powY < b->powY);
    if (cmp != 0) {
        return cmp;
    }
    cmp = (a->powZ > b->powZ) - (a->powZ < b->powZ);
    return cmp;
}

void sortPolynomialTerms(struct Node **poly)
{
    struct Node *head;
    unsigned int sublen;

    head = *poly;
    if (!head) {

        return;
    }

    sublen = 1;
    while (1) {
        struct Node *tail;
        struct Node *p;
        struct Node *q;
        struct Node *e;
        unsigned int plen;
        unsigned int qlen;
        unsigned int merges;
        unsigned int i;

        p = head;
        head = NULL;
        tail = NULL;
        merges = 0;
        while (p) {
            merges++;
            q = p;
            plen = 0;
            for (i = 0; i < sublen; i++) {
                plen++;
                q = q->next;
                if (!q) {
                    break;
                }
            }

            qlen = plen;

            while (plen || (qlen && q)) {
                if (!plen || (qlen && q && compareTerms(p, q) < 0)) {
                    e = q;
                    q = q->next;
                    qlen--;
                } else {
                    e = p;
                    p = p->next;
                    plen--;
                }
                if (tail) {
                    tail->next = e;
                } else {
                    head = e;
                }
                tail = e;
            }

            p = q;
        }
        tail->next = NULL;

        if (merges <= 1) {
            break;
        }

        sublen *= 2;
    }

    *poly = head;
}

void printPolynomial(const struct Node *poly)
{
    while (poly)
    {
        if(poly->coeff != 0)
        {
                printf("%d %d %d %.3f\n", poly->powX, poly->powY, poly->powZ, poly->coeff);
        }
        poly = poly->next;
    }
}

void canonicalPolynomial(struct Node **poly)
{
    sortPolynomialTerms(poly);
    printPolynomial(*poly);
}

void checkTerms(struct Node* poly)
{
    while(poly)
    {
        if(poly->next != NULL)
        {
            if(compareTerms(poly, poly->next) == 0)
            {
                poly->coeff = poly->coeff + poly->next->coeff;
                poly->next = poly->next->next;
            }
        }
        poly = poly->next;
    }
}


void addPolynomials(struct Node** result, struct Node* first, struct Node* second)
{
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->next = NULL;
    *result = temp;
    while(first && second)
    {
        if(compareTerms(first, second) < 0)
        {
            temp->coeff = second->coeff;
            temp->powX = second->powX;
            temp->powY = second->powY;
            temp->powZ = second->powZ;
            second = second->next;

        }
        else if(compareTerms(first, second) > 0)
        {
            temp->coeff = first->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
        }
        else
        {
            temp->coeff = first->coeff + second->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
            second = second->next;
        }
        if(first && second)
        {
            temp->next = (struct Node*)malloc(sizeof(struct Node));
            temp = temp->next;
            temp->next = NULL;
        }
    }
    while(first || second)
    {
        temp->next = (struct Node*)malloc(sizeof(struct Node));
        temp = temp->next;
        temp->next = NULL;

        if(second)
        {
            temp->coeff = second->coeff;
            temp->powX = second->powX;
            temp->powY = second->powY;
            temp->powZ = second->powZ;
            second = second->next;
        }

        else if(first)
        {
            temp->coeff = first->coeff;
            temp->powX = first->powX;
            temp->powY = first->powY;
            temp->powZ = first->powZ;
            first = first->next;
        }
    }
}

int main()
{
    struct Node* first = NULL;
    struct Node* second = NULL;
    struct Node* result = NULL;

    readPolynomial(&first);
    readPolynomial(&second);
    sortPolynomialTerms(&first);
    checkTerms(&first);
    sortPolynomialTerms(&second);
    checkTerms(&second);
    addPolynomials(&result, first, second);
    canonicalPolynomial(&result);
    return 0;
}

Answer 1

I think it could be written in a much concise manner. Could you please try with this code? My approach is quite similar to the one by @tstanisl.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<float.h>

static int comparefn(const void *a, const void *b)
{
  const double *l= (const double *) a;
  const double *r= (const double *) b;
  for(int i= 0; i< 3; ++i) {
    if(l[i]< r[i]) { return -1; }
    if(l[i]> r[i]) { return 1; }
    if(l[0]== r[0]) { continue; }
  }
  return 0;
}

double *data= NULL;
int main(int argc, char *argv[])
{
  int n1= 0;
  scanf("%d", &n1);
  data= malloc(sizeof(double)* n1* 4);
  int i= 0;
  for(; i< n1; ++i) {
    scanf("%lf %lf %lf %lf", data+ i* 4, data+ i* 4+ 1, data+ i* 4+ 2, data+ i* 4+ 3);
  }

  int n2= 0;
  scanf("%d", &n2);
  data= realloc(data, sizeof(double)* (n1+ n2)* 4);
  for(; i< n1+ n2; ++i) {
    scanf("%lf %lf %lf %lf", data+ i* 4, data+ i* 4+ 1, data+ i* 4+ 2, data+ i* 4+ 3);
  }

  qsort(data, ((size_t) (n1+ n2)), sizeof(double)* 4, &comparefn);
  for(i= 1; i< n1+ n2; ++i) {
    if(0== comparefn(data+ i* 4, data+ (i- 1)* 4)) {
      data[i* 4+ 3]+= data[(i- 1)* 4+ 3]; data[(i- 1)* 4+ 3]= 0.0;
    }
  }
  for(i= n1+ n2- 1; i> -1; --i) {
    if(fabs(data[i* 4+ 3])> DBL_EPSILON) {
      printf("%g %g %g %.3lf\n", data[i* 4], data[i* 4+ 1], data[i* 4+ 2], data[i* 4+ 3]);
    }
  }

  if(NULL!= data) {
    free(data);
    data= NULL;
  }

  return 0;
}

Answer 2

There is no need to use lists. As the size of introduced polynomial is given in advance it is possible to allocate a sufficient. Next use realloc() to load the other polynomial. There is a problem with definition of zero coefficient. The precision should be specified. I assumed it is 0.

The problem can be solved in phases:

• read size of 1st polynomial
• alloc array
• load 1st polynomial
• read size of 2nd poly
• realloc array to fit both polynomials
• read 2nd poly
• sort terms to ensure that all terms with the same exponents are neighbours
• accumulate chunks of consecutive terms with same exponents
• print result

The code. Error handling is omitted.

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

struct term {
    int x, y, z;
    double coef;
};

struct term load_term() {
    struct term T;
    scanf("%d %d %d %lf", &T.x, &T.y, &T.z, &T.coef);
    return T;
}

int term_cmp(const void *a_, const void *b_) {
    const struct term *a = a_, *b = b_;
    if (a->x != b->x) return b->x - a->x;
    if (a->y != b->y) return b->y - a->y;
    return b->z - a->z;
}

int main() {
    int n = 0, m;

    // load first polynomial
    scanf("%d", &m);
    struct term *P = malloc(m * sizeof *P);
    while (m--) P[n++] = load_term();

    // load second polynomial
    scanf("%d", &m);
    P = realloc(P, (n + m) * sizeof *P);
    while (m--) P[n++] = load_term();

    // sort by x,y,z exponents
    qsort(P, n, sizeof *P, term_cmp);

    // merge
    int n2 = 0;
    for (int i = 0; i < n; ++i) {
        if (n2 > 0 && term_cmp(&P[n2 - 1], &P[i]) == 0) {
            // as long as exponents are the same as the last
            // accumulate coefficients to the last term
            P[n2 - 1].coef += P[i].coef;
        } else {
            // start a new term
            P[n2++] = P[i];
        }
    }

    // print accumulated polynomial of size `n2`
    for (int i = 0; i < n2; ++i)
           if (P[i].coef != 0)
        printf("%d %d %d %.3lf\n", P[i].x, P[i].y, P[i].z, P[i].coef);

    free(P);
}