Problem Three: Implement the Polynomials class. Once you do, PolynomialCalculator will work, because in the previous problem you implemented the generic RPNCalculator, which can handle any CalculatorOperand. Represent a monomial as a single node with two integers (the coefficient and the degree). Represent a polynomial as a linked list of monomials, in order of decreasing degree. Only monomials with nonzero coefficients should be present in your list. Thus, for example, 6x^10 + 4x^3 + 15x^2 + 2 should be represented as the list (6,10) -> (4, 3) -> (15, 2) -> (2, 0). (where (6,10) is a node containing two integers and a next pointer). It follows that the zero polynomial is the empty list. Use the the dummy header node, just like in OrderedList. Thus, at creation, your linked list has one node, whose contents don't matter. Write the constructor that takes a coefficient c and a degree d and creates a new polynomial cx^d. If the coefficient is 0, it should create the zero polynomial. You will never create polyomials with more than a single monomial by using the constructor. Instead, you will use the addition and subtraction methods of the calculator to build up larger polynomials as sums of monomials. Next, implement add. It is essentially the same as merge, except you have a special case when the degrees of the two monomials are equal, and a special case within that when the coefficients are opposite. Think those special cases through. Test your add thoroughly before moving on, using the PolynomialCalculator. You will notice that subtract is very similar to add. You could, of course, copy and paste the add to create subtract by making a few changes, but that would be wasteful. Instead write a more general method addTimesMonomial that is almost the same as add, except the elements of that get multiplied by a given monomial before being added to this (remember not to modify that, however). For add, the monomial is 1x^0; for subtract, the monomial is -1x^0. You will use other monomials for multiply. Once you get addTimesMonomial, change add to be one line, and write subtract in one line. Test these methods. Now use addTimesMonomial to write multiply. Here is a sample input and output that you should get: 1 2 x^2 3 4 x^2 3x^4 + 3x^4 + x^2 5 6 3x^4 + x^2 5x^6 7 8 3x^4 + x^2 5x^6 7x^8 - 3x^4 + x^2 -7x^8 + 5x^6 * -21x^12 + 8x^10 + 5x^8 + -21x^12 + 8x^10 + 5x^8 -1 0 -21x^12 + 8x^10 + 5x^8 -1 * 21x^12 - 8x^10 - 5x^8 0 0 21x^12 - 8x^10 - 5x^8 0 * 0 q

What I have so far:

* Polynomial Class which implements the CalculatorOperand interface. * Maintains polynomials as an ordered linked list, with monomials arranged by decreasing degree */

public class Polynomial implements CalculatorOperand {

private class PolyNode { int coeff; int degree; PolyNode next; // TODO: add a constructor PolyNode(int c, int d) { coeff = c; degree = d; } PolyNode(int c, int d, PolyNode n) { coeff = c; degree = d; next = n; } }

private PolyNode monomialsList = new PolyNode(0,-1,null); // TODO: initialize in the constructor

Polynomial(int coeff, int degree) { // TODO: IMPLEMENT if (coeff != 0 && degree >=0) { monomialsList.next = new PolyNode(coeff, degree, null); } }

/** * Returns this + coeff*x^degree * that; does not modify this or that. Assumes coeff is nonzero. */

// NOTE: normally, this would be private, but leave it public so we can test it public Polynomial addTimesMonomial (Polynomial that, int coeff, int degree) { return null; // TODO: IMPLEMENT; READ THE ASSIGNMENT AND IMPLEMENT add FIRST }

/** * Returns this+that; does not modify this or that */ public Polynomial add (Polynomial that)

/** * Returns this-that; does not modify this or that */ public Polynomial subtract (Polynomial that) { return null; // TODO: IMPLEMENT }

/** * Returns this*that; does not modify this or that */ public Polynomial multiply (Polynomial that) { return null; }

/** * Prints the polynomial the way a human would like to read it * @return the human-readable string representation */ public String toString () { if (monomialsList.next == null) return "0";

String ret = monomialsList.next.coeff<0 ? "-" : ""; for (polynode p = monomialsList.next; p!=null; { if (p.degree 0 || (p.coeff! =1 && p.coeff! =-1)) ret=ret + java.lang.math.abs(p.coeff) ;> 0) ret = ret + "x"; if (p.degree > 1) ret = ret + "^" + p.degree; if (p.next != null) ret = ret + (p.next.coeff<0 ? " - " : " + "); } return ret; } }