How to implement polynomial class using linked list and monomial class C++

Question

So I need to create two classes one for Monomials. The other for polynomials (built using a linked list of Monomials).

I have the function declarations done and now I need to get into the definitions, which is where I'm stuck.

I think if I can get some direction on one function I'll be able to write the rest. Here is the direction I'm going with it, not sure if this is right. If it isn't can you point me in the right direction? Never used a the iterator thing so that's really throwing me off. Here is my header

#ifndef __POLYNOMIAL_H_
#define __POLYNOMIAL_H_

#include <iostream>
#include <list>
#include "Polynomial.cpp"

#define var = 'x' //varible to use in polynomial

using namespace std;

struct ZERO_T {
static const short ZERO = 0;
};
template <typename NumT>
class Monomial
{
public:
        Monomial<NumT>(NumT c = 0, int d = 0) : coeff(c), expo(d)
            { };
        NumT coefficient(void) const { return coeff; };
        int degree(void) const { return expo; };
        void assign_coefficient(const NumT c) { coeff = c; };
        void assign_degree(const int d) { expo = d; };
        bool operator==(const Monomial<NumT> & m) const
        {
            return (coeff == m.coeff && expo == m.expo);};
        bool operator!=(const Monomial<NumT> & m) const 
            {return (coeff != m.coeff || expo != m.expo);};

private:
        NumT coeff;
        int expo;
};
template <typename NumberType>
class Polynomial : public ZERO_T
{
public:
        Polynomial<NumberType>(NumberType c = 0, int d = 0)
        {
            const Monomial<NumberType> m(c, d);
            term_list.push_back(m); //creates a ZERO monomial
            number_of_terms = 1;
            highest_degree = d;
        }

        Polynomial<NumberType>(const Monomial<NumberType> & m) //type conversion constructor
        {
            term_list.push_back(m);
            number_of_terms = 1;
            highest_degree = m.degree();
        }

        ~Polynomial<NumberType>() { } // use default destructors and list's destructor

        Polynomial<NumberType>(const Polynomial<NumberType> & rhs) // copy constructor
            : term_list(rhs.term_list), number_of_terms(rhs.number_of_terms),
                highest_degree(rhs.highest_degree) { }

        const Polynomial<NumberType> & operator=(const Polynomial<NumberType> & rhs);
        //copy assignment 
        Polynomial<NumberType> operator+=(const Monomial<NumberType> &m);
        Polynomial<NumberType> operator+=(const Polynomial<NumberType> & rhs);
        const Polynomial<NumberType> operator+(const Monomial<NumberType> &m)const;
        const Polynomial<NumberType> operator+(const Polynomial<NumberType> & rhs) const;
        Polynomial<NumberType> operator*=(const Monomial<NumberType> &m);
        Polynomial<NumberType> operator*=(const Polynomial<NumberType> & rhs);
        const Polynomial<NumberType> operator*(const Monomial<NumberType>  &m) const;
        const Polynomial<NumberType> operator*(constPolynomial<NumberType> & rhs) const;
        const NumberType evaluate(NumberType x);
        bool operator==(const Polynomial<NumberType> &p) const;
        bool operator!=(const Polynomial<NumberType> &p) const;
        const int gethighestdegree();
        void read(istream & in = cin);
        void print(ostream & out = cout) const;
        //static Polynomial<NumberType> ZERO;
        private:
                list<Monomial<NumberType> > term_list;
                //sorted by decreasing degrees
                int number_of_terms;
                int highest_degree;
                void insert_in_poly(Polynomial<NumberType> & p, const Monomial<NumberType> & m);
                //helper function
                NumberType power(NumberType x, int n);
};
//template<> Polynomial<int> Polynomial<int>::ZERO = 0;
template <typename NumberType>
istream&operator>>(istream &  in, Polynomial<NumberType> & rhs);

template <typename NumberType>  
ostream& operator<<(ostream & out, const Polynomial<NumberType> & rhs);

#include "polynomial.cpp"
#endif

How would you do the add? Here's what I have so far:

