//Driver
import java.io.*;
import java.util.*;
public class Project6
{
	private static Scanner console = new Scanner(System.in);
	public static void main(String[] args)
 
	{
		//3 instances of the class Polynomial
		Polynomial polyAdd = new Polynomial();
		Polynomial polySub = new Polynomial();
		Polynomial polyMul = new Polynomial();
 
		//Call to menu
		menu();
	}
	public static void menu()
 
	{
		//Decalre Variable to record the user's number entered to navigate menu
		int choice;
		String polynomial1;
		String polynomial2;
 
		//Menu print
		System.out.println("1. Create a Polynomial from the keyboard.");
		System.out.println("2. Add two Polynomials and Display Result.");
		System.out.println("3. Subtract two Polynomials and Display Result.");
		System.out.println("4. Multiply two Polynomials and Display Result.");
		System.out.println("5. Terminate the program");
		System.out.println("");
 
		//Take in choice variable to navigate the menu
		choice = console.nextInt();
		System.out.println("");
 
		//Switch controlling the menu system
		switch (choice)
		{
		//Take in two polynomails
		case 1:
		System.out.println("Enter the first polynomial.");
		polynomial1 = console.next();
		System.out.println("Enter the second polynomial.");
		polynomial2 = console.next();
		System.out.println("");
		break;
 
		//Add two Polynomials and Display result
		case 2:
		System.out.println("");
		break;
 
		//Subtract two Polynomials and Display result
		case 3:
		System.out.println("");
		break;
 
		//Multiply two Polynomials and Display result
		case 4:
 
		System.out.println("");
		break;
 
 
		//Terminate the program
		case 5:
		System.exit(0);
		break;
 
		//Default
		default:
		choice = console.nextInt();
		console.nextLine();
		}
		menu();
	}
 
}

import java.util.*;
 
public class Polynomial extends UnorderedArrayList<Double>
{
       //Default constructor
       //Postcondition: An array of the size 100, and
       //             length and maxSize are set to 100
    public Polynomial()
    {
         super();
         length = 100;
    }
 
      //Constructor with a parameter
      //Postcondition: An array of the size specified by
      //               the parameter size is created, length
      //               and maxSize are initialized to size
    public Polynomial(int size)
    {
         super(size);
         length = size;
    }
 
       //Method to evaluate a polynomial at a given value
       //Postcondition: The polynomial is evaluated at x and
       //               the value is returned
    public double evaluate(Double x)
    {
        double value = 0.0;
 
        Double coeff;
 
        for (int i = 0; i < length; i++)
        {
            coeff = retrieveAt(i);
 
            if (coeff != 0.0)
               value = value + coeff * Math.pow(x, i);
        }
 
        return value;
    }
 
       //Method to add two polynomials
       //Postcondition: This polynomial is added with the polynomial
       //               specified by the parameter right. A
       //               reference of the result is returned.
    public Polynomial add(Polynomial right)
    {
        int size = max(length, right.length);
        int i;
        Double sumCoeff;
 
        Double coeffP;
        Double coeffQ;
 
        Polynomial temp = new Polynomial(size);
 
        for (i = 0; i < min(length, right.length); i++)
        {
            coeffP = retrieveAt(i);
            coeffQ = right.retrieveAt(i);
 
            sumCoeff = coeffP + coeffQ;
            temp.replaceAt(i, sumCoeff);
        }
 
        if (size == length)
            for (i = min(length, right.length); i < length; i++)
                temp.replaceAt(i, retrieveAt(i));
        else
            for (i = min(length, right.length);
                                  i < right.length; i++)
                temp.replaceAt(i, right.retrieveAt(i));
 
        return temp;
    }
 
       //Method to subtract two polynomials
       //Postcondition: The polynomial specified by the
       //               parameter right is subtracted from this
       //               polynomial. A reference of the result
       //               is returned.
    public Polynomial subtract(Polynomial right)
    {
        int size = max(length, right.length);
        int i;
        Double diffCoeff;
 
        Double coeffP;
        Double coeffQ;
 
        Polynomial temp = new Polynomial(size);
 
        for (i = 0; i < min(length, right.length); i++)
        {
            coeffP = retrieveAt(i);
            coeffQ = right.retrieveAt(i);
 
            diffCoeff = coeffP - coeffQ;
            temp.replaceAt(i, diffCoeff);
        }
 
        if (size == length)
           for (i = min(length, right.length); i < length; i++)
               temp.replaceAt(i, retrieveAt(i));
        else
           for (i = min(length, right.length);
                                    i < right.length; i++)
           {
               Double coeff;
               coeff = right.retrieveAt(i);
               coeff = -coeff;
               temp.replaceAt(i, coeff);
           }
 
        return temp;
    }
 
       //Method to multiply two polynomials
       //Postcondition: This polynomial is multiplied with the
       //               polynomial specified by the parameter right.
       //               A reference of the result is returned.
    public Polynomial multiply(Polynomial right)
    {
 
        Polynomial temp = new Polynomial();
 
        System.out.println("See Programming Exercise 5 at "
                         + "the end of the chapter.");
 
        return temp;
    }
 
