Creating a polynomial linked list program for adding/subtracting/multiplying pol
ID: 3809228 • Letter: C
Question
Creating a polynomial linked list program for adding/subtracting/multiplying polynomials?
I've attached the code below with TODO with the parts I am stuck on:
/**
* 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;
PolyNode(int c, int d) {
coeff = c;
degree = d;
}
}
private PolyNode monomialsList; // TODO: initialize in the constructor
Polynomial(int coeff, int degree) {
// TODO: IMPLEMENT
PolyNode newNode = new PolyNode(coeff, degree);
}
/**
* 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) {
return null;// TODO: IMPLEMENT
}
/**
* 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; p=p.next) {
if (p.degree == 0 || (p.coeff!=1 && p.coeff!=-1))
ret = ret + java.lang.Math.abs(p.coeff) ;
if (p.degree > 0)
ret = ret + "x";
if (p.degree > 1)
ret = ret + "^" + p.degree;
if (p.next != null)
ret = ret + (p.next.coeff<0 ? " - " : " + ");
}
return ret;
}
}
Explanation / Answer
Program code to copy:
public class Polynomial
{
class PolyNode
{
int coeff;
int degree;
PolyNode next;
public PolyNode(int coeff, int degree)
{
this.coeff = coeff;
this.degree = degree;
this.next = null;
}
public String toString()
{
String form = Math.abs(coeff) + "";
if (degree == 0)
return form;
else if (degree == 1)
return form + "x";
else
return form + "x^" + degree;
}
}
private PolyNode monomialsList; // TODO: initialize in the constructor
/**
* Default constructor creates a Polynomial with no terms
*/
public Polynomial() // DO NOT MODIFY THIS CONSTRUCTOR
{
monomialsList = null;
}
// copy constructor to make the copy of the current
public Polynomial(Polynomial p)
{
// get the node of list
PolyNode newNode = p.monomialsList;
while (newNode != null)
{
// by using addTerm, the term will be added as per the
// power value
addTerm(newNode.coeff, newNode.degree);
// move the pointer next of the n node
newNode = newNode.next;
}
}
/**
* 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)
{
Polynomial newPoly = new Polynomial();
Polynomial tempPoly = new Polynomial();
tempPoly.addTerm(coeff, degree);
Polynomial temp = new Polynomial();
temp = tempPoly.multiply(that);
newPoly = this.add(temp);
return newPoly; // TODO: IMPLEMENT; READ THE ASSIGNMENT AND IMPLEMENT add FIRST
}
/**
* Creates a new Term and Node containing it and inserts it in its proper
* place in this Polynomial (i.e. in ascending order by exponent)
*
* @param coeff
* the coefficient of the new Term
* @param degree
* the exponent of the new Term
*/
public static int count = 0;
public void addTerm(int coeff, int degree)
{
PolyNode temp = new PolyNode(coeff, degree); // new node
PolyNode current;
/* Special case for head node */
if (monomialsList == null || monomialsList.degree < temp.degree)
{
temp.next = monomialsList;
monomialsList = temp;
}
else
{
/* Locate the node before point of insertion. */
current = monomialsList;
while (current.next != null && current.next.degree > temp.degree)
{
current = current.next;
}
if (current != null)
{
if (current.degree == temp.degree)
{
current.coeff += temp.coeff;
return;
}
}
if (current.next != null)
{
if (current.next.degree == temp.degree)
{
current.next.coeff += temp.coeff;
return;
}
}
temp.next = current.next;
current.next = temp;
}
}
// method to get the current node information
String getTerm(int coefficient, int exponent)
{
if (coefficient == 1 && exponent == 1)
return "x";
else if (coefficient == 1)
return "x^" + String.valueOf(exponent);
else if (exponent == 0)
return String.valueOf(coefficient);
else if (exponent == 1)
return String.valueOf(coefficient) + "x";
else
return String.valueOf(coefficient) + "x^"
+ String.valueOf(exponent);
}
/**
* Prints the polynomial the way a human would like to read it
*
* @return the human-readable string representation
*/
public String toString()
{
StringBuffer sb = new StringBuffer();
for (PolyNode tmp = monomialsList; tmp != null; tmp = tmp.next)
{
if (tmp.coeff < 0)
sb.append(" - " + tmp.toString());
else
sb.append(" + " + tmp.toString());
}
return sb.toString();
}
/**
* Returns this*that; does not modify this or that
*/
public Polynomial multiply(Polynomial that)
{
Polynomial tempPoly = new Polynomial();
PolyNode n1 = monomialsList;
PolyNode temp = that.monomialsList;
PolyNode n2 = temp;
while (n1 != null)
{
while (n2 != null)
{
tempPoly.addTerm((n1.coeff * n2.coeff),
(n1.degree + n2.degree));
n2 = n2.next;
}
n2 = temp;
n1 = n1.next;
}
return tempPoly;
}
/**
* Returns this+that; does not modify this or that
*/
public Polynomial add(Polynomial that)
{
// create a new polynomial object by using the this operator
Polynomial result = new Polynomial();
PolyNode p1, p2;
int power = this.monomialsList.degree > that.monomialsList.degree ? this.monomialsList.degree
: that.monomialsList.degree;
while (power >= 0)
{
p1 = this.monomialsList;
while (p1 != null)
{
if (p1.degree == power)
break;
p1 = p1.next;
}
p2 = that.monomialsList;
while (p2 != null)
{
if (p2.degree == power)
break;
p2 = p2.next;
}
if ((p1 != null) && (p2 != null))
result.addTerm((p1.coeff + p2.coeff), p1.degree);
else if (p1 != null)
result.addTerm(p1.coeff, p1.degree);
else if (p2 != null)
result.addTerm(p2.coeff, p2.degree);
power--;
}
// return the resultant polynomial
return result;
}
/**
* Returns this-that; does not modify this or that
*/
public Polynomial subtract(Polynomial that)
{
// create a new polynomial object by using the this operator
Polynomial result = new Polynomial();
PolyNode p1, p2;
int power = this.monomialsList.degree > that.monomialsList.degree ? this.monomialsList.degree
: that.monomialsList.degree;
while (power >= 0)
{
p1 = this.monomialsList;
while (p1 != null)
{
if (p1.degree == power)
break;
p1 = p1.next;
}
p2 = that.monomialsList;
while (p2 != null)
{
if (p2.degree == power)
break;
p2 = p2.next;
}
if ((p1 != null) && (p2 != null))
result.addTerm((p1.coeff - p2.coeff), p1.degree);
else if (p1 != null)
result.addTerm(p1.coeff, p1.degree);
else if (p2 != null)
result.addTerm(p2.coeff, p2.degree);
power--;
}
return result;
}
public static void main(String[] args)
{
// create objects to the polynomial class
Polynomial poly1 = new Polynomial();
Polynomial poly2 = new Polynomial();
Polynomial poly3 = new Polynomial();
Polynomial poly4 = new Polynomial();
poly1.addTerm(5, 2);
poly1.addTerm(4, 5);
poly1.addTerm(1, 4);
poly1.addTerm(5, 6);
poly2.addTerm(3, 8);
poly2.addTerm(2, 6);
poly2.addTerm(2, 5);
poly2.addTerm(0, 3);
poly2.addTerm(1, 2);
poly3.addTerm(1, 2);
poly3.addTerm(5, 0);
poly3.addTerm(2, 1);
poly3.addTerm(4, 1);
poly3.addTerm(3, 3);
poly4.addTerm(1, 2);
poly4.addTerm(2, 1);
poly4.addTerm(5, 0);
System.out.println(" Polynomial 1 = " + poly1);
System.out.println(" Polynomial 2 = " + poly2);
System.out.println(" Polynomial 3 = " + poly3);
// call the add method of the polynomial and add the two polynomials
// and return the polynomial and store it in p3
Polynomial ployAdd = poly1.add(poly2);
System.out.println(" ply1 = " + poly1 + " poly2 = " + poly2
+ " ploy1 + poly2 = " + ployAdd);
// call the add method of the polynomial and sub the two
// polynomials and return the polynomial and store it in p3
Polynomial ploySub = poly2.subtract(poly3);
System.out.println(" poly2 = " + poly2 + " poly3 = " + poly3
+ " ploy2 - poly3 = " + ploySub);
// call the multiply method of the polynomial and sub the two
// polynomials and return the polynomial and store it in p3
Polynomial ployMul = poly1.multiply(poly3);
System.out.println(" poly1 = " + poly1 + " ploy3 = " + poly3
+ " poly1 * poly3 = " + ployMul);
Polynomial addTimes = new Polynomial();
addTimes = poly1.addTimesMonomial(poly4, 2, 2);
System.out.println(" poly1 = " + poly1 + " poly4 = " + poly4);
System.out.println("poly1 + (2x^2 *( Poly4)) = "+addTimes);
}
}
Sample Output:
Polynomial 1 = + 5x^6 + 4x^5 + 1x^4 + 5x^2
Polynomial 2 = + 3x^8 + 2x^6 + 2x^5 + 0x^3 + 1x^2
Polynomial 3 = + 3x^3 + 1x^2 + 6x + 5
ply1 = + 5x^6 + 4x^5 + 1x^4 + 5x^2
poly2 = + 3x^8 + 2x^6 + 2x^5 + 0x^3 + 1x^2
ploy1 + poly2 = + 3x^8 + 7x^6 + 6x^5 + 1x^4 + 0x^3 + 6x^2
poly2 = + 3x^8 + 2x^6 + 2x^5 + 0x^3 + 1x^2
poly3 = + 3x^3 + 1x^2 + 6x + 5
ploy2 - poly3 = + 3x^8 + 2x^6 + 2x^5 - 3x^3 + 0x^2 + 6x + 5
poly1 = + 5x^6 + 4x^5 + 1x^4 + 5x^2
ploy3 = + 3x^3 + 1x^2 + 6x + 5
poly1 * poly3 = + 15x^9 + 17x^8 + 37x^7 + 50x^6 + 41x^5 + 10x^4 + 30x^3 + 25x^2
poly1 = + 5x^6 + 4x^5 + 1x^4 + 5x^2
poly4 = + 1x^2 + 2x + 5
poly1 + (2x^2 *( Poly4)) = + 5x^6 + 4x^5 + 3x^4 + 4x^3 + 15x^2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.