Menu driven program to represent polynomials as a data structure using arrays

Question

Write a menu-driven program to represent Polynomials as a data structure using arrays and write functions to add, subtract and multiply two polynomials; multiply a polynomial with a constant, find whether a polynomial is a “zero” polynomial, return the degree of the polynomial. Assume that a new polynomial is created after each operation.

I have used two arrays one for storing the terms of all the polynomials and another to store the beginning and ending indices of each polynomial. Only the non zero terms of the polynomials are stored except for the zero polynomial which I have represented as a single term having coefficient zero and exponent -1. The terms are stored in decreasing order of their exponents.

polynomial.h

#ifndef POLYNOMIAL_H_
#define POLYNOMIAL_H_

// all polynomials are stored in one array

// holds the current available index
extern int avail;

// reads a polynomial from the user and stores it
//
// Terms will be entered in decreasing order of exponents.
// Each term will be entered as the coefficient and the exponent respectively, separated by a space.
// Zero polynomial will consist of one term with coefficient 0 and exponent -1.
// 0 0 will be entered after the last term to terminate the input.
void read_poly();

// prints the polynomial stored at poly_idx
void print_poly(int poly_idx);

// returns whether the polynomial stored at poly_idx is a zero polynomial or not
int is_zero(int poly_idx);

// returns the degree of a polynomial stored at poly_idx
int get_deg(int poly_idx);

// multiplies the polynomial stored at poly_idx and stores the result
void mult_poly_const(int poly_idx, double k);

// adds the polynomials stored at poly1_idx and poly2_idx and stores the result
void add_poly(int poly1_idx, int poly2_idx);

// subtracts the polynomial stored at poly2_idx from that stored at poly1_idx
// and stores the result
void sub_poly(int poly1_idx, int poly2_idx);

// multiplies the polynomials stored at poly1_idx and poly2_idx and stores the result
void mult_poly(int poly1_idx, int poly2_idx);

#endif

polynomial.c

#include <stdio.h>
#include <limits.h>
#include <math.h>
#include "polynomial.h"

#define MAX_NO 100
#define MAX_TERMS 10000

#define EPS 0.0000005

struct term {
    double coef;
    int expon;
};

// For each polynomial, terms are stored in decreasing order of their exponents.
// All terms have nonzero coefficients, except for a zero polynomial
// which has a single term with coefficient zero and exponent -1.

// Stores the terms of all the polynomials
struct term terms[MAX_TERMS];

struct polynomial {
    // holds the starting index of the polynomial in the array terms
    int start;
    // holds the ending index of the polynomial in the array terms
    int end;
};

// Stores all the polynomials
struct polynomial polynomials[MAX_NO];

int avail = 0;

void read_poly()
{
    if (avail == 0) {
        polynomials[avail].start = 0;
    } else {
        polynomials[avail].start = polynomials[avail - 1].end + 1;
    }

    double coef;
    int expon;
    int i = polynomials[avail].start;
    while (1) {
        scanf("%lf%d", &coef, &expon);

         // To terminate the input
        if (coef == 0 && expon == 0) {
            break;
        }

        terms[i].coef = coef;
        terms[i].expon = expon;
        i++;
    }

    polynomials[avail].end = i - 1;

    avail++;
}

void print_poly(int poly_idx)
{
    for (int i = polynomials[poly_idx].start; i <= polynomials[poly_idx].end; i++) {
        if (i != polynomials[poly_idx].start) {
            printf("+ ");
        }

        if (terms[i].expon != 0) {
            printf("%lf * x ^ %d ", terms[i].coef, terms[i].expon);
        } else {
            // if the exponent is zero just the cofficient is printed
            printf("%lf ", terms[i].coef);
        }
    }
    printf("\n");
}

int is_zero(int poly_idx)
{
    if (polynomials[poly_idx].start == polynomials[poly_idx].end && fabs(terms[polynomials[poly_idx].start].coef) <= EPS) {
        return 1;
    }
    return 0;
}

