Polynomial Project Part A

NOTE: if there is any ambiguity in the following specification it is YOUR responsibility to ask me in order to clarify.  Be sure and read the following very carefully.

In this project we develop a polynomial class.  This will be an example of a class that uses dynamic memory in the form of a linked list to store the terms of a polynomial.  You may recall that a polynomial is of the form 2x^4+7x^3+12x -7.  If we let coef represent the coefficient and power represent the power then each term looks like coef*x^power were I am using ^ for exponentiation.    To simplify things we can use a vector<int> to represent small polynomials for initialization purposes.  For example the vector 1,2,-4,0,7 could be used to represent the polynomial x^4+2x^3-4x^2+7.  Note this is just the usual place value notation.  Using a linked list to store the poly allows us to save memory if we do not store the 0 coefficient terms.  Hence polynomials such as 23x^100-8 can be stored in a list having only two terms in addition to the header and trailer.  Our linked list will have both a header node and a trailer node in order to simplify insertions.  It will also store the polynomial in decreasing powers of the polynomial.   Here is the poly.h file to define our data, constructors and necessary methods for the class.  Use this as is.  Do not modify or add new methods.

#pragma once
using namespace std;
#include <cmath>
#include <vector>
#include <string>
#include <iostream>
class Poly
 // terms are stored from small power to large power. 
// There are no coef of 0 or repeated powers in the list
 struct Term{
    int coef;// first is the coefficient and second is the power
    int power;
    Term * next;
    Term(int c, int p) :coef(c), power(p),next(nullptr) {};
   // or you may use Term(int c,int p, Term* n):coef(c),power(p),next(n){};
 Term * header;// Points to the first node in the list (ie header)
 Term * trailer;// Points to the last node in the list (ie trailer) public:
 Poly();// default. Create just a header and trailer that are linked together 
 ~Poly();// You must implement this constructor since we have dynamic memory 
 // The vector [1,2,6,-2] represents x^3+2x^2+6x-2. 
 Poly(const vector<int> &);//parameterized constructor using vector<int>
 Poly(const Poly & p);// normal deep copy constructor 
 friend std::ostream& operator << (std::ostream& os, const Poly & p) {
 // write your output code here to print the poly. Print in the form 
 // 3x^4+2x^2-1x^1+5. Don't print 0 coefficient terms. Is ok to print 
 // terms like 1x instead of just x. If you want to print using
 // an algebra acceptable form that is fine but it will take a lot more coding.
  // You may use the following method to add two polys. What is the
 // the complexity of the add when it is done this way? Think!
 void AddTerm(int coef, int power);// add new term to object poly (in the right location!)
 int Eval(int x);// evaluates the poly and returns the result. Use horners rule

I would start by implementing the vector<int> constructor.  Do not call AddTerm() to implement these constructors.  This can be done by just going down the vector, index by index adding a new term on the end of the list.  You can then add temporary code to the output friend operator to print out the linked list in some simple testing format.  This of course can be changed when everything else is running properly.

Now add the remaining methods AddTerm() and Eval() testing carefully.  In order to add two polynomials it is OK to add the terms of the second to the first using AddTerm(). This is inefficient but later we will implement operator+ and do it more efficiently.

Your main program is requested to read commands that process polynomials. Use a switch(cmd) statement to select the command section to process. Each polynomial will be represented as an integer N followed by a list of N coefficients as discussed at the top of the project. The first coefficient should be > zero.  There are three types of data.  Type 1 begins with a + that is followed by two polynomials.   In this case you add the polynomials and print the result.  Clarification: In order to do this read the first values into a vector v and create a Poly by Poly p(v).  Now read in the remaining vector and add the terms of this vector to p using AddTerm(). You do not need to actually create the second polynomial. The second (type 2) begins with a – that is followed by two polynomials which you subtract and then print the result.  The third type (type 3) begins with an E followed by a polynomial and then a value to evaluate the polynomial at.  Use Horner’s Rule to perform the evaluation. Here is a data set you can test with.  This is the data set you turn in the output for.  You of course need to test many more examples looking for a case that causes your program a problem.  I noticed in the last project that many of you did not test your project seriously.  Some of your outputs were not fully reduced and were NOT noticed.  (BAD!) I will run a different data set thru you code to test it thoroughly. Remember to read in using stdin and write out using stdout.

+ 5 2 3 4 1 7   5 3 1 2 2 5
+ 10 2 6 5 7 -3 1 2 2 3 9   7 -4 3 5 12 11 21 5
- 4 12 0 0 0   4 1 2 7 4
+ 4 3 0 0 5    4 3 9 0 0
E 4 3 2 1 12 0
E 5 2 3 0 1 7 -1
E 10 5 0 0 0 0 0 0 0 0 0 2

The output for each pair of polynomials should have the following format. Note that my polynomials are printed in acceptable algebraic form. It is ok for  you to have powers of 1 and coef’s of 1 but NO coef of 0.

Sum is F(x)=5x^4+4x^3+6x^2+3x+12
Sum is F(x)=2x^9+6x^8+5x^7+3x^6+6x^4+14x^3+13x^2+24x+14
Difference is F(x)=11x^3-2x^2-7x-4
Sum is F(x)=6x^3+9x^2+5
F(x)=3x^3+2x^2+x+12 evaluated at 0 is 12
F(x)=2x^4+3x^3+x+7 evaluated at -1 is 5
F(x)=5x^9 evaluated at 2 is 2560

TO TURN IN: Turn in a jump drive containing , your entire well documented project, executable stored in the root dir (renamed to procpoly.exe, and test data.  Several of you on the last project incorrectly had fract.exe.exe as your executable.  Also include a printout of the source and print out of the output file for the above data. Put into an envelope with name and project on the outside.  Be sure the only thing on your jumpdrive is the project,the executable as well as your test dataJust three things.  Test the executable on the data.

NOTE: the above project is just a partial one.  We really should create two polynomials and add them with an overloaded operator.  We will do this later in an efficient way.

Comments are closed.