Assignment #5: Interfaces, Recursion, Linked Lists

In this assignment, you will redo assignment #1 and change the implementation from an array to a sorted linked list. Since you will now have two different implementations of Polynomial, you should refactor as follows:
  1. Make Polynomial an interface.
  2. Rename your old Polynomial class ArrayPolynomial.
  3. Implement your new class as ListPolynomial.
You do not have to submit the ArrayPolynomial class but it will be nice to have it so you can do testing. The following test program illustrates the usage of the new class.
import cop3337.Polynomial;
import cop3337.ListPolynomial;

class Assign5
{  
    public static void main( String [ ] args )
    {
        Polynomial [ ] arr = { new ListPolynomial( "3" ),
                               new ListPolynomial( "x+5" ),
                               new ListPolynomial( "x^2+2x+3" ),
                               new ListPolynomial( "x^2+x^2+x^2" ),
                               new ListPolynomial( "x+2" ),
                               new ListPolynomial( "x^3-2x^2+5x^1+1" )
                             };
        
        Polynomial sum = new ListPolynomial( );
        Polynomial prod = new ListPolynomial( "1" );
        
        for( Polynomial p : arr )
        {
            sum = sum.add( p );
            prod = prod.multiply( p );
            System.out.println( "This: " + p + " total sum is " + sum + " product is " + prod  );
        }
        
        Polynomial p1 = new ListPolynomial( "x+5" );
        Polynomial p2 = new ListPolynomial( "x-5" );
        Polynomial p3 = new ListPolynomial( "x^2-25" );
        Polynomial p4 = p2.multiply( p1 );
        Polynomial p5 = p4.subtract( p3 );
        Polynomial p6 = p4.divide( p2 );   // Should be p1!
        System.out.println( "p1=" + p1 );
        System.out.println( "p2=" + p2 );
        System.out.println( "p3=" + p3 );
        System.out.println( "p4=" + p4 );
        System.out.println( "p5=" + p5 );
        System.out.println( "p6=" + p6 );
        System.out.println( "p3.equals(p4): " + p3.equals( p4 ) );
        System.out.println( "p5 is 0: " + p5.equals( ListPolynomial.ZERO ) );
        System.out.println( "p6.equals(p1): " + p6.equals( p1 ) );
    }
}
The output of this program is intended to be as follows:
This: 3 total sum is 3 product is 3
This: x+5 total sum is x+8 product is 3x+15
This: x^2+2x+3 total sum is x^2+3x+11 product is 3x^3+21x^2+39x+45
This: 3x^2 total sum is 4x^2+3x+11 product is 9x^5+63x^4+117x^3+135x^2
This: x+2 total sum is 4x^2+4x+13 product is 9x^6+81x^5+243x^4+369x^3+270x^2
This: x^3-2x^2+5x+1 total sum is x^3+2x^2+9x+14 product is 9x^9+63x^8+126x^7+297x^6+828x^5+1548x^4+1719x^3+270x^2
p1=x+5
p2=x-5
p3=x^2-25
p4=x^2-25
p5=0
p6=x+5
p3.equals(p4): true
p5 is 0: true
p6.equals(p1): true

Polynomial Interface and ListPolynomial Class Sketch

Here is a rough outline of the Polynomial interface and the ListPolynomial class:
package cop3337;

public interface Polynomial
{
    public Polynomial negate( );
    public Polynomial add( Polynomial rhs );
    public Polynomial subtract( Polynomial rhs );
    public Polynomial multiply( Polynomial rhs );
    public Polynomial divide( Polynomial rhs );   
}

package cop3337;

public class ListPolynomial implements Polynomial
{
    public static final ListPolynomial ZERO = new ListPolynomial( );
    
    public ListPolynomial( )
    {
        first = null;
    }
    
    public ListPolynomial( String str )
      { /* YOU MUST PROVIDE */ }  
    
    // Makes an independent copy
    public ListPolynomial( ListPolynomial other )
      { /* YOU MUST PROVIDE */ }  
        
    public Polynomial negate( )
      { /* YOU MUST PROVIDE */ } 

    public Polynomial add( Polynomial rhs )
      { /* YOU MUST PROVIDE */ }  
    
    public Polynomial subtract( Polynomial rhs )
      { /* YOU MUST PROVIDE */ }  
    
    public Polynomial multiply( Polynomial rhs )
      { /* YOU MUST PROVIDE */ }  
        
    public Polynomial divide( Polynomial rhs )
      { /* YOU MUST PROVIDE */ }  

    public boolean equals( Object other )
      { /* YOU MUST PROVIDE */ }  
    
    public String toString( )
      { /* YOU MUST PROVIDE */ }
    
    private static class Node
    {
        int exp;
        int coeff;
        Node next;
    }

    private Node first;
}
The functionality of the Polynomial class is exactly as in Assignment #1, with the following modifications:
  1. If routines such as add, subtract, equals, etc. have parameters that are not ListPolynomials, you may throw an exception. The are elegant ways that would allow you to accept any Polynomial such as an ArrayPolynomial, but that is for another course.
  2. The divide routine does not have to be exact (i.e. there can be a remainder), however, at no point can an integer division not be exact. Thus 3x^2 divided by 2x^2 should throw an exception. On the other hand x+1 divided by x-1 should return 1 (and there is a remainder of 2, that would be available if there were a mod operation).
  3. The linked list is sorted in decreasing order, by exponent.
  4. Any coefficients that are zero will be removed from the linked list.
  5. If this ListPolynomial is zero, then first will be null.
  6. You do not have to go to great lengths to write efficient code. Just get it to work. You can reuse lots of code from Assignment #1, especially the difficult constructor code.

The divide algorithm

Use recursion for the divide algorithm. The basic idea is as follows. Suppose you are computing lhs/rhs. Look at the first term in each of lhs and rhs. If lhs has a lower exponent, the answer is 0. If the exponents are the same, divide the coefficients, and that is the answer as long as the division is exact (otherwise throw an exception). If lhs has a larger exponent, divide the coefficients and subtract the exponents. That is the first term of the quotient (as long as the division is exact). Multiply that term by rhs, subtract the result from lhs and then RECURSIVELY divide that result by rhs. Whatever answer you get, add it to the first term and you are done. As an example, consider 90x^9+630x^8+1260x^7+2970x^6+8280x^5+15480x^4+17190x^3+2700x^2 divided by 9x^6+81x^5+243x^4+369x^3+270x^2. Then dividing the first term of lhs and rhs gives 10x^3. We then compute: 10x^3 TIMES 9x^6+81x^5+243x^4+369x^3+270x^2, which is 90x^9+810x^8+2430x^7+3690x^6+2700x^5. We subtract this from the original 90x^9+630x^8+1260x^7+2970x^6+8280x^5+15480x^4+17190x^3+2700x^2, and we get -180x^8-1170x^7-720x^6+5580x^5+15480x^4+17190x^3+2700x^2. Now we RECURSIVELY divide this last value by 9x^6+81x^5+243x^4+369x^3+270x^2. When we do that, we will automatically get -20x^2+50x+10. Consequently, the final result is 10x^3-20x^2+50x+10.

Extra Credit

For a few extra points, valid only if the rest of the program works, toss in the following extras:
    public Polynomial mod( Polynomial rhs );
    public Polynomial gcd( Polynomial rhs );