Programmed in Java // Your task in this homework is to write a complete implementation for the // class X00000000 which is used to implement the polynomial operations. // You will need to store terms of a polynomial in the nodes of a linked list, the head // should store the term with highest degree and the tail the term with lowest degree. // The implementations of the classes for node, list and term are fully implemented for you. // An abstract class Polynomial provides a method to print polynomials. You should make // use of all these features and not try to reimplement any of them. 

// Advice: // There are three main steps to overcome: // 1. Write the constructor to enter data from a String giving a polynomial // 2. Write the add method, the subtract method will be very similar // 3. Write the multiply method, this helps with the divide method although that still needs // work. The remainder method is then easy. // // The main problems in the constructor are to break the input string apart into terms and to deal // with conventions about (shortcuts in) formulas for terms. How can we tell that a point of the // String is the beginning of a new term? What missing parts of a term might need to be added in? // // The add method works rather similarly to the merge method of mergeSort. Can you see why these // are similar? // // The multiply method needs to repeatedly multiply a single term from the first polynomial by the // second polynomial and use the add method to add together the results. // See also the general homework guidelines for other instructions before you submit work. public class X00000000 extends Polynomial { public static void main(String args[]) throws Exception { Polynomial p = new X00000000(" X^5"), q = new X00000000("X^2 - X + 1"); Utility.run(p, q); } public X00000000(String s) { // complete this code } public X00000000() { super(); } public Polynomial add(Polynomial p) { Polynomial ans = new X00000000(); // complete this code return ans; } public Polynomial subtract(Polynomial p) { Polynomial ans = new X00000000(); // complete this code return ans; } public Polynomial multiply(Polynomial p) { Polynomial ans = new X00000000(); // complete this code return ans; } public Polynomial divide(Polynomial p) throws Exception { Polynomial ans = new X00000000(); // complete this code return ans; } public Polynomial remainder(Polynomial p) throws Exception { Polynomial ans = new X00000000(); // complete this code return ans; } } //------- cut here. Place your new code above this line and submit only the ------ //------- code above this line as your homework. Do not make any code changes ---- //------- below this line. --------- abstract class Polynomial { DList data = null; public Polynomial() { data = new DList<>(); } public final String toString() { String ans = ""; boolean starting = true; try { DNode n = data.getFirst(); while (n != null) { if (!starting && n.getData().isPositive()) ans += " +"; starting = false; ans += " " + n.getData().toString(); n = data.getNext(n); } } catch (Exception e) { if (starting) return "0"; } return ans; } abstract public Polynomial add(Polynomial p); abstract public Polynomial subtract(Polynomial p); abstract public Polynomial multiply(Polynomial p); abstract public Polynomial divide(Polynomial p) throws Exception; abstract public Polynomial remainder(Polynomial p) throws Exception; } class Utility { public static void run(Polynomial p, Polynomial q) throws Exception { System.out.println("Polynomials p = " + p + " q = " + q); System.out.println("Sum " + p.add(q)); System.out.println("Difference " + p.subtract(q)); System.out.println("Product " + p.multiply(q)); System.out.println("Quotient " + p.divide(q)); System.out.println("Remainder " + p.remainder(q)); } } class Term { Double coefficient; int degree; public Term() { this(null, 0); } public boolean isPositive() { return coefficient > 0; } public Term(Double coefficient, int degree) { this.coefficient = coefficient; this.degree = degree; } public Double getCoefficient() { return coefficient; } public void setCoefficient(Double coefficient) { this.coefficient = coefficient; } public int getDegree() { return degree; } public void setDegree(int degree) { this.degree = degree; } public String toString() { String ans = ""; if (coefficient.doubleValue() == 0) return ""; if (degree == 0) return coefficient.toString(); if (coefficient != 1) { if (coefficient == -1) ans += "-"; else ans += coefficient + " "; } ans = ans + "X"; if (degree == 1) return ans; return ans + "^" + degree; } } class DList { private DNode header, trailer; private int size; public DList() { size = 0; header = new DNode(null, null, null); trailer = new DNode(null, header, null); header.setNext(trailer); } // utility methods public int size() { return size; } public boolean isEmpty() { return size == 0; } // give clients access to nodes, but not to the header or trailer public DNode getFirst() throws Exception { if (isEmpty()) throw new Exception("Empty"); return header.getNext(); } public DNode getLast() throws Exception { if (isEmpty()) throw new Exception("Empty"); return trailer.getPrev(); } public DNode getNext(DNode v) throws Exception { DNode ans = v.getNext(); if (ans == null || ans == trailer) throw new Exception("No such node"); return ans; } public DNode getPrev(DNode v) throws Exception { DNode ans = v.getPrev(); if (ans == null || ans == header) throw new Exception("No such node"); return ans; } // methods to change the list public void addBefore(T d, DNode v) { DNode u = v.getPrev(); DNode x = new DNode(d, u, v); u.setNext(x); v.setPrev(x); size++; } public void addAfter(T d, DNode v) { DNode w = v.getNext(); DNode x = new DNode(d, v, w); v.setNext(x); w.setPrev(x); size++; } public void addFirst(T d) { addAfter(d, header); } public void addLast(T d) { addBefore(d, trailer); } public T remove(DNode v) throws Exception { if (v == header || v == trailer) throw new Exception("Sentinel"); DNode u = v.getPrev(); DNode w = v.getNext(); w.setPrev(u); u.setNext(w); size--; return v.getData(); } // LinkedList testing methods: public String toString() { String ans = ""; DNode n = header; ans += "(H)<-->"; do { n = n.getNext(); if (n == trailer) ans += "(T)"; else ans += (n.getData() + "<-->"); } while (n != trailer); return ans; } } class DNode { private T data; private DNode prev, next; public DNode(T d, DNode p, DNode n) { data = d; next = n; prev = p; } public T getData() { return data; } public DNode getNext() { return next; } public DNode getPrev() { return prev; } public void setData(T d) { data = d; } public void setNext(DNode n) { next = n; } public void setPrev(DNode p) { prev = p; } }