       //Method to read the coefficients of a polynomial
    public void read()
    {
        Scanner console = new Scanner(System.in);
 
        Double x;
 
        System.out.println("The degree of this polynomial is: "
                         + (length - 1));
        for (int i = 0; i < length; i++)
        {
            System.out.print("Enter the coefficient of x^"
                             + i + ": ");
 
            x = console.nextDouble();
            replaceAt(i, x);
        }
    }
 
       //Method to return the string containing the polynomial
    public String toString()
    {
        int i;
        int firstNonzeroCoeff = 0;
        Double coeff = 0.0;
        String str = "";
 
        for (i = 0; i < length; i++)
        {
            coeff = retrieveAt(i);
 
            if (coeff != 0.0)
            {
               firstNonzeroCoeff = i;
               break;
            }
        }
 
        if (firstNonzeroCoeff < length)
        {
           if (firstNonzeroCoeff == 0)
              str = retrieveAt(firstNonzeroCoeff) + " ";
           else
              str = retrieveAt(firstNonzeroCoeff) + "x^"
                       + firstNonzeroCoeff + " ";
 
           for (i = firstNonzeroCoeff + 1; i < length; i++)
           {
               coeff = retrieveAt(i);
 
               if (coeff != 0.0)
                  if (coeff > 0.0)
                     str += "+ " + coeff + "x^" + i + " ";
                  else
                     str += "- " + (-coeff) + "x^" + i + " ";
           }
        }
 
        return str;
    }
 
       //Method to determine the smaller of x and y
       //Postcondition: The smaller of x and y is returned
    public int min(int x, int y)
    {
        if (x <= y)
           return x;
        else
           return y;
    }
 
       //Method to determine the larger of x and y
       //Postcondition: The larger of x and y is returned
    public int max(int x, int y)
    {
        if (x >= y)
            return x;
        else
            return y;
    }
}

public class UnorderedArrayList<T> extends ArrayListClass<T>
{
	   //Default constructor
    public UnorderedArrayList()
    {
        super();
    }
 
       //Constructor with a parameter
    public UnorderedArrayList(int size)
    {
        super(size);
    }
 
       //Method to determine whether searchItem is in the list.
       //Postcondition: If searchItem is found, returns the
       //               location in the array where searchItem
       //               is found; otherwise, returns -1.
    public int seqSearch(T searchItem)
    {
        int loc;
        boolean found = false;
 
        for (loc = 0; loc < length; loc++)
            if (list[loc].equals(searchItem))
            {
                found = true;
                break;
            }
 
        if (found)
            return loc;
        else
            return -1;
    } //end seqSearch
 
       //Method to insert insertItem in the list at the position
       //specified by location.
       //Postcondition: Starting at location, the elements of
       //               the list are shifted to make room for
       //               insertItem, list[location] = insertItem;,
       //               and length++;
       //               If the list is full or location is out
       //               of range, an appropriate message is
       //               output.
    public void insertAt(int location, T insertItem)
    {
        if (location < 0 || location >= maxSize)
            System.err.println("The position of the item to "
                             + "be inserted is out of range.");
        else
            if (length >= maxSize)  //list is full
                System.err.println("Cannot insert in a full "
                                 + "list.");
            else
            {
                for (int i = length; i > location; i--)
                    list[i] = list[i - 1];  //move the
                                            //elements down
 
                list[location] = insertItem;
                length++;   //increment the length
            }
    } //end insertAt
 
       //Method to insert insertItem at the end of the list.
       //Postcondition: list[length] = insertItem; and length++;
       //               If the list is full, an appropriate
       //               message is output.
    public void insertEnd(T insertItem)
    {
        if (length >= maxSize)  //the list is full
            System.err.println("Cannot insert in a full list.");
        else
        {
              list[length] = insertItem;  //insert the
                                          //item at the end
              length++; //increment the length
        }
    } //end insertEnd
 
 
       //Method to replace the element in the list at
       //the position specified by location with repItem.
       //Postcondition: list[location] = repItem
       //               If location is out of range, an
       //               appropriate message is output.
    public void replaceAt(int location, T repItem)
    {
        if (location < 0 || location >= length)
            System.err.println("The location of the item to "
                             + "be replaced is out of range.");
        else
            list[location] = repItem;
    } //end replaceAt
 
       //Method to remove an item from the list.
       //The parameter removeItem specifies the item to
       //be removed.
       //Postcondition: If removeItem is found in the list, it
       //               is removed from the list and length is
       //               decremented by one.
    public void remove(T removeItem)
    {
        int loc;
 
        if (length == 0)
            System.err.println("Cannot delete from an "
                             + "empty list.");
        else
        {
            loc = seqSearch(removeItem);
 
            if (loc != -1)
                removeAt(loc);
            else
                System.out.println("The item to be deleted "
                                 + "is not in the list.");
        }
    } //end remove
}

