/****************************************************************************** * Name: * NetID: * Precept: * * Description: Provides a data type Polynomial which works by using a symbol * table to pair exponents (integers) with coefficients (doubles). ******************************************************************************/ import edu.princeton.cs.algs4.StdIn; import edu.princeton.cs.algs4.StdOut; import edu.princeton.cs.algs4.ST; // (add other imports if necessary) public class Polynomial { // (Public) constant indicating the largest possible exponent that a // term can take in this Polynomial class public static final int MAX_EXPONENT = 10000; // This instance variable is part of the "Suggested Progress Steps" as // a possible solution (but there are many other equally good // solutions which do not use an ST object, so feel free to comment // this instance variable if it is confusing you) private final ST coefficients; // internal constructor, initializes new symbol table private Polynomial() { coefficients = new ST(); } // internal constructor to initialize given a symbol table private Polynomial(ST s) { coefficients = s; } // Create a polynomial from an array 'coeffs' in which 'coeffs[i]' is // coefficient of x^i (x raised to the i-th power). public Polynomial(double[] coeffs) { if (coeffs.length > MAX_EXPONENT) throw new RuntimeException("LInput array is too long."); // iterate through coeffs, adding to our sym table only non-zero ones coefficients = new ST(); for (int i = 0; i < coeffs.length; i++) { if (coeffs[i] != 0) { coefficients.put(i, coeffs[i]); } } } // Return the value of the coefficient of the term with exponent // 'expo' (and 0.0 if such a coefficient doesn't exist) public Double coeff(int expo) { if (expo < 0 || expo >= MAX_EXPONENT) throw new RuntimeException("Exponent not in range."); // use this to prevent calling both contains() and get(), which is // not efficient as it iterates twice through the table, when we // really only need to do it once Double d = coefficients.get(expo); if (d == null) return 0.0; else return d; } // Return a string representation of the polynomial public String toString() { // Use the (provided) pretty printer. // NOTE: using this class will require compiling it: // $ javac-algs4 PolynomialTools.java return PolynomialTools.toString(this); } // Create a new immutable polynomial resulting from the addition of the // instance polynomial to 'that' public Polynomial add(Polynomial that) { // create a new ST ST newPoly = new ST(); // copy over pairings from that for (int exp: that.coefficients.keys()) { newPoly.put(exp, that.coeff(exp)); } // add the necessary coefficients from this for (int exp: coefficients.keys()) { newPoly.put(exp, coefficients.get(exp) + that.coeff(exp)); } // return a new polynomial based on this symbol table return new Polynomial(newPoly); } // Create a new immutable polynomial resulting from the product of the // instance polynomial and 'that' public Polynomial multiply(Polynomial that) { // create a new ST ST newPoly = new ST(); // loop through the keys in both polynomials for (int exp1: that.coefficients.keys()) { for (int exp2: coefficients.keys()) { if (exp1 + exp2 >= MAX_EXPONENT) throw new RuntimeException("Product is too large"); Double d = newPoly.get(exp1+exp2); // if exp1+exp2 is not in the symbol table, put it in if (d == null) { newPoly.put(exp1+exp2, that.coeff(exp1) * this.coeff(exp2)); } // otherwise, just add the product to what's already there else newPoly.put(exp1+exp2, that.coeff(exp1)*this.coeff(exp2) + d); } } return new Polynomial(newPoly); } // Evaluate the polynomial at some value 'x' public double evaluate(double x) { double answer = 0; // loop through the exponents, incrementing answer when needed for (int exp: coefficients.keys()) { answer += Math.pow(x, exp) * coefficients.get(exp); } return answer; } // Some unit testing public static void main(String[] args) { // ========= // Our tests // ========= runStaffTests(); // ================================ // Your own tests below? (optional) // ================================ double[] c1 = {1, 3, 4}; double[] c2 = {1, 1, 2}; Polynomial p1 = new Polynomial(c1); Polynomial p2 = new Polynomial(c2); System.out.println("------------------------------------------------"); System.out.println(p2.multiply(p1)); System.out.println(p1.multiply(p2)); System.out.println("------------------------------------------------"); System.out.println(p1.add(p2)); System.out.println(p2.add(p1)); // ... } // Below are tests we have created as an example and so that you may // check your work on your computer public static void runStaffTests() { // =================================== // Creation of test Polynomial objects // =================================== // Empty polynomial! Polynomial mz = new Polynomial(new double[0]); // Single terms (to test constructor) Polynomial m10 = PolynomialTools.makeSingleTerm(4.0, 10); Polynomial m5 = PolynomialTools.makeSingleTerm(2.0, 5); Polynomial m2 = PolynomialTools.makeSingleTerm(7.5, 2); Polynomial m1 = PolynomialTools.makeSingleTerm(1.0, 1); Polynomial m0 = PolynomialTools.makeSingleTerm(13.0, 0); // Polynomials (to test operations) Polynomial p1a = m10.add(m5).add(m2); Polynomial p1b = m2.add(m10).add(m5); Polynomial p2 = m0.add(m2).add(m5); Polynomial p3 = m0.add(m10); Polynomial p4 = m0.add(m1); Polynomial p5 = p4.multiply(p4); // multiply with itself Polynomial p6 = p4.multiply(p3); // multiply with different // ================================================================ // Tests using string formatting through the PolynomialTools module // ================================================================ // Empty polynomial (testing edge case) PolynomialTools.runStringTest(mz, "0.0"); // Testing monomials (so just formatting) PolynomialTools.runStringTest(m10, "4.0*x^10"); PolynomialTools.runStringTest(m10, "4.0*x^10"); PolynomialTools.runStringTest(m5, "2.0*x^5"); PolynomialTools.runStringTest(m2, "7.5*x^2"); PolynomialTools.runStringTest(m1, "1.0*x^1"); PolynomialTools.runStringTest(m0, "13.0"); // Testing polynomials (so result of operation) PolynomialTools.runStringTest(p1a, "7.5*x^2 + 2.0*x^5 + 4.0*x^10"); PolynomialTools.runStringTest(p1b, "7.5*x^2 + 2.0*x^5 + 4.0*x^10"); PolynomialTools.runStringTest(p1a, p1b.toString()); // transitivity PolynomialTools.runStringTest(p2, "13.0 + 7.5*x^2 + 2.0*x^5"); PolynomialTools.runStringTest(p3, "13.0 + 4.0*x^10"); PolynomialTools.runStringTest(p4, "13.0 + 1.0*x^1"); // Testing multiplication PolynomialTools.runStringTest(p5, "169.0 + 26.0*x^1 + 1.0*x^2"); PolynomialTools.runStringTest(p6, "169.0 + 13.0*x^1 + 52.0*x^10 + 4.0*x^11"); // ====================== // Tests using 'evaluate' // ====================== Polynomial p66 = new Polynomial( new double[] {1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0 } ); Polynomial p77 = new Polynomial( new double[] {0.0, 1.0 + 1.0/2.0 + 1.0/3.0 + 1.0/4.0 + 1.0/5.0 + 1.0/6.0 } ); Polynomial p88 = p66.multiply(p77); // [because doubles are tricky] "fake" test using evaluation PolynomialTools.runEvaluateTest(p88, 1.0, 17.15); PolynomialTools.runEvaluateTest(p88, 2.0, 622.3); } }