#ifndef __POLYNOMIAL_CPP_
#define __POLYNOMIAL_CPP_

#include <iostream>
#include <cmath>
#include <list>
#include "polynomial.h"
#endif

template<typename NumberType>
const Polynomial<NumberType> Polynomial<NumberType>::operator+(const Monomial<NumberType>& m) const
{
int i = 0;
term_list.sort();  //sort list in decending order
term_list.reverse();  //rearrange into ascending order
Monomial temp;      //create a temp object to hold our monomial
temp.coeff = m.coeff;   
temp.expo = m.expo;     
/////////////////experiments here/////////
list <Monomial<NumberType>>::iterator itr;
itr = p.termlist.begin();
while (itr != p.termlist.end())       //traverse termlist until we reach end
{
    if (itr.expo == temp.expo)      //if temp exponents meet current list exponent
        itr insert(i, NumberType& temp);        //insert monomial here
    else
            i++;
}

Obviously I still need to doctor it up with what if the list is empty and what if the exponent match is never found and such. But for now I just want a simple add monomial to polynomial function to use as an example to build my other functions please.

Answer 1

After looking at your classes declarations I can see some issues and will try to mark up your existing code with comments to help you out. I will also suggest that since your classes are templates you should have 3 files to the class: ClassName.h, ClassName.inl & ClassName.cpp this will help you in the long run due to the behavior of templates. After making comments in your standing code I will then try to reconstruct your classes as they would appear in their respective files.

This Is What You Have

#ifndef __POLYNOMIAL_H_
#define __POLYNOMIAL_H_

#include <iostream>
#include <list>
#include "Polynomial.cpp" // Why including *.cpp?

#define var = 'x' //varible to use in polynomial

using namespace std;

struct ZERO_T {
   static const short ZERO = 0;
};

template <typename NumT>
class Monomial {
public:
    Monomial<NumT>(NumT c = 0, int d = 0) : coeff(c), expo(d)
        { };
    NumT coefficient(void) const { return coeff; };
    int degree(void) const { return expo; };
    void assign_coefficient(const NumT c) { coeff = c; };
    void assign_degree(const int d) { expo = d; };
    bool operator==(const Monomial<NumT> & m) const
    {
        return (coeff == m.coeff && expo == m.expo);};
    bool operator!=(const Monomial<NumT> & m) const 
        {return (coeff != m.coeff || expo != m.expo);};

private:
    NumT coeff;
    int expo;
};

template <typename NumberType>
class Polynomial : public ZERO_T {
public:
    Polynomial<NumberType>(NumberType c = 0, int d = 0) {
        const Monomial<NumberType> m(c, d);
        term_list.push_back(m); //creates a ZERO monomial
        number_of_terms = 1;
        highest_degree = d;
    }

    Polynomial<NumberType>(const Monomial<NumberType> & m) //type conversion constructor {
        term_list.push_back(m);
        number_of_terms = 1;
        highest_degree = m.degree();
    }

    ~Polynomial<NumberType>() { } // use default destructors and list's destructor

    Polynomial<NumberType>(const Polynomial<NumberType> & rhs) // copy constructor
        : term_list(rhs.term_list), number_of_terms(rhs.number_of_terms),
            highest_degree(rhs.highest_degree) { }

    const Polynomial<NumberType> & operator=(const Polynomial<NumberType> & rhs);
    //copy assignment 
    Polynomial<NumberType> operator+=(const Monomial<NumberType> &m);
    Polynomial<NumberType> operator+=(const Polynomial<NumberType> & rhs);
    const Polynomial<NumberType> operator+(const Monomial<NumberType> &m)const;
    const Polynomial<NumberType> operator+(const Polynomial<NumberType> & rhs) const;
    Polynomial<NumberType> operator*=(const Monomial<NumberType> &m);
    Polynomial<NumberType> operator*=(const Polynomial<NumberType> & rhs);
    const Polynomial<NumberType> operator*(const Monomial<NumberType>  &m) const;
    const Polynomial<NumberType> operator*(constPolynomial<NumberType> & rhs) const;
    const NumberType evaluate(NumberType x);
    bool operator==(const Polynomial<NumberType> &p) const;
    bool operator!=(const Polynomial<NumberType> &p) const;
    const int gethighestdegree();
    void read( istream & in = cin );
    void print( ostream & out = cout ) const;
    //static Polynomial<NumberType> ZERO;
    private:
            list<Monomial<NumberType> > term_list;
            //sorted by decreasing degrees
            int number_of_terms;
            int highest_degree;
            void insert_in_poly(Polynomial<NumberType> & p, const Monomial<NumberType> & m);
            //helper function
            NumberType power( NumberType x, int n );
};

