COSC 2415 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies
Program 2 - Polynomial Class with a Dynamic Array
Final version. I will not make any changes unless I find problems.
Be sure to read through Section 6.3 in your textbook before starting this assignment.
A polynomial in one variable is an arithmetic expression of the form
anxn + ... + a2x2 + a1x1 + a0
where x is a variable that can take on different numeric values and an , ... , a2 , a1 , and a0 are constants called the coefficients of the polynomial. The highest exponent with non-zero coefficient, n, is called the degree of the polynomial. For example, 0x2 + 2x + 3 is normally written as 2x + 3 and has degree 1. Note that x1 is the same as x, and x0 is 1. A polynomial whose coefficients are all zero has degree -1. Note that a polynomial with degree 2 is called a quadratic polynomial.
One way to represent a polynomial is to use an array to hold the coefficients. A polynomial of degree n has n + 1 coefficients. An array of size k can hold the coefficients for a polynomial of degree k - 1 (or a smaller degree).
Below you will find code for a Polynomial class that uses an array to hold the polynomial coefficients (similar to the List class in section 6.2 of your textbook). It can represent a polynomial of any degree up to and including MAX_DEGREE (a global constant defined with the class). This class has the limitation that all Polynomials have the same "physical size". That is, they all have the same upper limit on the degree. You cannot have a Polynomial with degree larger than MAX_DEGREE.
Your assignment is to make two enhancements to this class. The first is to allow programmers to create Polynomials of any maximum degree. This is accomplished by using a dynamically-allocated array in the class, and by providing a constructor function that allows you to specify the maximum degree. This enhancement is similar to the List class described in section 6.3 of your textbook. The second enhancement is to provide a resize( ) member function that allows the maximum degree of a Polynomial to be changed after it is created. The following paragraphs describe these enhancements in more detail.
Modify the data members of the Polynomial class to use a dynamically-allocated array. You will need to add a data member, say called maxDegree, that stores the maximum degree that a Polynomial object can hold.
The default (no-argument) constructor will create a Polynomial using a dynamically-allocated array large enough to hold a polynomial of a default maximum degree, say called DEF_MAX_DEGREE. Remember that to hold the coefficients of a polynomial of degree n, you need n + 1 coefficients. You will need to add a second constructor to your class that allows the user to create a Polynomial of any maximum degree (this will be an integer parameter). Note: you can combine these into a single constructor by using a default parameter.
As noted in section 6.3 of your textbook, your new class will also need to have a destructor function, a copy constructor, and an overloaded assignment operator.
Add a public member function resize( ) that will increase or decrease the maximum degree of a polynomial. If the maximum degree is decreased, it will never be set smaller than the current degree.
// resize( ) - change the maximum degree of the polynomial
// void resize( int newMaxDegree );
// Precondition: None.
// Postcondition: The Polynomial's maximum degree has been changed to newMaxDrgree
// (but not less than the current degree).
Here is pseudocode for this function:
if newMaxDegree < degree
reset newMaxDegree to degree
if newMaxDegree is the same as maxDegree
don't need to do anything - return
dynamically allocate a new array large enough to hold a polynomial of degree newMaxDegree
copy the coefficients from the old array to the new array
free the memory for the old array
make the object point to the new array
reset the maxDegree
Change the setCoef( ) function so that it will automatically increase the maxDegree of a Polynomial if required (using the resize( ). Be sure to remove the precondition.
Be sure to update the documentation in the class to reflect your changes.
Code for a Polynomial class that uses an array to store the coefficients:
// Polynomial class header file
// Polynomial.h
// GLOBAL CONSTANT USED BY CLASS
// const int MAX_DEGREE = 5;
// The Polynomial class can represent a polymp,ia; of up to degree MAX_DEGREE.
// CONSTRUCTOR
// Polynomial( );
// Postcondition: A polynomial has been created. All coefficients are zero and
// the degree is -1.
// MODIFICATION MEMBER FUNCTIONS
// setCoef( ) - set a coefficient of the polynomial
// void setCoef( int k, double value );
// Precondition: The exponent k is less than or equal to MAX_DEGREE.
// Postcondition: The coefficient of the x^k term has been set to value.
// The degree of the polynomial has been adjusted as necessary.
// clear - set all coefficients to zero
// void clear( );
// Postcondition: All coefficients of the polynomial have been set to zero
// and the degree has been set to -1.
// ACCESSOR MEMBER FUNCTIONS
// getCoef( ) - returns a coefficient
// double getCoef( int k ) const;
// Postcondition: If k is less than or equal to the degree of the polynomial,
// the return value is the coefficient of x^k. Otherwise, the
// return value is zero.
// getDegree( ) - returns the degree
// int getDegree( ) const;
// Postcondition: The return value is the degree of the polynomial.
// evaluate( ) - evaluate the polynomial
// double evaluate(double value) const;
// Postcondition: The return value is the value of the polynomial at x = value.
// NON-MEMBER FUNCTIONS
// operator<<( ) - display the polynomial
// ostream & operator<<(ostream & out, const Polynomial & p);
// Postcondition: A character representation of Polynomial p has been inserted into
// output stream out.
// operator+( ) - defines the sum of two polynomials
// Polynomial operator+(const Polynomial & leftPoly, const Polynomial & rightPoly );
// Postcondition: The return value is the sum of leftPoly and rightPoly. Each coefficient
// of the result is the sum of the corresponding coefficients of leftPoly
// and rightPoly.
#include <iostream>
#ifndef POLYNOMIAL
#define POLYNOMIAL
const int MAX_DEGREE = 5;
class Polynomial
{
public:
// constructor
Polynomial( );
// modification member functions
void setCoef( int k, double value );
void clear( );
// accessor functions
double getCoef( int k ) const;
int getDegree( ) const;
double evaluate(double value) const;
private:
int degree;
double coef[MAX_DEGREE+1];
};
ostream & operator<<(ostream & out, const Polynomial & p);
Polynomial operator+(const Polynomial & leftPoly, const Polynomial & rightPoly );
#endif
// Polynomial class implementation file
// Polynomial.cpp
#include <iostream>
#include <cassert>
using namespace std;
#include "polynomial.h"
// Constructor
Polynomial::Polynomial( )
{
degree = -1;
for ( int i = 0; i <= MAX_DEGREE; i++ )
coef[i] = 0.0;
}
int Polynomial::getDegree( ) const
{
return degree;
}
double Polynomial::getCoef( int k ) const
{
if ( k <= degree )
return coef[k];
else
return 0.0; // all coefficients where the exponent is larger than the degree
// must be zero
}
void Polynomial::setCoef(int k, double value)
{
assert( k <= MAX_DEGREE );
coef[k] = value;
// fix the degree if necessary
if ( value != 0.0 && k > degree ) // degree inhcreased (but not past maxDegree)
degree = k;
// if terms with largest exponents are 0, decrease degree
int i = degree;
while ( i >= 0 && coef[i] == 0.0 )
{
degree--;
i--;
}
}
//-- Definition of <<
ostream & operator<<(ostream & out, const Polynomial & p)
{
if ( p.getDegree( ) == -1 )
{
cout << 0;
return out;
}
out << p.getCoef( p.getDegree( ) ) << "x^" << p.getDegree( );
for (int i = p.getDegree( )-1; i >= 0; i--)
{
out << " + ";
if ( p.getCoef( i ) < 0.0 )
out << '(' << p.getCoef( i ) << ')';
else
out << p.getCoef( i );
out << "x^" << i;
}
return out;
}
void Polynomial::clear( )
{
for ( int i = 0; i <= degree; i++ )
coef[i] = 0.0;
degree = -1;
}
void Polynomial::fixDegree( )
{
// if terms with largest exponents are 0, fix the degree
for ( int i = degree; i >= 0; i-- )
if ( coef[i] == 0.0 )
degree--;
}
//-- Definition of evaluate()
double Polynomial::evaluate(double value) const
{
double power = 1,
result = 0;
for (int i = 0; i <= degree; i++)
{
result += coef[i] * power;
power *= value;
}
return result;
}
//-- Definition of +
Polynomial operator+(const Polynomial & leftPoly, const Polynomial & rightPoly )
{
int leftDegree = leftPoly.getDegree( ),
rightDegree = rightPoly.getDegree( ),
degree;
double sum;
if ( leftDegree > rightDegree )
degree = leftDegree;
else
degree = rightDegree;
Polynomial resPoly;
for ( int i=degree; i >= 0; i-- )
{
sum = leftPoly.getCoef( i ) + rightPoly.getCoef( i );
if ( sum != 0.0 ) // Don't need to set coefficients that are 0.0
resPoly.setCoef( i, sum ); // Also makes sure that degree is correctly set
}
return resPoly;
}
A convenient way to test a class is to use a menu-driven driver. Here is a start on a program to help test your class.
#include <cctype> // Provides toupper
#include <iostream> // Provides cout and cin
#include <cstdlib> // Provides EXIT_SUCCESS
using namespace std;
#include "polynomial.h"
// PROTOTYPES:
void print_menu( );
// Postcondition: A menu of choices has been printed.
int get_number( );
// Postcondition: The user has been prompted to enter an integer number. The
// number has been read, echoed to the screen, and returned by the function.
Polynomial readPolynomial( )
{
int degree;
double value;
Polynomial poly;
cout << "Enter degree for polynomial: ";
cin >> degree;
for ( int i=degree; i>=0; i-- )
{
cout << "Enter coefficient for x^" << i << ": ";
cin >> value;
poly.setCoef( i, value );
}
return poly;
}
int main( )
{
char choice; // Command entered by the user
int num, exp;
double value;
Polynomial poly1, poly2;
cout << "creating 2 polynomials" << endl;
cout << "Initialize polynomial 1" << endl;
poly1 = readPolynomial( );
cout << "Initialize polynomial 2" << endl;
poly2 = readPolynomial( );
do
{
print_menu( );
cout << "Enter choice: ";
cin >> choice;
choice = toupper(choice);
switch (choice)
{
case 'C': // clear
break;
case 'E': // evaluate
break;
case 'P': // print polynomial
cout << "Print polynomial 1 or 2: ";
cin >> num;
if ( num == 1 )
cout << "poly1 is " << poly1 << endl;
else if ( num == 2 )
cout << "poly2 is " << poly2 << endl;
else
cout << "There are only 2 polynomials - 1 and 2" << endl;
break;
case 'S': // set a polynomial
cout << "Set polynomial 1 or 2: ";
cin >> num;
if ( num == 1 )
{
cout << "Enter exponent to select term (or a negative number to quit): ";
cin >> exp;
while ( exp >= 0 )
{
cout << "Enter value of coefficient: ";
cin >> value;
poly1.setCoef( exp, value );
cout << "Enter exponent to select term (or a negative number to quit): ";
cin >> exp;
}
cout << "poly1 is " << poly1 << endl;
}
else if ( num == 2 )
{
cout << "Enter exponent to select term (or a negative number to quit): ";
cin >> exp;
while ( exp >= 0 )
{
cout << "Enter value of coefficient: ";
cin >> value;
poly2.setCoef( exp, value );
cout << "Enter exponent to select term (or a negative number to quit): ";
cin >> exp;
}
cout << "poly2 is " << poly2 << endl;
}
else
cout << "There are only 2 polynomials - 1 and 2" << endl;
break;
case '+': // add polynomials 1 and 2
cout << "The sum of " << poly1 << endl;
cout << " and " << poly2 << endl;
cout << " is " << (poly1 + poly2) << endl;
break;
case 'Q': cout << "Test program ended." << endl;
break;
default: cout << choice << " is invalid." << endl;
}
}
while ((choice != 'Q'));
return EXIT_SUCCESS;
}
void print_menu( )
{
cout << endl;
cout << "The following choices are available: " << endl;
cout << " C Clear a polynomial" << endl;
cout << " E Evaluate a polynomial" << endl;
cout << " P Print a polynomial with degree" << endl;
cout << " S Set a polynomial" << endl;
cout << " + Add 2 polynomials" << endl;
cout << " Q Quit this test program" << endl;
}
char get_user_command( )
// Library facilities used: iostream
{
char command;
cout << "Enter choice: ";
cin >> command; // Input of characters skips blanks and newline character
return command;
}
int get_number( )
// Library facilities used: iostream
{
int result;
cout << "Please enter an integer number for the list: ";
cin >> result;
cout << result << " has been read." << endl;
return result;
}