Polynomial Addition and Subtraction This is Java Write a program that adds and s
ID: 647421 • Letter: P
Question
Polynomial Addition and Subtraction
This is Java
Write a program that adds and subtracts two polynomials. Implement the algorithm four different ways. The first two implementations will use arrays and the third will use pointers. The forth is a set of linked lists in an array. Use the following interface for the 4 classes:
public interface PolynomialInterface
{
PolynomialInterface add(PolynomialInterface other);
// Effect: Adds value to owner of addPolynomial method.
// Postcondition: Return value = this + value.
PolynomialInterface subtract(PolynomialInterface other);
// Effect: Subtracts value from owner of addPolynomial method.
// Postcondition: Return value = this - value. void readPolynomial();
// Postcondition: polynomial read.
String toString();
// Postcondition: polynomial converted to string. }
The class must be able to read and print polynomials. Example: 4X4 + X3 - 3 + 4X4 - 2X3 + 4X 8X4 - X3 + 4X 3
The four ways to implement the requirements:
2- Create an array or ArrayList holding coefficients with the array indexes as exponents
3- Create and array or ArrayList of nodes, each node holding a term of the polynomial
4- Use a linked list of terms using pointers.
Polynomials are linked lists in one static array. Implementations 2, 3, and 4 require a class that will encapsulate a polynomial term unique to that particular implementation. The string from the constructor is a polynomial that each implementation must take apart and store each term in sorted order. All three implementations will follow the same basic algorithm to add two sorted polynomials. One array is used to store multiple polynomial instances and the free store. This array must be declared static so that it is available to all polynomial instances. There are two challenges in the first implementation. The first is converting the polynomial string given in the constructor into the terms of the polynomial. The second is taking the internal representation of the polynomial and converting it back to a string in the toString() method. The other three implementations will modify slightly the code from the first implementation for their constructor and toString() methods. Your code must use the Demo provided below.
Explanation / Answer
package demo;
import java.util.LinkedList;
import java.util.ListIterator;
/**
* This class stores and manipulates polynomials.
*/
public class Polynomial
{
/* a constructor that makes an empty polynomial (equal to 0) */
public Polynomial()
{
termList = new LinkedList<term>();
}
/* a constructor that defines a polynomial with a single term */
public Polynomial(int coeff, int exp)
{
termList = new LinkedList<term>();
term firstTerm = new term(coeff, exp);
termList.addFirst(firstTerm);
}
/* a constructor that defines a polynomial with 3 terms */
public Polynomial(int c1, int e1, int c2, int e2, int c3, int e3)
{
termList = new LinkedList<term>();
term term1 = new term(c1,e1);
term term2 = new term(c2,e2);
term term3 = new term(c3,e3);
termList.addLast(term1);
termList.addLast(term2);
termList.addLast(term3);
}
/* math operator methods */
public Polynomial add(Polynomial li2) /* return this + li2 */
{
Polynomial result = new Polynomial();
/* iterator for "this" object */
ListIterator<term> itr = termList.listIterator();
/* iterator for li2 object */
ListIterator<term> itr2 = li2.termList.listIterator();
term myTerm;
term li2Term;
while (itr.hasNext() && itr2.hasNext()) {
myTerm = itr.next();
itr.previous();
li2Term = itr2.next();
itr2.previous();
/* if the exponents are equal, create a term with the two
coefficients added together and that exponent */
/* add the term to the result */
if (myTerm.exp == li2Term.exp){
term term1 = new term((myTerm.coeff + li2Term.coeff),myTerm.exp);
result.termList.addLast(term1);
itr.next();
itr2.next();
}
/* if myTerm's exponent is less than li2Term's, create a term
with li2Term's coefficient and exponent */
/* add the term to the result */
else if (myTerm.exp < li2Term.exp){
term term2 = new term(li2Term.coeff,li2Term.exp);
result.termList.addLast(term2);
itr2.next();
}
/* if li2Term's exponent is less than myTerm's, create a term
with myTerm's coefficient and exponent */
/* add the term to the result */
else {
term term3 = new term(myTerm.coeff,myTerm.exp);
result.termList.addLast(term3);
itr.next();
}
}
/* still more terms to process in the self list (myTerm) */
while (itr.hasNext()){
myTerm = itr.next();
term term4 = new term(myTerm.coeff,myTerm.exp);
result.termList.addLast(term4);
}
/* still more terms to process in the param list (li2Term) */
while (itr2.hasNext()){
li2Term = itr2.next();
term term5 = new term(li2Term.coeff,li2Term.exp);
result.termList.addLast(term5);
}
return result;
}
public Polynomial subtract(Polynomial li2) /* return this - li2 */
{
Polynomial result = new Polynomial();
/* iterator for "this" object */
ListIterator<term> itr = termList.listIterator();
/* iterator for li2 object */
ListIterator<term> itr2 = li2.termList.listIterator();
term myTerm;
term li2Term;
while (itr.hasNext() && itr2.hasNext()) {
myTerm = itr.next();
itr.previous();
li2Term = itr2.next();
itr2.previous();
/* if the exponents are equal, create a term with the
coefficient of li2Term subtracted from the coefficient
of myTerm and that exponent */
/* add the term to the result */
if (myTerm.exp == li2Term.exp){
term term1 = new term((myTerm.coeff - li2Term.coeff),myTerm.exp);
result.termList.addLast(term1);
itr.next();
itr2.next();
}
/* if myTerm's exponent is less than li2Term's, create a term
with the opposite of li2Term's coefficient and exponent */
/* add the term to the result */
else if (myTerm.exp < li2Term.exp){
term term2 = new term(-li2Term.coeff,li2Term.exp);
result.termList.addLast(term2);
itr2.next();
}
/* if li2Term's exponent is less than myTerm's, create a term
with myTerm's coefficient and exponent */
/* add the term to the result */
else {
term term3 = new term(myTerm.coeff,myTerm.exp);
result.termList.addLast(term3);
itr.next();
}
}
/* still more terms to process in the self list (myTerm) */
while (itr.hasNext()){
myTerm = itr.next();
term term4 = new term(myTerm.coeff,myTerm.exp);
result.termList.addLast(term4);
}
/* still more terms to process in the param list (li2Term) */
while (itr2.hasNext()){
li2Term = itr2.next();
term term5 = new term(li2Term.coeff,li2Term.exp);
result.termList.addLast(term5);
}
return result;
}
public Polynomial multiply(Polynomial li2) /* return this * li2 */
{
Polynomial result = new Polynomial();
/* iterator for "this" object */
ListIterator<term> itr = termList.listIterator();
/* iterator for li2 object */
ListIterator<term> itr2 = li2.termList.listIterator();
term myTerm;
term li2Term;
/* while there are terms in the li2 object, create a new polynomial
that is the result of multiplying each term in the "this" object
with the current li2 term */
while (itr2.hasNext()){
li2Term = itr2.next();
Polynomial newresult = new Polynomial();
while (itr.hasNext()){
myTerm = itr.next();
term term1 = new term((myTerm.coeff * li2Term.coeff),(myTerm.exp + li2Term.exp));
newresult.termList.addLast(term1);
}
/* add the new polynomial to the result */
itr = termList.listIterator();
result = result.add(newresult);
}
return result;
}
public Polynomial derivative(Polynomial p)
{
Polynomial result = new Polynomial();
/* iterator for p object */
ListIterator<term> itr = p.termList.listIterator();
term theTerm;
while (itr.hasNext()){
theTerm = itr.next();
/* create a term that multiplies the coefficient and exponent
for the new coefficient and subtracts one from the exponent
for the new exponent */
/* add the term to the result */
term term1 = new term((theTerm.coeff * theTerm.exp),(theTerm.exp-1));
result.termList.addLast(term1);
}
return result;
}
/* return the result of evaluating the polynomial at point x */
public int evaluate(int x)
{
int result = 0;
/* iterator for "this" object */
ListIterator<term> itr = termList.listIterator();
term theTerm;
while (itr.hasNext()){
theTerm = itr.next();
/* accumulate the result of the coefficient multiplied by
the exponent raised to the x power */
result += theTerm.coeff * (int) Math.pow(x, theTerm.exp);
}
return result;
}
/* equality testing, true if x matches term for term */
public boolean equals(Object rhs)
{
if ( ! ( rhs instanceof Polynomial ) )
return false;
/* cast the object into a Polynomial */
Polynomial rhPolynomial = ( Polynomial ) rhs;
/* iterator for "this" object */
ListIterator<term> itr = termList.listIterator();
/* iterator for Object rhs */
ListIterator<term> rhitr = rhPolynomial.termList.listIterator();
term theTerm;
term rhTerm;
/* return true only if the two objects have the same number of
terms and each term has the same coefficient and exponent */
while (itr.hasNext() && rhitr.hasNext()) {
theTerm = itr.next();
rhTerm = rhitr.next();
if (theTerm.coeff != rhTerm.coeff)
return false;
if (theTerm.exp != rhTerm.exp)
return false;
if (itr.hasNext() &! rhitr.hasNext())
return false;
if (rhitr.hasNext() &! itr.hasNext())
return false;
else
return true;
}
return false;
}
/* cleanly prints the polynomial to a string */
public String toString()
{
ListIterator<term> itr = termList.listIterator();
term nextTerm;
String result = "";
boolean firstTime = true;
/* correctly handles the cases when the exponent is 0 or 1
and the coefficient is 0, 1, or -1 */
while (itr.hasNext()) {
nextTerm = itr.next();
if ((nextTerm.coeff > 0) && !firstTime)
result += "+ ";
firstTime = false;
if (nextTerm.coeff == 0)
result += "";
else if (nextTerm.exp == 1)
result += nextTerm.coeff + "x" + " ";
else if (nextTerm.coeff == 1)
result += "x^" + nextTerm.exp + " ";
else if (nextTerm.coeff == -1)
result += "-x^" + nextTerm.exp + " ";
else if (nextTerm.exp == 0)
result += nextTerm.coeff + " ";
else
result += nextTerm.coeff + "x^" + nextTerm.exp + " ";
}
if (result == "")
result = "0";
return result;
}
private class term
{
private term(int c, int e)
{
coeff = c;
exp = e;
}
public int coeff;
public int exp;
}
private LinkedList<term> termList;
/* main method that tests constructors and methods */
public static void main (String[] args)
{
/* tests empty polynomial constructor */
Polynomial li = new Polynomial();
System.out.println(li);
/* tests single term polynomial constructor */
Polynomial li2 = new Polynomial(2,3);
System.out.println(li2);
/* tests 3 term polynomial constructor */
Polynomial li3 = new Polynomial(3,5,2,3,-4,2);
System.out.println(li3);
/* tests toString method when the exponent is 1 */
Polynomial li4 = new Polynomial(2,1);
System.out.println(li4);
/* tests toString method when the coefficient is 1 */
Polynomial li4b = new Polynomial(1,6);
System.out.println(li4b);
/* tests toString method when the coefficient is -1 */
Polynomial li4c = new Polynomial(-1,6);
System.out.println(li4c);
/* tests toString method when the exponent is 0 */
Polynomial li5 = new Polynomial(2,0);
System.out.println(li5);
System.out.println();
Polynomial li7 = new Polynomial(4,6,-2,5,3,4);
Polynomial li9 = new Polynomial(2,8,-5,5,8,0);
Polynomial li10 = new Polynomial(-3,7,5,5,-1,4);
/* tests add method */
Polynomial li8 = new Polynomial();
li8 = li3.add(li7);
System.out.println("The result of adding " + li3 + "to " + li7 + "is: " + li8);
Polynomial li11 = new Polynomial();
li11 = li9.add(li10);
System.out.println("The result of adding " + li9 + "to " + li10 + "is: " + li11);
System.out.println();
/* tests subtract method */
Polynomial li12 = new Polynomial();
li12 = li3.subtract(li7);
System.out.println("The result of subtracting " + li7 + "from " + li3 + "is: " + li12);
Polynomial li13 = new Polynomial();
li13 = li9.subtract(li10);
System.out.println("The result of subtracting " + li10 + "from " + li9 + "is: " + li13);
System.out.println();
/* tests multiply method */
Polynomial li19 = new Polynomial(5,3,6,2,10,1);
Polynomial li20 = new Polynomial(3,3,7,2,1,1);
Polynomial li21 = new Polynomial();
li21 = li19.multiply(li20);
System.out.println("The result of multiplying " + li19 + "with " + li20 + "is: " + li21);
Polynomial li22 = new Polynomial();
li22 = li3.multiply(li7);
System.out.println("The result of multiplying " + li3 + "with " + li7 + "is: " + li22);
System.out.println();
/* tests derivative method */
Polynomial li16 = new Polynomial(6,3,2,2,10,1);
Polynomial li17 = new Polynomial().derivative(li16);
System.out.println("The derivative of " + li16 + "is: " + li17);
Polynomial li18 = new Polynomial().derivative(li3);
System.out.println("The derivative of " + li3 + "is: " + li18);
System.out.println();
/* tests evaluate method */
int x = li3.evaluate(2);
System.out.println("The result of evaluating " + li3 + " at 2 is: " + x);
int y = li3.evaluate(3);
System.out.println("The result of evaluating " + li3 + " at 3 is: " + y);
int z = li7.evaluate(3);
System.out.println("The result of evaluating " + li7 + " at 3 is: " + z);
int a = li7.evaluate(-2);
System.out.println("The result of evaluating " + li7 + " at -2 is: " + a);
System.out.println();
/* tests equals method */
System.out.println(li3 + "equals " + li7 + ": " + li3.equals(li7));
Polynomial li14 = new Polynomial(3,5,2,3,-4,2);
System.out.println(li3 + "equals " + li14 + ": " + li3.equals(li14));
Polynomial li15 = new Polynomial(3,5);
System.out.println(li3 + "equals " + li15 + ": " + li3.equals(li15));
}
}