//template<> Polynomial<int> Polynomial<int>::ZERO = 0;
template <typename NumberType>
istream& operator>>( istream &  in, Polynomial<NumberType> & rhs );

template <typename NumberType>  
ostream& operator<<( ostream & out, const Polynomial<NumberType> & rhs );

#include "polynomial.cpp" // Why include *.cpp?
#endif

If you noticed the comment I had about Why including Polynomial.cpp? You never want to include a CPP file in another file especially a header file. If you want an implementation file that you can include at the bottom of your header file that comes after your class definition and before the #endif directive for your header file's safeguard it should be an inline file as in ClassName.inl this way any type of inline methods that are not in your ClassName.cpp file or any template functions are defined in this implementation file which is another form of a header file. Your CPP files are reserved for the compiler to build object code and the header files both H & INL are used for look ups during compilation, and linking. The use of the inline file keeps your definitions - implementations separate from your declarations!

I will try to simplify your classes for easier reading while separating the declarations from the definitions.

Monomial.h

#ifndef MONOMIAL_H
#define MONOMIAL_H

template<typename NumT>
class Monomial {
private:
    NumT m_coeff;
    int  m_expo;

public:
    explicit Monomial( NumT c = 0, int d = 0 ); // Added Explicit since both parameters can be defaulted

    NumT coefficient() const;
    int  degree() const;

    void assignCoefficient( const NumT c );
    void assignDegree( const int d );

    bool operator==( const Monomial<NumT>& other ) const;
    bool operator!=( const Monomial<NumT>& other ) const;

private:
    Monomial( const Monomial& c ); // Not Implemented - Copy Constructor
    Monomial& operator=( const Monomial& c ); // Not Implemented - Assignment Operator

}; // Monomial

#include "Monomial.inl"

#endif // MONOMIAL_H

Monomial.inl

// -------------------------------------------------------------------------
// Monomial() - Constructor
template<typename NumT>
Monomial<NumT>::Monomial( NumT c, int d ) :
m_coeff( c ),
m_expo( d ) {
} // Monomial

// -------------------------------------------------------------------------
// coefficient()
template<typename NumT>
NumT Monomial<NumT>::coefficient() const {
    return m_coeff;
} // coefficient

// -------------------------------------------------------------------------
// degree()
template<typename NumT>
int Monomial<NumT>::degree() const {
    return m_expo;
} // degree

// -------------------------------------------------------------------------
// assignCoefficient()
template<typename NumT>
void Monomial<NumT>::assignCoefficient( const NumT c ) {
    m_coeff = c;
} // assignCoefficient

// -------------------------------------------------------------------------
// assignDegree()
template<typename NumT>
void Monomial<NumT>::assignDegree( const int d ) {
    m_expo = d; 
} // assignDegree

// -------------------------------------------------------------------------
// operator==()
template<typename NumT>
bool Monomial<NumT>::operator==( const Monomial<NumT>& other ) const {
    return ( m_coeff == other.m_coeff && m_expo == other.m_expo );
} // operator==

// -------------------------------------------------------------------------
// operator!=()
template<typename NumT>
bool Monomial<NumT>::operator!= ( const Monomial<NumT>& other ) const {
    return ( m_coeff != other.m_coeff || m_expo != other.m_expo );
} // operator!=

Monomial.cpp

#include "Monomial.h"

Polynomial.h

#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H

#include <iostream>
#include <list>

#include "Monomial.h"

