I am currently at Kutztown University enrolled in Computer Science II. I am struggling to finish writing the actual cpp for the program, the implementation and header files are finished.

Here are the instructions of the program:

Recall that a polynomial is a sum of terms in the form, f(x) = a0x0 + a1x1 + a2x2 + … + anxn. You are to write a program that will manipulate polynomials. The application should instantiate polynomials as linked lists of terms. The application should allow the user to do the following

1. Build a polynomial by entering it term by term. The function must first check to see if there is a term with that exponent in the polynomial (find). If there is not, the function will insert the term. If there is, the function will first remove the existing term and then insert the new term.

2. Add the two polynomials to produce a new polynomial. The function will be passed two polynomials and return their sum.

3. Print out the three polynomials in the form
term1 + term2 + … + termN
+ term1 + term2 + … + termN
term1 + term2 + … + termN

4. Evaluate the polynomial that was the result of 2 given a value from the user

5. Clear the polynomials and start again

The user should be able to repeat the process above as many times as he or she wants.

Now I have finished the implementation and the header files:

//File:     linkedList.h
//Author:   Prof. Day
//Course:   CSC 136
//Date:     Spring 2009
//Purpose:  Declaration of linked list class
#include <iostream>
using namespace std;

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

template <class T>
class linkedList
{
 public:

  //sets the head to null
  linkedList() {head = NULL;}

  //The Big 3
  //Copy constructor does a deep copy
  linkedList(const linkedList &list);
  //Assignment operator does a deep copy
  linkedList& operator=(const linkedList &list);
  //Destructor deletes all the nodes in the list
  ~linkedList();

  //returns true if the list is empty, false otherwise
  bool empty() const;

  //clears out all the nodes in the list and sets head to NULL
  void clear();

  //inserts the value in the list to maintain ascending order
  //insert fails if the value is already in the list
  bool insert(T value);

  //removes the value from the list
  //remove fails if there value is not found in the list
  bool remove(T value);


  //find looks for the value in the list.  If found, it copies
  // the list component into the parameter.  This is in case
  // the component is not a simple type.
  //Return: true if found, falser otherwise
  bool find(T &value);

  //for traversing
  //moves to the beginning of the list
  void start();

  //returns the next value in the list and advances along
  //getNext fails if it is at the end of the list
  bool getNext(T &value);

 private:

  class node
  {
    public:
      node() {next = NULL;}
      node(T value) {data = value; next = NULL;}
      T data;
      node *next;
  };

  //attributes
  node *head;            //points to the beginning of the list
  node *current;         //keeps track of where the traversal is
};

#endif

template class linkedList<int>;
//File:     linkedList.cpp
//Author:   Prof. Day
//Course:   CSC 136
//Date:     Spring 2009
//Purpose:  Declaration of linked list class
#include <iostream>
#include "linkedList.h"
using namespace std;


  //The Big 3
  //Copy constructor does a deep copy
template <class t>
linkedList<t>:: linkedList(const linkedList &list)
{
  node *create;

  for (node *ptr = list.head; ptr != NULL; ptr = ptr->next)

    if (head == NULL)
        {
          head = new node(ptr->data);
          create = head;
        }
      else
        {
          create->next = new node(ptr->data);
          create = create->next;
        }

}

 //Assignment operator does a deep copy
template <class t>
linkedList<t>& linkedList<t>:: operator=(const linkedList &list)
{
  if (head != NULL)
  delete this;

  node *create;

  for (node *ptr = list.head; ptr != NULL; ptr = ptr->next)

    if (head == NULL)
      {
        head = new node(ptr->data);
        create = head;
      }
    else
      {
        create->next = new node(ptr->data);
        create = create->next;
      }



}

  //Destructor deletes all the nodes in the list
template <class t>
linkedList<t>:: ~linkedList()
{
  for (node *ptr = head; ptr != NULL; )
    {
      ptr = ptr->next;
      delete ptr;
    }
  head = NULL;
}

  //returns true if the list is empty, false otherwise
template <class t>
bool linkedList<t>::empty() const
{
  if (head == NULL)
    return true;

  return false;
}

  //clears out all the nodes in the list and sets head to NULL