public abstract class ArrayListClass<T>
                      implements ArrayListADT<T>, Cloneable
{
    protected int length;  //to store the length of the list
    protected int maxSize; //to store the maximum size of
                           //the list
    protected T[] list;    //array to hold the list elements
 
 
       //Default constructor
       //Creates an array of size 100
       //Postcondition: list points to the array, length = 0,
       //               and maxSize = 100
    public ArrayListClass()
    {
        maxSize = 100;
 
        length = 0;
        list = (T[]) new Object[maxSize];
    }
 
       //Constructor with a parameter
       //Creates an array of the size specified by the
       //parameter size.
       //Postcondition: list points to the array, length = 0,
       //               and maxSize = size
    public ArrayListClass(int size)
    {
        if (size <= 0)
        {
            System.err.println("The array size must be positive. "
                             + "Creating an array of size 100. ");
             maxSize = 100;
        }
        else
            maxSize = size;
 
        length = 0;
        list = (T[]) new Object[maxSize];
    }
 
       //Method to determine whether the list is empty.
       //Postcondition: Returns true if the list is empty;
       //               otherwise, returns false.
    public boolean isEmpty()
    {
        return (length == 0);
    }
 
       //Method to determine whether the list is full.
       //Postcondition: Returns true if the list is full;
       //               otherwise, returns false.
    public boolean isFull()
    {
        return (length == maxSize);
    }
 
       //Method to return the number of elements in the list.
       //Postcondition: Returns the value of length.
    public int listSize()
    {
        return length;
    }
 
       //Method to return the maximum size of the list.
       //Postcondition: Returns the value of maxSize.
    public int maxListSize()
    {
        return maxSize;
    }
 
       //Method to output the elements of the list.
       //Postcondition: Elements of the list are output on the
       //standard output device.
    public void print()
    {
        for (int i = 0; i < length; i++)
            System.out.println(list[i]);
        System.out.println();
    }
 
       //Returns a copy of objects data in store.
       //This method clones only the references stored in
       //the array. The objects that the array references
       //point to are not cloned.
    public Object clone()
    {
        ArrayListClass<T> copy = null;
 
        try
        {
            copy = (ArrayListClass<T>) super.clone();
        }
        catch (CloneNotSupportedException e)
        {
            return null;
        }
 
        copy.list = (T[]) list.clone();
 
        return copy;
    }
 
       //Method to determine whether item is the same as the item
       //in the list at the position specified by location.
       //Postcondition: Returns true if list[location] is the
       //               same as item; otherwise, returns false.
    public boolean isItemAtEqual(int location, T item)
    {
        if (location < 0 || location >= length)
        {
            System.err.println("The location of the item to "
                             + "be compared is out of range.");
            return false;
        }
 
        return (list[location].equals(item));
    }
 
       //Method to remove all the elements from the list.
       //Postcondition: length = 0
    public void clearList()
    {
        for (int i = 0; i < length; i++)
            list[i] = null;
 
          length = 0;
 
        System.gc();   //invoke garbage collector
    } //end clearList
 
       //Method to remove the item from the list at the position
       //specified by location.
       //Postcondition: The list element at list[location] is
       //               removed and length is decremented by 1.
       //               If location is out of range, an
       //               appropriate message is output.
    public void removeAt(int location)
    {
        if (location < 0 || location >= length)
            System.err.println("The location of the item to "
                             + "be removed is out of range.");
        else
        {
            for (int i = location; i < length - 1; i++)
                  list[i] = list[i + 1];
 
            list[length - 1] = null;
 
            length--;
        }
    } //end removeAt
 
       //Method to retrieve the element from the list at the
       //position specified by location.
       //Postcondition: A reference of the element at the
       //               position specified by location is
       //               returned. If location is out of range,
       //               an appropriate message is output and
       //               null is returned.
    public T retrieveAt(int location)
    {
        if (location < 0 || location >= length)
        {
            System.err.println("The location of the item to be "
                             + "retrieved is out of range.");
            return null;
        }
        else
            return list[location];
    } //end retrieveAt
 
 
       //Method to insert insertItem in the list at the position
       //specified by location.
       //Postcondition: Starting at location, the elements of
       //               the list are shifted to make room for
       //               insertItem, list[location] = insertItem;,
       //               and length++;
       //               If the list is full or location is out
       //               of range, an appropriate message is
       //               output.
    public abstract void insertAt(int location, T insertItem);
 
       //Method to insert insertItem at the end of the list.
       //Postcondition: list[length] = insertItem; and length++;
       //               If the list is full, an appropriate
       //               message is output.
    public abstract void insertEnd(T insertItem);
 
        //Method to replace the element in the list at
        //the position specified by location with repItem.
        //Postcondition: list[location] = repItem
        //               If location is out of range, an
        //               appropriate message is output.
    public abstract void replaceAt(int location, T repItem);
 
       //Method to determine whether searchItem is in the list.
       //Postcondition: If searchItem is found, returns the
       //               location in the array where searchItem
       //               is found; otherwise, returns -1.
    public abstract int seqSearch(T searchItem);
 
       //Method to remove an item from the list.
       //The parameter removeItem specifies the item to
       //be removed.
       //Postcondition: If removeItem is found in the list, it
       //               is removed from the list and length is
       //               decremented by one.
    public abstract void remove(T removeItem);
}