#define var = 'x'

struct ZERO_T {
    static const short ZERO = 0;
};

template<typename NumberType>
class Polynomial : public ZERO_T {
    friend std::istream& operator>>( std::istream& in, const Polynomial<NumberType>& poly );
    friend std::ostream& operator<<( std::ostream& out, const Polynomial<NumberType>& poly );
private:
    list<Nomomial<NumberType>> m_lTerms;

    int m_iNumTerms;
    int m_iHighestDegree;

public:
    // Constructors & Destructors
    explicit Polynomial( NumberType c = 0, int d = 0 );
    Polynomial( const Monomial<NumberType>& m );
    Polynomial( const Polynomial<NumberType& rhs );
    // ~Polynomial(); // Default Okay

    // Assignment Operator
    const Polynomial<NumberType>& operator=( const Polynomial<NumberType>& rhs );

    // Comparison Operators
    bool operator==( const Polynomial<NumberType>& p ) const;
    bool operator!=( const Polynomial<NumberType>& p ) const;
    bool operator<(  const Polynomial<NumberType>& p ) const;
    bool operator<=( const Polynomial<NumberType>& p ) const;
    bool operator>(  const Polynomial<NumberType>& p ) const;
    bool operator>=( const Polynomial<NumberType>& p ) const;

    // Numerical Operators
    Polynomial<NumberType>& operator+=( const Monomial<NumberType>& m );
    Polynomial<NumberType>& operator+=( const Polynomial<NumberType>& rhs );
    Polynomial<NumberType>  operator+(  const Monomial<NumberType>& m ) const;
    Polynomial<NumberType>  operator+(  const Polynomial<NumberType>& rhs ) const;
    Polynomial<NumberType>& operator*=( const Monomial<NumberType>& m );
    Polynomial<NumberType>& operator*=( const Polynomial<NumberType>& rhs );
    Polynomial<NumberType>  operator*(  const Monomial<NumberType>& m ) const;
    Polynomial<NumberType>  operator*(  const Polynomial<NumberType& rhs ) const;

    // Public Member Functions
    int getHighestDegree() const;

    void read( std::istream& in = cin );
    void print( std::ostream& out = cout ) const;

private:
    void insertInPoly( Polynomial<NumberType>& p; const Monomial<NumberType>& m );
    NumberType power( NumberType x, int n );

}; // Polynomial

#include "Polynomial.inl"

#endif // POLYNOMIAL_H

Polynomial.inl

// -------------------------------------------------------------------------
// Polynomial()

// To save some time all of this class's implementations should be in here
// where template<typename T> needs to be defined, just as I did within 
// Monomial.inl

Polynomial.cpp

#include "Polynomial.h"

This style of layout separates the declarations from the definitions making the code easier to read and allowing it to be modular. This way a person or user who is using your classes doesn't have to worry about how these functions work they only need to see the declaration of what they return and what parameters they accept with a basic description of what kind of tasks the functions / methods perform. I also removed some lines of code that were not needed in the Monomial class since they were only being used by the Polynomial class #includes, #defines & structure and moved them into the Polynomial class where they are needed.

Now as to your question about how to do a specific task that you showed in your question such as how to do add I can give you some advice based off of what you already have shown.

If you are creating a stack variable of type Monomial called temp you need to use the template brackets for the variable as such:

Monomial<NumberType> temp; // You did define Monomial as a template type.

I see that you are setting both the coefficient & exponent of your passed in parameter of a Monomial<> type, it could be helpful to define the assignment operator in your Monomial class. You may want to also add other operators to your Monomial Class as well +, +=, *, *=, etc.

As for your implementation of adding two monomials that have equivalent exponents you are on the right track, you already have your comparison operators for you to see if they are equal or not, then when two Monomials: A & B can be added you need to add the two and store the answer in a temporary container and removed the two that you added together from the list, continue this process until no more terms can be added. Then take all of your temporarily stored terms and repopulate your class's list.

You have to remember that the numerical operators in your Polynomial are for adding & multiplying two Polynomials together. If you are trying to add two Monomials together then this is where you will need the operator in your Monomial class.

