Question

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 4x², the coefficient is 4 and the exponent 2

in -6x⁸, 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. Your class will also override toString to return a Term in this general form:

ax^b     where a is the coefficient and b the exponent

with these special cases:

Case	Returns
a = 1	x^b
b = 1	ax
b = 0	a
a = 1, b = 1	x

You may assume that the coefficient will not be zero.

     

The Generic Node Class

This has already been done, declared as an inner class in Polynomial. Do not modify it in any way. Note that it will not compile until the Term class is defined.

The Polynomial Class

A “skeleton” of the Polynomial class you are to use is on the class web site. All you have to do is write the bodies of the methods.

Do not declare any new instance variables or methods and do not modify any of the method declarations.

As defined here, a polynomial is a sequence of terms. E.g.

1.

2.

3.

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)

To receive credit for this assignment, you must use no data structures other than your own programmer-defined (you being the programmer) singly-linked list of generic Nodes

Note that the Polynomial class has:

A constructor that creates a null Polynomial (a Polynomial with 0 terms)

A copy constructor that creates a new Polynomial as an exact duplicate of an existing one (aka: a “deep” copy)

A method with signature

     public void addTerm(int coefficient, int exponent)

which creates a Term and places it in its proper position in the linked list

The terms on the list are stored in ascending order by exponent (see III., above) so there is never a need to “sort” the list. Terms with the same exponent may be stored in any order but will appear after all terms with lesser exponents and before all terms with greater exponents

A method with signature

     public Polynomial polyAdd(Polynomial p)

which adds this Polynomial to p and returns the sum

A method with signature

     public Polynomial polyMultiply(Polynomial p)

which multiplies this Polynomial by p and returns the product

An overridden toString method that returns a String representation of a polynomial as a sum of terms. For example polynomial 1 above would have this String representation:

          3x^2 + 48x^4 + x^6

    

A private method with signature

     private void collectTerms()

which “collects” like terms of this Polynomial. E.g.

     Before:   x^2 + 3x^2 + 2x^2 + 3x^3 + 5x^4 + 2x^4

     After:    6x^2 + 3x^3 + 7x^4

Polynomials should always be printed with like terms collected.

Helpful Hints! Divide and Conquer!

Begin by coding the Term class and Polynomial methods toString and addTerm. For now, haveaddTermsimply add each new Term at the head of the list or, if you prefer, at the end. This will enable you to run the program and verify that your Term class is correct and that new Terms are indeed being created and added to the list.

Code the polyAdd and polyMultiply methods. These are fairly straightforward and once completed, along with the temporary version of addTerm, you will have a majority of the credit in the bank. J

Modify the addTerm method so that each new Term is inserted in it’s proper place in the list. An algorithm will be discussed in class. Note that none of the other methods will need to be modified in any way. More credit in the bank.

Code the collectTerms method. An algorithm will be discussed in class.

Code the copy constructor.

Don’t forget: “With linked lists, crayons are more important than keyboards.”

-------------------------------------------------------------------------------------------

Skeleton for Polynomial.java:

/**
 * A class to represent a polynomial as a sum of terms where each term has
 * the same variable, an int coefficient, and a nonnegative int exponent.
 * Polynomials may be added and multiplied 
 */
public class Polynomial
{
   private Node head ;              // points to the first Node of a Polynomial

   /**
    * Default constructor creates a Polynomial with no terms
    */
   public Polynomial()  // DO NOT MODIFY THIS CONSTRUCTOR
   {
      head = null ;
   }
   
   /**
    * Creates a "deep copy" of a given Polynomial. I.e. a new Polynomial with
    * identical terms
    * @param p Polynomial to be copied
    */
   public Polynomial(Polynomial p)  // a "copy" constructor
   {
      // TO DO: write body of this method
   }
   
   /**
    * Creates a new Term and Node containing it and inserts it in its proper
    * place in this Polynomial (i.e. in ascending order by exponent) 
    * @param coeff the coefficient of the new Term
    * @param expo the exponent of the new Term
    */
   public void addTerm(int coeff, int expo)
   {
      // TO DO: write body of this method 
   }      
  