int get_deg(int poly_idx)
{
    if (is_zero(poly_idx)) {
        return INT_MIN;
    } else {
        return terms[polynomials[poly_idx].start].expon;
    }
}

// Enters a zero polynomial at the index idx
void enter_zero_poly(int idx)
{
    if (idx == 0) {
        polynomials[idx].start = polynomials[idx].end = 0;
    } else {
        polynomials[idx].start = polynomials[idx].end = polynomials[idx - 1].end + 1;
    }

    terms[polynomials[idx].start].coef = 0;
    terms[polynomials[idx].start].expon = -1;
}

void mult_poly_const(int poly_idx, double k)
{
    if (k == 0) {
        enter_zero_poly(avail);
        avail++;
        return;
    }

    polynomials[avail].start = polynomials[avail - 1].end + 1;

    int res_term_idx = polynomials[avail].start; 
    for (int i = polynomials[poly_idx].start; i <= polynomials[poly_idx].end; i++) {
        terms[res_term_idx].coef = k * terms[i].coef;
        terms[res_term_idx].expon = terms[i].expon;
        res_term_idx++;
    }

    polynomials[avail].end = res_term_idx - 1;

    avail++;
}

void add_poly(int poly1_idx, int poly2_idx)
{
    polynomials[avail].start = polynomials[avail - 1].end + 1;

    // stores the answer if the answer is not a zero polynomial
    int i = polynomials[poly1_idx].start;
    int j = polynomials[poly2_idx].start;
    int k = polynomials[avail].start;
    while (i <= polynomials[poly1_idx].end || j <= polynomials[poly2_idx].end) {
        // if any of the term of any of the two polynomials is a zero term
        // then it is not processed
        // Will be required if atleast one of them is a zero polynomial
        if (i <= polynomials[poly1_idx].end && terms[i].coef == 0) {
            i++;
            continue;
        }
        if (j <= polynomials[poly2_idx].end && terms[j].coef == 0) {
            j++;
            continue;
        }

        if (i > polynomials[poly1_idx].end) {
            terms[k] = terms[j];
            j++;
            k++;
        } else if (j > polynomials[poly2_idx].end) {
            terms[k] = terms[i];
            i++;
            k++;
        } else if (terms[i].expon > terms[j].expon) {
            terms[k] = terms[i];
            i++;
            k++;
        } else if (terms[i].expon < terms[j].expon) {
            terms[k] = terms[j];
            j++;
            k++;
        } else {
            // only if the resulting term is not a zero term
            // it will be stored
            // since non zero terms are not stored
            if (terms[i].coef + terms[j].coef != 0) {
                terms[k].expon = terms[i].expon;
                terms[k].coef = terms[i].coef + terms[j].coef;
                i++;
                j++;
                k++;
            } else {
                i++;
                j++;
            }
        }
    }

    if (k == polynomials[avail].start) {
        // If the answer is a zero polynomial
        enter_zero_poly(avail);
    } else {
        polynomials[avail].end = k - 1;
    }

    avail++;
}

