Polynomial Addition and Subtraction

Write a program that adds and subtracts two polynomials. Implement the algorithm four different ways. The first two implementations will use arrays and the third will use pointers. 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 The three ways to implement the requirement: 1. Create and array or ArrayList of nodes, each node holding a term of the polynomial 2. Use a linked list of terms using pointers. 3. Polynomials are linked lists in one static array. Implementations 1, 2, and 3 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 third 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; }