   /**
    * Returns a polynomial as a String in this form: x + 3x^2 + 7x^3 + x^5
    * @return the polynomial as a String
    */
   public String toString()
   {
       // TO DO: write body of this method
       // temporary return so class skeleton will compile and run
       return "Hi Mom!" ;
   }
   
   // collect terms of a Polynomial object. I.e. replace all terms having the 
   // same exponent with a single term which is their sum
   private void collectTerms()
   {
       // TO DO: write body of this method
   }
   
   /**
    * Multiply this Polynomial by another Polynomial
    * @param p the other Polynomial
    * @return the Polynomial product
    */
   public Polynomial polyMultiply(Polynomial p)
   {
       // TO DO: write body of this method
       // temporary return so class skeleton will compile and run
       return null ;
   }
   
   /**
    * Add this Polynomial and another Polynomial
    * @param p the other Polynomial
    * @return the Polynomial sum
    */
   public Polynomial polyAdd(Polynomial p)
   {      
       // TO DO: write body of this method
       // temporary return so class skeleton will compile and run
       return null ;
   }
   
   // Node class definition - DO NOT MODIFY!
   class Node <E extends Term>
   {
      private E info ;     // each node stores an object of the 
                           // type-parameter class...
      private Node next ;  // ...and a pointer to another node

      // Node Constructor 
      // parameter x is an object of the type-parameter class
      Node(E x)         
      {
         info = x;      // set info portion to parameter passed
         next = null;   // not necessary, null is default value
      }
   } // end of Node class definition ============================
} // end of Polynomial class definition =========================

-------------------------------------------------------

PolynomialTester.java

public class PolynomialTester
{
   public static void main(String[] args)
   {
      Polynomial p1 = new Polynomial();
      Polynomial p2 = new Polynomial();
      Polynomial p0 = new Polynomial();
      
      Polynomial nullTest = p1.polyAdd(p2);
      System.out.println("\np1 = " + p1 + ", np2 = " + p2 + "\tp1 + p2 = " + 
                          nullTest);
      nullTest = p1.polyMultiply(p2);
      System.out.println("\np1 = " + p1 + ", np2 = " + p2 + "\tp1 * p2 is " + 
                          nullTest);
      
      p1.addTerm(5, 2);
      p1.addTerm(4, 5);
      p1.addTerm(3, 3);
      p1.addTerm(1, 2);
      p1.addTerm(5, 6);
      p2.addTerm(3, 8);
      p2.addTerm(2, 5);
      p2.addTerm(1, 2);
      p0.addTerm(1, 2);
      p0.addTerm(5, 0);
      p0.addTerm(4, 1);
      
      System.out.println("\np0 = " + p0);
      
      Polynomial p3 = p1.polyAdd(p2);
      System.out.println("\np1 = " + p1 + "\np2 = " + p2 + "\np1+p2 = " + p3);
      
      Polynomial p4 = p1.polyMultiply(p2);
      System.out.println("\np1 = " + p1 + "\np2 = " + p2 + "\np1*p2 = " + p4);
      
      Polynomial p5 = p2.polyMultiply(p2);
      System.out.println("\np2 = " + p2 + "\np2*p2 = " + p5);
      
      Polynomial p6 = p0.polyMultiply(p2);
      System.out.println("\np0 = " + p0 + "\n" + "p2 = " + p2 + "\np0*p2 = " 
                         + p6);
      
      Polynomial p7 = p0.polyAdd(p2);
      System.out.println("\np0 = " + p0 + "\n" + "p2 = " + p2 + "\np0+p2 = " 
                         + p7);
      
      p1 = p1.polyAdd(p2);
      System.out.println("\nAfter p1 = p1+p2  p1 = " + p1);
      
      p2 = p2.polyMultiply(p2);
      System.out.println("\nAfter p2 = p2*p2  p2 = " + p2);
      
      // Testing copy constructor
      Polynomial pCopy = new Polynomial(p1) ;
      System.out.println("\nAfter copy p1 =    " + p1); 
      System.out.println("After copy pCopy = " + pCopy);
      p1.addTerm(10, 4);
      System.out.println("\nAfter adding 10x^4 to p1, p1 = " + p1); 
      System.out.println("But pCopy is still             " + pCopy);
      
      
   }
}