template <class t>
void linkedList<t>::clear()
{
  current = head;
  while (current != NULL)
    {
      head = current->next;
      delete current;
      current = head;
    }
  head = NULL;
}

  //inserts the value in the list to maintain ascending order
  //insert fails if the value is already in the list
template <class t>
bool linkedList<t>::insert(t value)
{
  node *insertloc = new node(value);

    for (node *ptr = head; ptr != NULL; ptr = ptr->next)
      {
        if (ptr->data == value)
          return false;
        else if ((value > ptr->data) && (value < ptr->next->data))
          {
            insertloc->next = ptr->next;
            ptr->next = insertloc;
            return true;
          }

      }
}

  //removes the value from the list
  //remove fails if there value is not found in the list
template <class t>
bool linkedList<t>::remove(t value)
{
  for (node *ptr = head; ptr !=NULL; ptr = ptr -> next)
    {
      if (ptr->data == value)
        {
          if (ptr == head)
            head = ptr->next;
          else
            current -> next = ptr -> next;
          delete ptr;
          return true;

        }
      current = ptr;
    }
  return false;

}

  //find looks for the value in the list.  If found, it copies
  // the list component into the parameter.  This is in case
  // the component is not a simple type.
  //Return: true if found, falser otherwise
template <class t>
bool linkedList<t>::find(t &value)
{
  for (node *ptr = head; ptr != NULL; ptr = ptr -> next)
    if (ptr -> data == value)
      value = ptr -> data;
      return true;
  return false;

}

  //for traversing
  //moves to the beginning of the list
template <class t>
void linkedList<t>::start()
{
  current = head;
}

  //returns the next value in the list and advances along
  //getNext fails if it is at the end of the list
template <class t>
bool linkedList<t>::getNext(t &value)
{
  if (current ==  NULL)
    return false;

  value = current -> data;
  current = current -> next;
  return true;
}

This is the part I need help with, the actual program.. This is what I have so far:

//File:linkedListApp.cpp

// Insructions to follow while coding:
/*/  if (there is a term with  exponent(t2) in the polynomial (using find)
    remove existing term then insert the term;
  else
    insert the term;

  add two polynomials to produce a new polynomial;
  function will be passed two polynomails and return the sum;

  print out polynomials in the form as on paper;

  evaluate the polynomial that was the result of 2 given a value from the user;

  clear the polynomials and start again; /*/



// Program Starts:

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


int main()
{
  int t1,t2;
  linkedList<int>p1,p2;

  cout<<"Please enter a polynomial term by term: (Ex. 12 3 ) \n";
  cin >> t1 >> t2;;

return 0;
}

I finished most of the program with the assistance of a tutor and seeing as it's Saturday and the program is due by 12:00 Sunday night im in a bind.

Thanks for any help!

-Bill

Ok, I suppose that you are using a list to keep each term of the polynomial, like the first element as the first term (like x), the second element as the second term (like x^2), and so it goes...

Just insert all the "terms", use your find method to find the needed term (it should be good if the find method can return an iterator or an object of that kind to get the element...), and use your getNext() function n times for the nth term...

Here's one approach:

add an attribute called degree to linkedList class. It will be equal to the number of terms in the linked list. All terms will be listed in linkedList, even if coefficient (aka value) is zero.

add a friend function to linkedList class to overload the + operator which will add second list to current list. It might look something like this:

declare a linkedList to act as the answer
determine whether current list has smaller, larger or same degree as the linkedList passed in
set current pointer in both linkedLists to header
while current pointer of smaller linkedList not equal to Null
      add current->value of both linked lists together
      insert sum from step above into answer
      advance both current pointers to next
insert remaining nodes of longer linkedList into answer
return answer

in main()

declare three linkedLists: first, second and answer
declare a bool variable to act as a flag, call it addLinkedListsTogether and assign it the value of true
while(addLinkedListsTogether)
    populate first
    populate second
    answer = first + second;
    display answer
    ask if want to add two more linkedLists
    if no
       change flag

