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

Posted on

Problem

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.

// 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

// 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;

{
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++;
}

{
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.nn");

while (1) {
// printing the options
printf("Current index = %dn", avail);
printf("1. Enter a polynomialn");
printf("2. Print a polynomialn");
printf("3. Find whether a polynomial is a zero polynomialn");
printf("4. Find the degree of a polynomialn");
printf("5. Multiply a polynomial with a constantn");
printf("7. Subtract two polynomialsn");
printf("8. Multiply two polynomialsn");
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");
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("-infn");
} else {
printf("%dn", 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);
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 optionn");
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?

Solution

• 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);
}

• 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 ε$\epsilon$$varepsilon$, and considers doubles to be equal if they fall within ε$\epsilon$$varepsilon$ of each other. Maybe that’s what the EPS was supposed to be (I didn’t find it used anywhere).