Answer 2

Why I don't like answering questions like this: In order to answer it you wind up doing half of someone's homework. Maybe they learn, maybe they don't, but lemme tell ya something. Cut and paste may get you through a class, but it leave you serving coffee and selling phones in real life.

I'm not even trying to optimize this code. The polynomial += polynomial operator is the worst way to do it. It is also the fastest to write.

OK. The Monomial class is largely the same. I add two methods and a friend function.

Monomial& operator+=(const Monomial & toadd)
{
    if (expo != toadd.expo)
    {
        throw "Mismatched exponents";
    }
    coeff += toadd.coeff;
    return *this;
}

Pretty simple. If the coefficients don't match, blow up. Otherwise add the coefficients and return a reference to the modified object.

I start with += because + is += called with a local copy

Monomial operator+(const Monomial & toadd) const
{
    return Monomial(*this) += toadd;
}

I toyed with passing in non const non reference toadd because somebody's getting copied, but wimped out and went for the familiar. I don't play games with the return because it is a trivial object to copy and any constructor logic will probably be elided if the compiler sees a need.

friend std::ostream& operator<<(std::ostream & out,
                                const Monomial<NumT> & rhs)
{
    out << rhs.coeff << '^' << rhs.expo;
    return out;
}

And a standard << override to test the results.

The Polynomial class I write entirely inside the class. There is usually nothing to be gained from spinning off the implementation of a template and this is no exception.

Polynomial & operator+=(const Monomial<NumberType> &m)
{
    auto found = std::find_if(term_list.begin(),
                              term_list.end(),
                              [&m] (const Monomial<NumberType> &mono)
                              {
                                  return mono.degree() == m.degree();
                              } );
    if (found != term_list.end())
    {
        *found += m;
    }
    else
    {
        term_list.push_back(m);
        highest_degree = std::max(m.degree(), highest_degree);
        number_of_terms++; // pointless variable. Should always equal term_list.size()
    }
    return *this;
}

I got rid of the sorting. There's not much point to sorting and resorting every time. Sorting every time is an O(n) that you're probably going to have to do anyway since Polynomial is built around std::list. Sort when the list is modified or don't sort at all. Anyway, I used std::find_if, which may have some container and ordering optimizations baked in, to do the look-up if the container is changed in the future.

Polynomial & operator+=(const Polynomial & rhs)
{
    for (auto & mono: rhs.term_list)
    {
        *this += mono;
    }
    return *this;
}

This is the laziest, stupidest way I could add two polynomials. Every monomial in rhs is added to this. Since polynomial + monomial inserts exponents that aren't there and adds to those that are, all monomials will be represented in the result. I'm pretty sure the time complexity can be reduced from O(n^2) to O(n) with some care and attention.

const Polynomial operator+(const Monomial<NumberType> &m) const
{
    return Polynomial (*this) += m;
}

const Polynomial operator+(const Polynomial & rhs) const
{
    return  Polynomial (*this) += rhs;
}

Same as last time the operator + simply copies and calls +=.

friend std::ostream& operator<<(std::ostream & out,
                                const Polynomial<NumberType> & rhs)
{
    if (!rhs.term_list.empty())
    {
        auto mono = rhs.term_list.begin();
        out << *mono;
        for (++mono; mono != rhs.term_list.end();++mono)
        {
            out << " + " << *mono;
        }
    }
    else
    {
        out << "empty";
    }
    return out;
}

And again a << overload for easy testing.

Finally some test code to make sure I'm not totally on crack.

#include <iostream>
#include "Polynomial.h"
using namespace std;

int main()
{
    Polynomial<int> p;

    p += Monomial<int>(100,0);
    p += Monomial<int>(1,1);
    p += Monomial<int>(0,2);
    p += Monomial<int>(1,3)+Monomial<int>(1,3);
    p += Monomial<int>(5,4);
    cout << p<<endl;

    auto p2 = p+ Monomial<int>(3,3);
    cout << p2 << endl;
    cout << p+p2<< endl;
}