Polynomial Addition and Subtraction

I need the LinkedListInArrayPolynomial class for this program, I have provided the PolynomialInterface, LLInArrayNode class along with the PolynomialDemo. I just need the LinkedListInArrayPolynomial.

Write a program that adds and subtracts two polynomials. Implement the algorithm four different ways. The forth is a set of linked lists in an array. Use the following

interface for the 4 classes:

public interface PolynomialInterface

{

PolynomialInterface add(PolynomialInterface other);

// Effect: Adds value to owner of addPolynomial method.

// Postcondition: Return value = this + value.

PolynomialInterface subtract(PolynomialInterface other);

// Effect: Subtracts value from owner of addPolynomial method.

// Postcondition: Return value = this - value.

void readPolynomial();

// Postcondition: polynomial read.

String toString();

// Postcondition: polynomial converted to string.

}

The class must be able to read and print polynomials.

+ 4X4

- 2X3 + 4X

= 8X4

- X3 + 4X 3

Polynomials are linked lists in one static array.

Implementations 2, 3, and 4 require a class that will encapsulate a polynomial term unique to that particular implementation.

The string from the constructor is a polynomial that each implementation must take apart and store each term in sorted order. All

three implementations will follow the same basic algorithm to add two sorted polynomials. This algorithm resembles the method

merge() found on page 642-643 of the text. In the fourth implementation one array is used to store multiple polynomial instances and

the free store. This array must be declared static so that it is available to all polynomial instances and initialized once by the

first instantiation of a polynomial.

There are two challenges in the first implementation. The first is converting the polynomial string given to the constructor into

the terms of the polynomial. The second is taking the internal representation of the polynomial and converting it back to a string in

the toString() method. The other three implementations will modify slightly the code from the first implementation for their

constructor and toString() methods. Your code must use the Demo class that I will provide. Your code must use the Demo class that I

will provide. Below is the syntax for working with the interface:

public PolynomialInterface add(PolynomialInterface other)

