/******************************************************************************
* 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<Integer, Double> coefficients;
// internal constructor, initializes new symbol table
private Polynomial() {
coefficients = new ST<Integer, Double>();
}
// internal constructor to initialize given a symbol table
private Polynomial(ST<Integer, Double> 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<Integer, Double>();
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<Integer, Double> newPoly = new ST<Integer, Double>();
// 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<Integer, Double> newPoly = new ST<Integer, Double>();
// 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);
}
}