------------------------------------

Please be thorough with comments, I want to understand whats going on

Answer 1

PolynomialTester.java

public class PolynomialTester
{
   public static void main(String[] args)
   {
      Polynomial p1 = new Polynomial();
      Polynomial p2 = new Polynomial();
      Polynomial p0 = new Polynomial();
      p1.addTerm(5, 2);
      p1.addTerm(4, 5);
      p1.addTerm(3, 3);
      p1.addTerm(1, 2);
      p1.addTerm(5, 6);
      p2.addTerm(3, 8);
      p2.addTerm(2, 5);
      p2.addTerm(1, 2);
    
      Polynomial p3 = p1.polyAdd(p2);
      System.out.println("p1 is " + p1 + "\np2 is " + p2 + "\np1+p2 is " + p3);
    
      Polynomial p4 = p1.polyMultiply(p2);
      System.out.println("p1 is " + p1 + "\np2 is " + p2 + "\np1*p2 is " + p4);
    
      Polynomial p5 = p2.polyMultiply(p2);
      System.out.println("p2 is " + p2 + "\np2*p2 is " + p5);
    
      Polynomial p6 = p0.polyMultiply(p2);
      System.out.println("p0 is " + p0 + "\n" + "p2 is " + p2 + "\np0*p2 is "
                         + p6);
    
      Polynomial p7 = p0.polyAdd(p2);
      System.out.println("p0 is " + p0 + "\n" + "p2 is " + p2 + "\np0+p2 is "
                         + p7);
    
      p1 = p1.polyAdd(p2);
      System.out.println("After p1 = p1+p2 p1 is " + p1);
    
      p2 = p2.polyMultiply(p2);
      System.out.println("After p2 = p2*p2 p2 is " + p2);
      System.out.println("p1 is " + p1 );
   }
}

Polynomial.java

public class Polynomial
{
    private Node first ; //First node on the list
  
    /**
     * Constructor for an empty polynomial.
     */
    public Polynomial ()
    {
        first = null ; //Empty list
    }
  
    /**
     * Constructor that creates a new polynomial from an existing one.
     * @param poly existing polynomial to be cloned
     */
    public Polynomial ( Polynomial poly )
    {
        //Clone the first term for new polynomial
        first = new Node( poly.first.info ) ;
        Node temp1 = first ; //new polynomials first node
        Node temp2 = poly.first.next ; //start at polys second node
        //traverse poly
        while ( temp2 != null )
        {
            temp1.next = new Node( temp2.info ) ; //Clone current term
            //Move to next node
            temp1 = temp1.next ;
            temp2 = temp2.next ;  
        }
    }
  
    /**
     * Utility method to find a position for a term in the list. Is based on
     * equal exponent.
     * @param term the term to find a position for
     * @return pointer to the node where you can place this term after
     */
    private Node findPos( Term term )
    {
        if ( first == null )       //if list empty
        {
            return null ;        //Term fits at the start of the list
        }
        else                    // else, search for a pos
        {
            Node temp = first ;           //first node of the list
            Term thatTerm = temp.info ; //Term of the first node
            //Check if term has a lower exponent than first one from the list
            if ( term.hasLowerExp( thatTerm ) )
            {
                return null ; //Term fits at the start of the list
            }
            //Traverse the list to find a position for the term
            while ( temp.next != null ) //while there is a node
            {
                thatTerm = temp.next.info ; //Term of the next node
                //Check if term has a lower exponent than the next term
                if( term.hasLowerExp( thatTerm ) )
                {
                    return temp ; //Term fits after this node
                }
                temp = temp.next ;   // move to next node
            }
            return temp ;       // Pointer to last node
        }
      
    }
  