void sub_poly(int poly1_idx, int poly2_idx)
{
    polynomials[avail].start = polynomials[avail - 1].end + 1;

    // stores the answer if the answer is not a zero polynomial
    int i = polynomials[poly1_idx].start;
    int j = polynomials[poly2_idx].start;
    int k = polynomials[avail].start;
    while (i <= polynomials[poly1_idx].end || j <= polynomials[poly2_idx].end) {
        // if any of the term of any of the two polynomials is a zero term
        // then it is not processed
        // Will be required if atleast one of them is a zero polynomial
        if (i <= polynomials[poly1_idx].end && terms[i].coef == 0) {
            i++;
            continue;
        }
        if (j <= polynomials[poly2_idx].end && terms[j].coef == 0) {
            j++;
            continue;
        }

        if (i > polynomials[poly1_idx].end) {
            terms[k].expon = terms[j].expon;
            terms[k].coef = -terms[j].coef;
            j++;
            k++;
        } else if (j > polynomials[poly2_idx].end) {
            terms[k] = terms[i];
            i++;
            k++;
        } else if (terms[i].expon > terms[j].expon) {
            terms[k] = terms[i];
            i++;
            k++;
        } else if (terms[i].expon < terms[j].expon) {
            terms[k].expon = terms[j].expon;
            terms[k].coef = -terms[j].coef;
            j++;
            k++;
        } else {
            // only if the resulting term is not a zero term
            // it will be stored
            // since non zero terms are not stored
            if (terms[i].coef - terms[j].coef != 0) {
                terms[k].expon = terms[i].expon;
                terms[k].coef = terms[i].coef - terms[j].coef;
                i++;
                j++;
                k++;
            } else {
                i++;
                j++;
            }
        }
    }

    if (k == polynomials[avail].start) {
        // If the answer is a zero polynomial
        enter_zero_poly(avail);
    } else {
        polynomials[avail].end = k - 1;
    }

    avail++;
}

void mult_poly(int poly1_idx, int poly2_idx)
{
    if (is_zero(poly1_idx) || is_zero(poly2_idx)) {
        enter_zero_poly(avail);
        avail++;
        return;
    }

    polynomials[avail].start = polynomials[avail - 1].end + 1;

    // Storing the terms of the answer in sorted order of their exponents
    //
    // Some zero terms which arise in the answer will also be stored
    // and will be removed later.
    int new_term_idx = polynomials[avail].start; // holds the index where a new term will be stored
    for (int i = polynomials[poly1_idx].start; i <= polynomials[poly1_idx].end; i++) {
        for (int j = polynomials[poly2_idx].start; j <= polynomials[poly2_idx].end; j++) {
            struct term new = {terms[i].coef * terms[j].coef, terms[i].expon + terms[j].expon};

            int k = polynomials[avail].start;
            // finding if a term whose exponent is not greater than the new term's exponent exists
            // and the finding first such term if exists
            while (k < new_term_idx && new.expon < terms[k].expon) {
                k++;
            }

            if (k == new_term_idx) {
                // if such a term does not exist
                terms[k] = new;
                new_term_idx = k + 1;
            } else if (new.expon == terms[k].expon) {
                terms[k].coef += new.coef;
            } else {
                // moving all the terms from the found term to one place right
                // to make place for the new term
                for (int mv_idx = new_term_idx - 1; mv_idx >= k; mv_idx--) {
                    terms[mv_idx + 1] = terms[mv_idx];
                }

                // entering the new term
                terms[k] = new;

                new_term_idx++;
            }
        }
    }

    // scanning for zero terms and removing them
    for (int i = polynomials[avail].start; i < new_term_idx; i++) {
        if (terms[i].coef == 0) {
            // moving all terms after the current term to one place left
            // to overwrite the zero term
            for (int mv_idx = i + 1; mv_idx < new_term_idx; mv_idx++) {
                terms[mv_idx - 1] = terms[mv_idx];
            }
            new_term_idx--;
        }
    }

    polynomials[avail].end = new_term_idx - 1;

    avail++;
}

main.c

#include <stdio.h>
#include <limits.h>
#include "polynomial.h"