You can use the power of object-oriented approach and create a Polynomial class that is represented by a List object as a attribute. For example, a getDegree() method returns the getSize() method on the list member. If you change the representation of the Polynomial class (the list), the methods like getDegree() will stay, but will be implemented differently.

The suggested operator+() will be on the Polynomial class, of course. There's no interest to do an operator+() with that behavior on the List class.

I'm sure your teacher will find it very elegant!

Still a bit dazed.. Is there anyway you could show me an example in actual code? Ive been trying at it and just keep getting errors..

Thanks

Bill

*Edit* And I don't believe she wants us to add any other functions to the header or implementation, she gave us the skeleton header file and I wrote an implementation from there*

So I have been messing with this, and know that its completely wrong. But the base Idea is down and I believe this is how my program file should look:

//File:
/*/  if (there is a term with  exponent(t2) in the polynomial (using find)
    remove existing term then insert the term;
  else
    insert the term;

  add two polynomials to produce a new polynomial;
  function will be passed two polynomails and return the sum;

  print out polynomials in the form as on paper;

  evaluate the polynomial that was the result of 2 given a value from the user;

  clear the polynomials and start again; /*/




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

void insertTerm();
void addTerms();
void printTerms();
void evaluateTerms();
void clearTerms();

int main()
{
  int t1,t2;
  linkedList<term>p1,p2,answer;
  term t;

  insertTerm();








  return 0;


}

////////////////////////////////////////////////////////////
//Name: insertTerm()
//Purpose: Open file and read prices into array
//Parameters: double prices[priceList], int size
//Return: N/A
////////////////////////////////////////////////////////////

void insertTerm()
{

  cout<<"Please enter a polynomial term: (Ex. 12 3 would equal 12x^3) \n";
  cin >> t1 >> t2;
  cin.ignore(1000, '\n');


    if (p1.find (t2))
      {
        p1.remove(t2);
        p1.insert(term(t2));
      }
    else
      {
        p1.insert(term(t2));
      }

}



////////////////////////////////////////////////////////////
//Name: addTerms()
//Purpose: Open file and read prices into array
//Parameters: double prices[priceList], int size
//Return: N/A
////////////////////////////////////////////////////////////

void addTerms()
{



}



////////////////////////////////////////////////////////////
//Name: printTerms()
//Purpose: Open file and read prices into array
//Parameters: double prices[priceList], int size
//Return: N/A
////////////////////////////////////////////////////////////

void printTerms()
{
  // Need to traverse loop and print each term.
}



////////////////////////////////////////////////////////////
//Name: evaluateTerms()
//Purpose: Open file and read prices into array
//Parameters: double prices[priceList], int size
//Return: N/A
////////////////////////////////////////////////////////////

void evaluateTerm()
{
  double y;
  y = t.evaluate(p1);
}



////////////////////////////////////////////////////////////
//Name: clearTerms()
//Purpose: Open file and read prices into array
//Parameters: double prices[priceList], int size
//Return: N/A
////////////////////////////////////////////////////////////

void clearTerms()
{
  p1.clear();
  p2.clear();
  answer.clear();
}

OK. Here's some untested and never compiled code that might give you some direction. It is not intended to be complete or even error proof. I wanted to focus on the process, rather than produce a finished product.

Rather than calling what I usually call a list a list I called it called it Polynomial. Except for the name change, it is exactly like a list with the exception of the evaluate() function and the Polynomial is made up of Terms, analagous to a list being made up of nodes. Since a Polynomial is specific for Terms I didn't bother to templatize the code. I used structs because I wanted to focus on algorhithms, not make the code as robust as possible. Further, I haven't written important protocols such as an assignment operator or a copy constructor for Polynomial. That I leave to you. I have also purposely left out some of the code for some of the functions that you haven't already demonstrated you know how to write, though it shouldn't be hard to figure out what to do given I've commented every line of code (or in some cases very minor algorithms) that I've removed. I also haven't modularized the code, put in any needed header files, etc.

struct Term
{
  int coeff;
  int exp;
  Term * next;
  void display() {cout << coeff << "x^" << exp;}
};

struct Polynomial
{
  Term * head;
  int numTerms;
  Polynomial() : head(NULL), numTerms(0) {}