    /**
     * Creates a term, finds a position for it on the list and places it.
     * @param coefficient coefficient for the term
     * @param exponent exponent for the term
     */
    public void addTerm( int coefficient, int exponent )
    {
        Term newTerm = new Term( coefficient, exponent ) ;//Creates new term
        Node newNode = new Node( newTerm ) ; //new Node with term
        //check if term fits as the first node (list could be empty)
        if ( findPos( newTerm ) == null )
        {
            //Node is either placed before first term or as the first.
            //New nodes 'next' points to first (which could be empty)
            newNode.next = first ;
            first = newNode ; //new Node is now the first
        }
        else //placed somewhere after first term
        {
            //temp node that points to the node after where the term can fit
            Node temp = findPos( newTerm ).next ;
            findPos( newTerm ).next = newNode ; //insert new node
            newNode.next = temp ; //new node now points to the next node
        }
    }
  
    /**
     * Creates a new polynomial that is the addition of this polynomial with
     * a given other, and returns it.
     * @param p polynomial to be added
     * @return new polynomial that is the sum of two polynomials
     */
    public Polynomial polyAdd( Polynomial p )
    {
        //resulting polynomial starts as the adding polynomial
        Polynomial resultPoly = new Polynomial( p ) ;
        Node temp = first ; //start fromm the first polynomial
        //traverse the list
        while ( temp != null )
        {
            //add the terms from 'this' polynomial to the resulting polynomial
            resultPoly.addTerm( temp.info.getCoef(), temp.info.getExp() ) ;
            temp = temp.next ; //move to the next node
        }
        return resultPoly ; //resulting polynomial
    }
  
    /**
     * Creates a new polynomial that is the multiplication of this polynomial
     * with a given other, and returns it.
     * @param p polynomial to be multiplied
     * @return new polynomial that is the multiplication of two polynomials
     */
    public Polynomial polyMultiply( Polynomial p )
    {
        //resulting polynomial starts as the multiplying polynomial
        Polynomial resultPoly = new Polynomial() ;
        Node temp1 = first ; //start from first node of 'this' list
        Node temp2 = p.first ; //start from first node of 'multiplying' list
        /*
            Multiply each term from 'this' list by each term of the
            'multiplying' list
        */
        while ( temp1 != null ) //traverse 'this' list
        {
            while ( temp2 != null ) //traverse 'multiplying' list
            {
                //multiply the coeficients
                int newCoef = temp2.info.getCoef() * temp1.info.getCoef() ;
                //add the exponents
                int newExp = temp2.info.getExp() + temp1.info.getExp() ;
                //add the new term to the resulting
                resultPoly.addTerm( newCoef, newExp ) ;
                temp2 = temp2.next ; //move to the next node
            }
            temp2 = p.first ; //reset the 'multiplying' list
            temp1 = temp1.next ; //move to the next node of 'this' list
        }
        return resultPoly ; //resulting polynomial
    }
  
    /**
     * Utility method that collects terms for proper formating.
     */
    private void collectTerms()
    {
        Node temp = first ; //start at first node
        while( temp.next != null ) //Traverse the list
        {
            Term thisTerm = temp.info ; //'this' term
            Term thatTerm = temp.next.info ; //the next term
            //compare and add the coefficients while the exponents of the next
            //term is the same as 'this' terms exponent
            while ( thisTerm.getExp() == thatTerm.getExp() )
            {
                int newCoef = thisTerm.getCoef() + thatTerm.getCoef() ;
                Term newTerm = new Term( newCoef, thisTerm.getExp() ) ;
                temp.info = newTerm ; //'this' get new resulting term
                temp.next = temp.next.next ; //point to the term after next
                thisTerm = temp.info ; //new term
                thatTerm = temp.next.info ; //new next term
            }
            //check if there is a next term
            if ( temp.next == null )
            {
                break ; //exit the loop
            }  
            temp = temp.next ; //move to next term
        }
    }
  
    /**
     * Overridden toString method that format the list into a polynomial.
     * @return the formated polynomial
     */
    public String toString()
    {
        if ( first == null ) //Check if list is empty
        {
            return "0" ; //the polynomial is '0'
        }
        collectTerms() ; //Collect the terms for formating
        String s = "" ; //the polynomial in string format
        Node temp = first; //start from the first node of the list
        while( temp != null ) //traverse the list
        {
            s = s + temp.info.toString() ; //add term to the string
            temp = temp.next ; //move to next node
        }
        return s ; //Formated polynomial
    }
  