int main()
{
    printf("\nNew polynomials are created for all options except 2, 3, 4.\n");
    printf("They will be stored at the current index.\n\n");

    while (1) {
        // printing the options
        printf("Current index = %d\n", avail);
        printf("1. Enter a polynomial\n");
        printf("2. Print a polynomial\n");
        printf("3. Find whether a polynomial is a zero polynomial\n");
        printf("4. Find the degree of a polynomial\n");
        printf("5. Multiply a polynomial with a constant\n");
        printf("6. Add two polynomials\n");
        printf("7. Subtract two polynomials\n");
        printf("8. Multiply two polynomials\n");
        printf("Enter option(EOF to exit): ");

        // getting the option from the user
        int op;
        if (scanf("%d", &op) == EOF) { // to stop if EOF is received
            break;
        }
        printf("\n");

        // executing the actions according to the option entered
        switch(op) {
            case 1: {
                printf("Terms should be entered in decreasing order of exponents.\n");
                printf("Each term should be entered as the coefficient and the exponent respectively, separated by a space.\n");
                printf("Zero polynomial should consist of one term with coefficient 0 and exponent -1.\n");
                printf("Enter the polynomial with each non-zero term in a line(Enter 0 0 in the next line after the last term):\n");
                read_poly();
                break;
            }
            case 2: {
                printf("Enter the polynomial index: ");
                int poly_idx;
                scanf("%d", &poly_idx);
                print_poly(poly_idx);
                break;
            }
            case 3: {
                printf("Enter the polynomial index: ");
                int poly_idx;
                scanf("%d", &poly_idx);
                if (is_zero(poly_idx)) {
                    printf("It is a zero polynomial.\n");
                } else {
                    printf("It is not a zero polynomial.\n");
                }
                break;
            }
            case 4: {
                printf("Enter the polynomial index: ");
                int poly_idx;
                scanf("%d", &poly_idx);
                int deg = get_deg(poly_idx);
                if (deg == INT_MIN) { // for zero polynomial, degree is given as -inf
                    printf("-inf\n");
                } else {
                    printf("%d\n", deg);
                }
                break;
            }
            case 5: {
                printf("Enter the polynomial index and the constant respectively: ");
                int poly_idx;
                double k;
                scanf("%d%lf", &poly_idx, &k);
                mult_poly_const(poly_idx, k);
                break;
            }
            case 6: {
                printf("Enter the polynomial indices: ");
                int poly1_idx, poly2_idx;
                scanf("%d%d", &poly1_idx, &poly2_idx);
                add_poly(poly1_idx, poly2_idx);
                break;
            }
            case 7: {
                printf("Enter the polynomial indices: ");
                int poly1_idx, poly2_idx;
                scanf("%d%d", &poly1_idx, &poly2_idx);
                sub_poly(poly1_idx, poly2_idx);
                break;
            }
            case 8: {
                printf("Enter the polynomial indices: ");
                int poly1_idx, poly2_idx;
                scanf("%d%d", &poly1_idx, &poly2_idx);
                mult_poly(poly1_idx, poly2_idx);
                break;
            }
            default: {
                printf("Invalid option\n");
                break;
            }
        }

        printf("\n");
    }

    printf("\n");
    return 0;
}

The program works. This is the first time I have written a program of this size. Also it is the first time I have written a program which is not contained in one file. Is there any way I can improve it? Also I feel the polynomial.c file is too large. Should I try to break it up into smaller files?

Answer 1

• Don't repeat yourself

  add_poly and sub_poly are practically identical except in a single line

  terms[k].coef = terms[i].coef + terms[j].coef; // add
  terms[k].coef = terms[i].coef - terms[j].coef; // sub
  

  which strongly suggests that these functions should be unified. One possible approach is to express sub_poly in terms of add_poly. In pseudocode:

  sub_poly(first, second)
  {
      negated = mul_poly_const(second, -1);
      add_poly(first, negated);
  }
  

• Avoid naked loops

  Most loops implement an important algorithm, and hence deserve the name - especially if you feel obliged to comment them. In your case, the zero term removal is an obvious candidate to become a function. Notice that having and using such function would immensely simplify add_poly logics: just blindly add them term-wise, and remove zero terms in a second pass.

• Comparing doubles

  Comparing doubles for equality

  if (terms[i].coef + terms[j].coef != 0)
  

  almost never works. Usually the application defines some small \$\varepsilon\$, and considers doubles to be equal if they fall within \$\varepsilon\$ of each other. Maybe that's what the EPS was supposed to be (I didn't find it used anywhere).