{

ArrayWithExponentAsIndex answer = new ArrayWithExponentAsIndex ();

ArrayWithExponentAsIndex parameter = (ArrayWithExponentAsIndex)other;

3

Here is code that can guide you in the fourth implementation. It creates an array of nodes and connects them into the freeStore.

public class LinkedListInArrayPolynomial implements PolynomialInterface

{

private static final int NUL = -1;

private static int free; //*** Reference to the first node on the free list

private static LLInArrayPolyNode[] nodeArray= new LLInArrayPolyNode[1000];

private static boolean nodeArrayIsInitialized = false;

private String polyString;

private int polynomial = NUL; //*** Reference to the first node on the list

public LinkedListInArrayPolynomial()

{

if(!nodeArrayIsInitialized)

initializeStaticArray();

}

public LinkedListInArrayPolynomial(String polyString)

{

if(!nodeArrayIsInitialized)

initializeStaticArray();

this.polyString = polyString;

storePolynomial();

}

private void initializeStaticArray()

{

// fill array with nodes

for(int x = 0; x < nodeArray.length; x++)

{

nodeArray[x] = new LLInArrayPolyNode();

}

for (int index = 1; index < nodeArray.length; index++)

{

nodeArray[index - 1].setNext(index);

}

nodeArray[ nodeArray.length - 1].setNext(NUL);

free = 0;

nodeArrayIsInitialized = true;

}

protected int getNode()

//*** Returns the index of the next available node from the freeStore

//*** and updates the freeStore index.

{

int hold;

hold = free;

free = nodes[free].next;

return hold;

}

public class LLInArrayNode implements Comparable

{

private int NUL = -1;

private String value;

private int next;

public LLInArrayNode()

{

}

public LLInArrayNode(LLInArrayNode clone)

{

this.value = clone.value;

this.next = clone.next;

}

public LLInArrayNode(String value)

{

this.value = value;

this.next = NUL;

}

public LLInArrayNode(String value,int next)

{

this.value = value;

this.next = next;

}

public int compareTo(LLInArrayNode other)

{

// calls the String compareToIgnoreCase() method

return this.value.compareToIgnoreCase(other.value);

}

public String getValue()

{

return value;

}

public void setValue(String value)

{

this.value = value;

}

public int getNext()

{

return next;

}

public void setNext(int next)

{

this.next = next;

}

public String toString()

{

return "Value = " + value + " "

+ " next " + next;

}

}

public class PolynomialDemo

{

public static void main(String[] args)

{

// example strings constructor must handle

// String s = "44";

// String s = "44x";

// String s = "4x^4+3x^3-3";

// String s = "4x^3-3x^11";

// String s = "44x^6-3x^10+4x^4";

// String s = "25x^5-3x^13+4x^12-78";

// String s ="34x^15-44x^14-3x^12+4x^31-78";

// String s1 = "44";

// String s2 = "44x-78";

String s1 = "4x^4+3x^3-3";

String s2 = "4x^6-3x^12";

//String s1 = "4x^14-3x^12+4x^4+78";

//String s2 = "-4x^4-3x^12+4x^17-78";

// String s1 = "4x^4+3x^11+4x^10";

// String s2 = "5x^14-3x^12+4x^19-78";

// String s1 = "4x^5+4x^4-3x^12-4x^41-78";

// String s2 = "-4x^4+3x^12+4x^41+78";

// Four implementations of the interface

PolynomialInterface exAsIndex1 = new ArrayWithExponentAsIndexPolynomial(s1);

PolynomialInterface exAsIndex2 = new ArrayWithExponentAsIndexPolynomial(s2);

PolynomialInterface exAsIndex3;

exAsIndex3 = exAsIndex1.add(exAsIndex2);

System.out.println("First test is with array index as exponent. " );

// System.out.println("exAsIndex1 string is " + s1);

System.out.println("exAsIndex1 = " + exAsIndex1);

// System.out.println("exAsIndex2 string is " + s2);

System.out.println("exAsIndex2 = " + exAsIndex2);

System.out.println("exAsIndex3 = exAsIndex1.add(exAsIndex2) " + exAsIndex3);

exAsIndex3 = exAsIndex1.subtract(exAsIndex2);

// System.out.println("exAsIndex1 string is " + s1);

// System.out.println("exAsIndex1 = " + exAsIndex1);

// System.out.println("exAsIndex2 string is " + s2);

//System.out.println("exAsIndex2 = " + exAsIndex2);

System.out.println("exAsIndex3 = exAsIndex1.subtract(exAsIndex2) " + exAsIndex3);

System.out.println();

PolynomialInterface sortA1 = new ArraySortedPolynomial(s1);

PolynomialInterface sortA2 = new ArraySortedPolynomial(s2);

PolynomialInterface sortA3;

sortA3 = sortA1.add(sortA2);

System.out.println("Second test is sorted array of terms.");

// System.out.println("sortA1 string is " + s1);

System.out.println("sortA1 = " + sortA1);

// System.out.println("sortA2 string is " + s2);

System.out.println("sortA2 = " + sortA2);

System.out.println("sortA3 = sortA1.add(sortA2) " + sortA3);

sortA3 = sortA1.subtract(sortA2);

// System.out.println("sortA1 string is " + s1);

//System.out.println("sortA1 = " + sortA1);

// System.out.println("sortA2 string is " + s2);

//System.out.println("sortA2 = " + sortA2);

System.out.println("sortA3 = sortA1.subtract(sortA2) " + sortA3);

System.out.println();

PolynomialInterface link1 = new LinkListPolynomial(s1);

PolynomialInterface link2 = new LinkListPolynomial(s2);

PolynomialInterface link3;

System.out.println("Third test is linked list of terms.");

// System.out.println("link1 string is " + s1);

System.out.println("link1 = " + link1);

// System.out.println("link2 string is " + s2);

System.out.println("link2 = " + link2);

link3 = link1.add(link2);

System.out.println("sum of link1 and link2 = " + link3);

// System.out.println("link1 string is " + s1);

// System.out.println("link1 = " + link1);

// System.out.println("link2 string is " + s2);

//System.out.println("link2 = " + link2);

link3 = link1.subtract(link2);

System.out.println("link1 minus link2 = " + link3);

System.out.println();

PolynomialInterface linkInArray1 = new LinkedListInArrayPolynomial(s1);

PolynomialInterface linkInArray2 = new LinkedListInArrayPolynomial(s2);

PolynomialInterface linkInArray3 = new LinkedListInArrayPolynomial();

System.out.println("Forth test is linked list of terms in an array.");

//System.out.println("linkInArray1 string is " + s1);

System.out.println("linkInArray1 = " + linkInArray1);

// System.out.println("linkInArray2 string is " + s2);

System.out.println("linkInArray2 = " + linkInArray2);

linkInArray3 = linkInArray1.add(linkInArray2);

System.out.println("sum of linkInArray1 and linkInArray2 = " + linkInArray3);

linkInArray3 = linkInArray1.subtract(linkInArray2);

System.out.println("linkInArray1 minus linkInArray2 = " + linkInArray3);

}

}