Question

Implementing Polynomials using Singly Linked List in C++ The Term Class Create a class to represent a term in an algebraic expression. As defined here, a term consists of an integer coefficient and a nonnegative integer exponent. E.g. • in the term 4X2, the coefficient is 4 and the exponent 2 • in -6X8, the coefficient is -6 and the exponent 8 Your class will have a constructor that creates a Term object with a coefficient and exponent passed as parameters, and accessor methods that return the coefficient and the exponent II. The Polynomial Class Now create a class to represent a polynomial. As defined here, a polynomial is a sequence of terms. E.g. 1. 3X2 + 4X4 + X6 2. 2 + 5X2 + 6X3 + 2X7 3. 4X10 The terms of polynomial 1 are (3,2), (4,4) and (1,6). The terms of polynomial 2 are (2,0), (5,2), (6,3) and (2,7). Polynomial 3 has only one term (4,10) F To receive credit for this assignment, your class must use a generic “List of Term” to store the terms of a Polynomial object Your class will have a constructor that creates an empty list and additional methods to do each of the following: 1. insert a new term in its proper place in a polynomial (see “Additional Specifications,” below) 2. return all the terms of a polynomial as a single line string, as shown here: 3x^2 + 4x^4 + x^6 3. delete a term from a polynomial (see “Additional Specifications,” below) 4. Compute and return the derivative of all the polynomial 5. reverse the order of the terms in a polynomial (see “Additional Specifications,” below) III. The Test Class The main method of your test class will create a Polynomial object and then read and process a series of operations The operations are: 1. INSERT X Y Insert a new term with coefficient X and exponent Y into its proper place in the polynomial (insert method : adds terms to the list in descending order of power) 2. DELETE X Y Remove the term with coefficient X and exponent Y from the polynomial 3. REVERSE Reverse the order of the terms of the polynomial 4. 1st DEV to find the first derivatives of the polynomial 2nd DEV to find the second derivatives of the polynomial Each operation is to be carried out by calling a method of the Polynomial class Each operation read must be “echo printed” to the screen After each operation, print the updated polynomial by calling the toString() method For the Derivatives operation, print the string returned.

Answer 1

Well commented C++ program:

#include<iostream>
using namespace std;

//Term class
template<class T>
class Term{

    private:
    int coeff;
    int exp;

    public:
    Term<T> * next;


    public:

    //constructor
    Term(T val, T pow){
        coeff = val;
        exp  = pow;
        next = NULL;
    }

    //method returns coefficlent
    T cf(){
        return coeff;
    }

    //method returns exponent
    T ex(){
        return exp;
    }

};



//Polynomial class
template<class T>
class Polynomial{

    Term<T> *head;

    public:

    //constructor
    Polynomial(){
        head = NULL;
    }


    //insert term in polynomial
    void insert(int x, int y){

        Term<T> * new_term = new Term<T>(x, y);
        
        //finding the proper place for insertion of the term

        //if the list is empty
        if(head == NULL){
            head = new_term;
        }
        else{
            Term<T> *temp = head, *prev = NULL;
            while(temp && temp->ex() < y){
                prev = temp;
                temp = temp->next;
            }

            //if the new_term has the lowest exponent
            if(temp == head){

                //assign head to new_term;
                new_term->next = head;
                head = new_term;
            }
            else{
                prev->next = new_term;
                new_term->next = temp;
            }
        }
    }



    //return polynomial as string
    string toString(){
        
        //if the list is empty
        if(head == NULL){
            return "List is empty!";
        }
        string pol = "";
        
        Term<T> *temp = head;

        //traverse the list
        while(temp->next){
            pol += to_string(temp->cf()) + "x^" + to_string(temp->ex()) + " + ";
            temp = temp->next;
        }

        pol += to_string(temp->cf()) + "x^" + to_string(temp->ex());
        return pol;
    }


    //method to delete a term from polynomial
    void Delete(int x, int y){

        Term<T> *temp =  head, *prev = NULL;

        //find the term to delete
        while(temp){
            
            if(temp->cf() == x && temp->ex() == y)
                break;
            prev = temp;
            temp = temp->next;
        }

        //if term is not found
        if(temp == NULL){
            cout<<"Not found the term to be deleted!"<<endl;
        }
        //if head is the term to be deleted
        if(temp == head){
            head = head->next;
            delete(temp);
        }
        else{
            prev->next = temp->next;
            delete(temp);
        }
    }


    //method to reverse the order of the terms in polynomial
    void reverse(){
        Term<T> *curr = head, *prev = NULL, *next = NULL; 

        //reverse the linked list while traversing
        while (curr != NULL) { 
            next = curr->next; 
            curr->next = prev; 
            prev = curr; 
            curr = next; 
        } 

        //reassigning the head
        head = prev;  
    }


    //method to find first derivative of polynomial
    string firstDev(){
        string first_dev = " ";

        //if the list is empty
        if(head == NULL){
            return "List is empty!";
        }


        Term<T> *temp = head;

        //traverse the list
        while(temp->next){

            if(temp->ex() != 0){
                first_dev += to_string((temp->ex() * temp->cf())) + "x^" + to_string((temp->ex() - 1)) + " + ";
            }
            else{
                first_dev += "0 +";
            }
            temp = temp->next;
        }

        if(temp->ex() != 0){
            first_dev += to_string((temp->ex() * temp->cf())) + "x^" + to_string((temp->ex() - 1));
        }
        else{
            first_dev += "0";
        }

        return first_dev;

    }


    //method to find second derivative of polynomial
    string secondDev(){
        string sec_dev = " ";

        //if the list is empty
        if(head == NULL){
            return "List is empty!";
        }


        Term<T> *temp = head;

        //traverse the list
        while(temp->next){

            if(temp->ex() != 0 && temp->ex() != 1){
                sec_dev += to_string((temp->ex()*(temp->ex() - 1) * temp->cf())) + "x^" + to_string((temp->ex() - 2)) + " + ";
            }
            else{
                sec_dev += "0 +";
            }
            temp = temp->next;
        }

        if(temp->ex() != 0 && temp->ex() != 1){
            sec_dev += to_string((temp->ex() *(temp->ex() - 1)* temp->cf())) + "x^" + to_string((temp->ex() - 2));
        }
        else{
            sec_dev += "0";
        }

        return sec_dev;

    }

};


int main(){

    Polynomial<int> *p = new Polynomial<int>();
    p->insert(10, 2);
    p->insert(-4, 1);
    p->insert(1, -2);
    p->insert(100, 5);
    
    cout<<p->toString()<<endl;

    p->Delete(10, 2);
    cout<<p->toString()<<endl;

    cout<<p->firstDev()<<endl;
    
    cout<<p->secondDev()<<endl;
    
    return 0;
}

Operation performed:

insert(10, 2);

insert(-4, 1);

insert(1, -2);

insert(100, 5);

toString();

Delete(10, 2);

toString();

firstDev();

secondDev();

Output: