/* * File: stack.cpp * Author: Leonid Reyzin * Date: January 2003 * Class: CS112B1 * Assignment: Implementation of an ordered linked list * -------------------------------------------------------------------- */ #include "polynomial.h" /* declarations of the class */ /*------------------------------------------------------------*/ /* Monomial::Monomial() constructor * Initializes a Monomial to point to NULL */ Monomial::Monomial() { next = NULL; } /*------------------------------------------------------------*/ /* Monomial::Monomial(newitem, newnext) constructor * Initializes a Monomial to contain newitem and point * to newnext */ Monomial::Monomial(int newdegree, float newcoeff, Monomial * newnext) { degree = newdegree; coeff = newcoeff; next = newnext; } /*------------------------------------------------------------*/ /* Polynomial::Polynomial constructor * creates a polynomial and initializes it to 0 */ Polynomial::Polynomial() { list = NULL; } /*------------------------------------------------------------*/ /* Polynomial::~Polynomial destructor * frees up the memory taken up by a polynomial */ Polynomial::~Polynomial() { Init(); } /*------------------------------------------------------------*/ /* Polynomial::Init: * Empties and re-initializes a polynomial to 0 */ bool Polynomial::Init() { Monomial * newlist; while (list != NULL) { newlist = list->next; delete list; list = newlist; } list=NULL; return true; } /*------------------------------------------------------------*/ /* Polynomial::IsZero: * checks whether a polynomial is zero. */ bool Polynomial::IsZero() const { return (list==NULL); } /*------------------------------------------------------------*/ /* Polynomial::AddMonomial: * Adds a monomial to a polynomial * returns true if successful, false if out of memory */ bool Polynomial::AddMonomial(int degree, float coeff) { Monomial *newnode, *biggernode, *smallernode=NULL; if (coeff==0.0) // Nothing to do return true; // Find the location where to insert. At the end of this loop, // biggernode will point to the node at or after the insertion point // (or NULL if insertion is at the end of the list), while smallernode // will point to the node before the insertion point // (or NULL if insertion is at the beginnig of the list) for (biggernode = list; biggernode != NULL; biggernode = biggernode->next) { if (biggernode->degree <= degree) break; smallernode = biggernode; } // If the degree of bigger node is the same as degree, we simply // add two coeeficients without creating a new node if (biggernode!=NULL && biggernode->degree == degree) { biggernode->coeff+=coeff; // It's possible that this addition produced a zero coefficient, // in which case the node must be removed if (biggernode->coeff==0.0) { if (smallernode == NULL) list = biggernode->next; else smallernode->next = biggernode->next; delete biggernode; } } // Create a new node and insert it before biggernode else { newnode = new Monomial(degree, coeff, biggernode); if (newnode == NULL) return false; if (smallernode == NULL) // special case: insertion at the beginning list = newnode; else // general case smallernode->next = newnode; } return true; } /*------------------------------------------------------------*/ /* Polynomial::EqualToSum * Sets the current polynomial equal to the sum of the * two arguments * returns true if successful, false if out of memory */ bool Polynomial::EqualToSum(const Polynomial * addend1, const Polynomial * addend2) { Monomial * p; // First set the current polynomial to 0 Init(); // Now add the first addend, one monomial at a time for (p=addend1->list; p!=NULL; p=p->next) if (!AddMonomial(p->degree, p->coeff)) return false; // Now add the second addend, one monomial at a time for (p=addend2->list; p!=NULL; p=p->next) if (!AddMonomial(p->degree, p->coeff)) return false; return true; } /*------------------------------------------------------------*/ /* Polynomial::EqualToDiff * Sets the current polynomial equal to the difference of the * two arguments * returns true if successful, false if out of memory */ bool Polynomial::EqualToDiff(const Polynomial * minuend, const Polynomial * subtrahend) { Monomial * p; // First set the current polynomial to 0 Init(); // Now add the minuend, one monomial at a time for (p=minuend->list; p!=NULL; p=p->next) if (!AddMonomial(p->degree, p->coeff)) return false; // Now subtract the subtrahend, one monomial at a time for (p=subtrahend->list; p!=NULL; p=p->next) if (!AddMonomial(p->degree, -p->coeff)) return false; return true; } /*------------------------------------------------------------*/ /* Polynomial::EqualToDiff * Sets the current polynomial equal to the difference of the * two arguments * returns true if successful, false if out of memory */ bool Polynomial::EqualToProd(const Polynomial * mult1, const Polynomial * mult2) { Monomial * p1, *p2; // First set the current polynomial to 0 Init(); // Now add all the product monomials, one a time for (p1=mult1->list; p1!=NULL; p1=p1->next) for (p2=mult2->list; p2!=NULL; p2=p2->next) if (!AddMonomial(p1->degree+p2->degree, p1->coeff*p2->coeff)) return false; return true; } #include using namespace std; /*------------------------------------------------------------*/ /* Polynomial::Print * Pretty prints the current polynomial */ void Polynomial::Print() { Monomial * n; // The zero polynomial is handled separately if (IsZero()) { cout<<"0"; } else { for (n=list; n!=NULL; n=n->next) { if (n!=list) { // If this is not the first monomial, we need to put the // + or - that goes between monomials // For the first one, however, the + or - must be handled // differently, because no + is output if its positive, // and the - goes without spaces if it's negative if (n->coeff>0) cout << " + "; else cout << " - "; } // Now we need to output the coefficient // This happens only if it's not equal to 1 or -1, in which case // the + or the - minus we output above already takes care of it // However, there are two special cases: the -1 at the beginning // of the polynomial must still be output as -, and the last // coefficient is always output, even if it's 1 if((n->coeff != 1.0 && (n->coeff != -1.0 || n==list)) || n->degree == 0) { // If this is not the first coefficent, then + or - is already // taken care of above, so simply output the absolute value if (n!=list) cout << ((n->coeff>0) ? n->coeff : -n->coeff); // If it is the first coefficient, then we output it the way it is // unless it is -1, in which case we just output - without spaces. else { if (n->coeff==-1.0) cout << '-'; else cout << n->coeff; } } // Now output x unless the degree is 0 if (n->degree>0) cout<<"x"; // Now output the degree unless it is 0 or 1 if (n->degree>1) cout<<"^"<degree; } } cout<<"\n"; } /* ----------- END OF FILE: polynomial.cpp ---------- */