    /**
     * Generic inner class that implements a Node in a dynamic data structure.
     * @param <E> object of the Term type
     */
    class Node< E extends Term >
    {                  
        E info ;   // each node stores an object
        Node next ;   // pointer to the next node
      
        /**
         * Node constructor
         * @param x parameter of class E type of object
         */
        Node ( E x )       // constructor takes one param of class E
        {          
            info = x ;   // obejet stored
            next = null ;   //node points to nothing
        }
    }
  
}

Term.java

public class Term
{
    private int coef ; //Coefficient of the term
    private int exp ; //Exponent of the term
  
    /**
     * Constructor method that sets the values for the coefficient and the
     * exponent of the term.
     * @param coef coefficient of the term
     * @param exp The exponent of the term
     */
    public Term( int coef, int exp )
    {
        //Set the values for the coefficient and the exponent of the term
        this.coef = coef ;
        this.exp = exp ;
    }
  
    /**
     * Accessor method for the coefficient of the term.
     * @return The coefficient of the term
     */
    public int getCoef()
    {
        return coef ; //The coefficient of the term
    }
  
    /**
     * Accessor method for the exponent of the term.
     * @return The exponent of the term
     */
    public int getExp()
    {
        return exp ; //The exponent of the term
    }
  
    /**
     * Overridden toString method the returns the term in ax^b format.
     * @return The formated term
     */
    public String toString()
    {
        //Creates a string in cx^e format
        String s = " " + formatCoef() + formatExp() ;
        return s ;
    }
  
    /**
     * Utility method that formats the coefficient.
     * @return the formated coefficient
     */
    private String formatCoef()
    {
        String coef = String.valueOf( this.coef ) ; //Formated coefficient
        //Modify the formated coefficient if it is zero or one or minus one
        if ( this.coef == 0 )
        {
          
            coef = "" ; //there is no coeficient
            //if the coefficient is zero than so is the rest of the term
            exp = 0 ;
        }
        else if ( this.coef == 1 )
        {
            coef = "" ; //'1x' is the same as 'x'
        }
        else if ( this.coef == -1 )
        {
            coef = "-" ; //'1x' is the same as '-x'
        }
        return coef ;
    }
  
    /**
     * Utility method that formats the exponent.
     * @return the formated exponent
     */
    private String formatExp()
    {
        String exp = "x^" + String.valueOf( this.exp ) ; //Formated exponent
        //Modify the formated exponent if it is zero or one
        if ( this.exp == 0 )
        {
            exp = "" ; //x^0 is 1 so there is no 'x'
        }
        else if ( this.exp == 1 )
        {
            exp = "x" ; //x^1 is x
        }
        return exp ;
    }
  
    /**
     * Compares this term to another to see if it has a or equal exponent.
     * @param thatTerm Term to compare to
     * @return true it has a lower exponent
     */
    public boolean hasLowerExp ( Term thatTerm )
    {
        //Check if this term has a lower or equal exponent
        if ( exp <= thatTerm.getExp() )
        {
            return true ;
        }
        else
        {
            return false ;
        }
    }
}

a Javadoc Declaration Console 3 <terminated> PolynomialTester [Java Application] CProgram FilesJava\jre7 binjavaw.exe (Apr 6, 2017, 1:45:50 PNM pl is 6x 2 3xA3 4xA5 5x6 p2 is x^2 2x15 3xng p1+p2 is 7x 2 3xA3 6xA5 5xA6 3x 8 pl is 6x 2 3xA3 4xA5 5xA6 p2 is x^2 2x15 3x18 pl*p2 is 6xA4 3x5 16xA7 11xA8 26x 10 19xA11 12x 13 15x 14 p2 is x2 2x5 3x 8 p2*p2 is xA4 4x7 10x 10 12x 13 9x 16 pe is e p2 is x^2 2x15 3xng pe p2 is 0 pe is 0 p2 is x^2 2x15 3x18 2 After pl = p1+p2 p1 IS 7x®2 3xa3 6x15 5x®6 3xng Aer p2 p2*p2 p2 is xA4 4x 7 10x 10 12x 13 9x 16 pl is 7x2 3xA3 6xA5 5x6 3x*8 2 2