Polynomials as lists of terms

 

We can represent a polynomial of one variable as an ordered list of terms, where the terms are ordered by their exponents. There are multiple ways to add or subtract two polynomials from an algorithmic standpoint. Here are two possibilities:

• Traverse both lists and examine the two terms at the current iterator position. If the exponent of one is smaller than the exponent of the other, then insert this one into the result and advance that list’s iterator. If the exponents are equal, then create a new term with the exponent and the sum of the coefficients, and advance both iterators.
• Traverse one list, adding a single term into another polynomial by looking for a matching exponent. If the exponents match, add the coefficients. Otherwise, place the single term in the other list at the right position to keep the terms ordered by exponent.

For example: 3x^4 + 2x^2 + 3x + 7 added to 2x^3 + 4x + 5 yields 3x^4 + 2x^3 + 2x^2 + 7x + 12.

Write a program to add and subtract polynomials (you don’t need to read input from the keyboard, just use methods to construct the polynomials). I have defined a class Term that contains the exponent and coefficient and implements the Comparable interface. You should define a class Polynomial that uses a java.util.LinkedList of Term objects. A toString() and equals() method is provided to help you debug. Things to keep in mind:

• Make sure that there is only one representation of zero.
  • This is frequently the cause of errors because a polynomial like 0x^4 is not equal to 0x^0 but both have a toString representation of “0”. This yields strange error messages like “Expected polynomial 0 but was 0.”
• Make sure that polynomials are built in order of exponent.
• If two terms cancel out, don’t include a zero term unless the whole polynomial is zero.
  • Again, 0x^4 + 0x^3 +0x^2 will print as “0” but is not the same as 0x^0.
• You should not change the Term class.
• Do not alter this or the parameter polynomials in your methods. They are expected to be immutable objects (like String objects).

HERE IS THERE PROGRAM YOU HAVE TO DO:import java.util.List;

import java.util.LinkedList;

import java.util.ListIterator;

public class Polynomial {

public static final Polynomial ZERO = new Polynomial(Term.ZERO);

private List<Term> terms;

public Polynomial() {

this.terms = new LinkedList<Term>();

}

public Polynomial(Term [] terms) {

this();

Polynomial p = new Polynomial();

for (Term term : terms) {

p = p.add(new Polynomial(term));

}

this.terms = p.terms;

}

public Polynomial(Term term) {

this();

terms.add(term);

}

public Polynomial(Polynomial other) {

this();

for (Term term : other.terms) {

terms.add(term);

}

}

public Polynomial add(Polynomial other) {

Polynomial result = new Polynomial();

// add your code here

return result;

}

public Polynomial sub(Polynomial other) {

Polynomial result = new Polynomial();

// add your code here

return result;

}

@Override

public boolean equals(Object obj) {

if (!(obj instanceof Polynomial)) {

return false;

}

Polynomial other = (Polynomial)obj;

return this.terms.equals(other.terms);

}

public String toString() {

StringBuilder builder = new StringBuilder();

for (Term term : this.terms) {

if (!term.equals(Term.ZERO)) {

if (builder.length() != 0) {

if (term.isNegative()) {

builder.append(” – “);

term = term.negate();

} else {

builder.append(” + “);

}

}

builder.append(term.toString());

}

}

if (builder.length() == 0) {

return “0”;

}

return builder.toString();

}