   ~Polynomial()
   { 
      Term * t;
      while(head != NULL)
      {
         t = head;
         head = head->next;
         delete t;
      }
   }

   void display()
   {
      Term * t = head;
      while(t != NULL)
      {
        t->display();
        
        //if not the last Term
            //output the string  " + "

        t = t->next;
      }
   }

   void build() //add as many Terms as you want
   {
      bool addAnotherTerm = true;
      char choice;

      while(addAnotherTerm)
      {
         int c, e;           
         cout << "enter coefficient for this term" << endl;
         cin >> c;
         cout << "enter exponent for this term" << end;
         cin >> e;
         insetTerm(c, e);

         cout << "add another term? y/n" << endl;
         cin >> choice;
         if(choice == 'n')
           addAnotherTerm = false;
      }
   }
    
   //insert Terms into Polynomial in ascending order by value of exp     
   void insertTerm(int c, int e)     
   {
      Term * term = new Term;
      term->coeff = c;
      term->exp = e; 
      term->next = NULL;

      Term * t = head;
      Term * prev;  //the Term to the left of t

      if(t == NULL)
      {
        head = term;
        ++numTerms;
      }
      else
      {
        while((t != NULL) && (t->exp < term->exp))
        {
            //assign a Term to prev
            //move t to the next Term
         }

        if(exponents are equal)
        {
            //change t exp to term exp
            //discard term                  
        }
        else
        {
            //insert term to left of t          
            //increment numTerms;
        }
      }           
   }

   void deleteTerm(int e)
   {
     Term * t;
     Term * prev;  //the Term to the left of t
       
     t = head;
     while(t != NULL && t->exp != e)
     {
        //assign a Term to prev
        //advance t to next Term
      }
       
     //assign the Term to the right of t to Term to the left of T    
 
     delete t;
     --numTerms;
   }
    
   double evaluate(double x)
   {
     double result = 0.0;
     Term * current;
     current = head;
     while(current != NULL)
     {
       result += //value of this Term
       //go to next Term
     }
     return result;
   }
   
   void clear()
   {
     Term * t;
      while(head != NULL)
      {
         t = head;
         head = head->next;
         delete t;
      }
      numTerms = 0;
   }

   friend Polynomial operator + (Polynomial & p1, Polynomial & p2)
   {
     int c, e;
     
     //copy p2 into a new polynomial that will change in this function
     Polynomial p3(p2);

     Polynomial result;
     
     //start at beginning of each Polynomial    
     Term * c1 = head;
     Term * c3 = p3.head;

     //for each Term in first Polynomial
     for( ; c1 != NULL;  ++c1)
     {
        //look for Term with same exponent
        for( ; c3 != NULL;  ++c3)
        {
           //if you find one
           if(c1->exp == c3->exp)
           {
              //add the coefficients together
              c = c1->coeff + c3->coeff;
              e = c1.exp;
              //insert a Term with the new coeff and this exp into result
              
              //delete the Term found in p3 from p3   
             
              //break out of the loop early
           }
        }
        //if didn't find Term in p3 with same exp as Term in p1
        {
           //insert Term from p1 into result
        }
     }
     //after all Terms in p1 and Terms common to p1 and p3 have been inserted into result, insert remaining Terms in p3 into result
     for(c3 = p3.head; c3 != NULL; ++c3)
       result.insert(c3->coeff, c3->exp);
          
     return result;
   }
}; 

int main()
{
   double x;
   bool addTwoPolynomials = true;
 
   Polynomial p1;
   Polynomial p2;
   Polynomial answer;
     
   while(addTwoPolynomials)
   {
      p1.build();
      p2.build();

      answer = p1 + p2;

      p1.display();
      p2.display();
      answer.display();

      cout << "enter value of x" << endl;
      cin >> x;
      cout << `answer.evaluate(x) << endl;

      cout << "add two more polynomials:  Y/N" << endl;
      cin << choice;
      if(choice == 'N')
        addTwoPolynomials = false;
      else
      {
        p1.clear();
        p2.clear();
        answer.clear();
      }
   }
   return 0;
}
This article has been dead for over six months. Start a new discussion instead.