Implement a MyPolynomial class that represents single-variable polynomials (with
ID: 670539 • Letter: I
Question
Implement a MyPolynomial class that represents single-variable polynomials (with nonnegative exponents) by using a CIRCULAR doubly linked list. Each term in the polynomial can be stored in one node containing its coefficient and exponent. The nodes are sorted in decreasing order of exponents. For example,
a polynomial P (x)=10x^100 +5x ^ 14 +1 can be represented by the linked list shown in the figure below.
You are NOT allowed to use Java’s LinkedList class. The KWLinkedList.java posted on our
webpage is NOT circular, hence you can NOT use that class directly either. You are REQUIRED to
implement your own circular doubly linked list.
In addition to the appropriate constructors, include the following methods in MyPolynomial:
• public int degree(): returns the degree of the polynomial.
• public String toString() : returns a String representation in the form of 10x^100 +5x ^ 14 +1
• public MyPolynomial(MyPolynomial) : the copy constructor.
• public int getCoef(int exp): returns the coefficient corresponding to the given exponent.
• public void setCoef(int coef, int exp): sets the coefficient of the given exponent. If the term
with the given exponent does not exist, it should be added to the polynomial (if coef!= 0).
• public boolean equals(MyPolynomial)
• public MyPolynomial add(MyPolynomial): adds this polynomial and the parameter polynomial,
returns the resulting polynomial.
• public MyPolynomial subtract(MyPolynomial)
• public MyPolynomial multiply( MyPolynomial)
• public int evaluate(int x): evaluates the polynomial by plugging in the given value for x, and
returns the result.
Write a driver program that tests your class. Do not change the signatures of the methods, I will
test with my own driver.
Explanation / Answer
Program:
Node.java:
import java.util.*;
import java.io.*;
import java.text.*;
public class Node
{
protected int data;
protected Node next, prev;
/* Constructor */
public Node()
{
next = null;
prev = null;
data = 0;
}
/* Constructor */
public Node(int d, Node n, Node p)
{
data = d;
next = n;
prev = p;
}
/* Function to set link to next node */
public void setLinkNext(Node n)
{
next = n;
}
/* Function to set link to previous node */
public void setLinkPrev(Node p)
{
prev = p;
}
/* Function to get link to next node */
public Node getLinkNext()
{
return next;
}
/* Function to get link to previous node */
public Node getLinkPrev()
{
return prev;
}
/* Function to set data to node */
public void setData(int d)
{
data = d;
}
/* Function to get data from node */
public int getData()
{
return data;
}
}
/* Class linkedList */
class linkedList
{
protected Node start;
protected Node end ;
public int size;
/* Constructor */
public linkedList()
{
start = null;
end = null;
size = 0;
}
/* Function to check if list is empty */
public boolean isEmpty()
{
return start == null;
}
/* Function to get size of list */
public int getSize()
{
return size;
}
/* Function to insert element at beginning */
public void insertAtStart(int val)
{
Node nptr = new Node(val, null, null);
if (start == null)
{
nptr.setLinkNext(nptr);
nptr.setLinkPrev(nptr);
start = nptr;
end = start;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
start = nptr;
}
size++ ;
}
/*Function to insert element at end */
public void insertAtEnd(int val)
{
Node nptr = new Node(val, null, null);
if (start == null)
{
nptr.setLinkNext(nptr);
nptr.setLinkPrev(nptr);
start = nptr;
end = start;
}
else
{
nptr.setLinkPrev(end);
end.setLinkNext(nptr);
start.setLinkPrev(nptr);
nptr.setLinkNext(start);
end = nptr;
}
size++;
}
/* Function to insert element at position */
public void insertAtPos(int val , int pos)
{
Node nptr = new Node(val, null, null);
if (pos == 1)
{
insertAtStart(val);
return;
}
Node ptr = start;
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node tmp = ptr.getLinkNext();
ptr.setLinkNext(nptr);
nptr.setLinkPrev(ptr);
nptr.setLinkNext(tmp);
tmp.setLinkPrev(nptr);
}
ptr = ptr.getLinkNext();
}
size++ ;
}
/* Function to delete node at position */
public void deleteAtPos(int pos)
{
if (pos == 1)
{
if (size == 1)
{
start = null;
end = null;
size = 0;
return;
}
start = start.getLinkNext();
start.setLinkPrev(end);
end.setLinkNext(start);
size--;
return ;
}
if (pos == size)
{
end = end.getLinkPrev();
end.setLinkNext(start);
start.setLinkPrev(end);
size-- ;
}
Node ptr = start.getLinkNext();
for (int i = 2; i <= size; i++)
{
if (i == pos)
{
Node p = ptr.getLinkPrev();
Node n = ptr.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size-- ;
return;
}
ptr = ptr.getLinkNext();
}
}
/* Function to display status of list */
public void display()
{
System.out.print(" Circular Doubly Linked List = ");
Node ptr = start;
if (size == 0)
{
System.out.print("empty ");
return;
}
if (start.getLinkNext() == start)
{
System.out.print(start.getData()+ " <-> "+ptr.getData()+ " ");
return;
}
System.out.print(start.getData()+ " <-> ");
ptr = start.getLinkNext();
while (ptr.getLinkNext() != start)
{
System.out.print(ptr.getData()+ " <-> ");
ptr = ptr.getLinkNext();
}
System.out.print(ptr.getData()+ " <-> ");
ptr = ptr.getLinkNext();
System.out.print(ptr.getData()+ " ");
}
}
PolynomialLinkedList.java:
import java.text.DecimalFormat;
class PolynomialLinkedList extends Node {
private Monomial head;
private double TOLERANCE = 0.00000001;
private class Monomial {
private DecimalFormat precision = new DecimalFormat("#.####");
private int exp;
private double coeff;
private Monomial next;
public Monomial(int exp, double coeff, Monomial next) {
this.exp = exp;
this.coeff = coeff;
this.next = next;
}
public String toString() {
String form = precision.format(Math.abs(coeff));
if (exp == 0)
return form;
else if (exp == 1)
return form + "*x";
else
return form + "*x^" + exp;
}
public boolean equals(Monomial mono) {
return exp == mono.exp && coeff == mono.coeff;
}
public void setCoeff(double coeff)
{
this.coeff = coeff;
}
public double getCoeff()
{
return coeff;
}
}
public PolynomialLinkedList() {
head = null;
}
/**
* Adds a new term into the polynomial, assuming that the polynomial is
* sorted in order from smallest to largest exponent.
*/
public void addTerm(int exp, double coeff) {
if (Math.abs(coeff) < TOLERANCE)
return;
if (head == null || exp < head.exp) {
head = new Monomial(exp, coeff, head);
return;
}
Monomial cur = head;
Monomial prev = null;
while (cur != null && exp > cur.exp) {
prev = cur;
cur = cur.next;
}
if (cur == null || exp != cur.exp)
prev.next = new Monomial(exp, coeff, cur);
else {
cur.coeff += coeff;
if (Math.abs(cur.coeff) < TOLERANCE)
if (prev != null)
prev.next = cur.next;
else
head = head.next;
}
}
public String toString() {
StringBuffer sb = new StringBuffer();
for (Monomial tmp = head; tmp != null; tmp = tmp.next)
if (tmp.coeff < 0)
sb.append(" - " + tmp.toString());
else
sb.append(" + " + tmp.toString());
return sb.toString();
}
/**
* Adds two polynomials The method does not change the original polynomial.
*/
public PolynomialLinkedList add(PolynomialLinkedList poly) {
PolynomialLinkedList res = (PolynomialLinkedList) clone();
for (Monomial tmp = null; tmp != poly.head; tmp = tmp.next)
res.addTerm(tmp.exp, tmp.coeff);
return res;
}
public Object clone() {
PolynomialLinkedList res = new PolynomialLinkedList();
for (Monomial tmp = head; tmp != null; tmp = tmp.next)
res.addTerm(tmp.exp, tmp.coeff);
return res;
}
public boolean equals(PolynomialLinkedList poly) {
Monomial tmp1 = head;
Monomial tmp2 = poly.head;
while (tmp1 != null && tmp2 != null) {
if (!tmp1.equals(tmp2))
return false;
tmp1 = tmp1.next;
tmp2 = tmp2.next;
}
return true;
}
/**
* Multiplies by a number The method does not change the original
* polynomial.
*/
public PolynomialLinkedList multiply(double num) {
PolynomialLinkedList res = (PolynomialLinkedList) clone();
for (Monomial tmp = res.head; tmp != null; tmp = tmp.next)
tmp.coeff *= num;
return res;
}
/**
* Returns a new polynomial that is the derivative of this polynomial.
*/
public PolynomialLinkedList diff() {
PolynomialLinkedList res = new PolynomialLinkedList();
for (Monomial tmp = head; tmp != null; tmp = tmp.next) {
if (tmp.exp != 0)
res.addTerm(tmp.exp - 1, tmp.coeff * tmp.exp);
}
return res;
}
/**
* Computes the polynomial at x = value
*/
public double eval(double value) {
double res = 0;
for (Monomial tmp = head; tmp != null; tmp = tmp.next) {
res += tmp.coeff * Math.pow(value, tmp.exp);
}
return res;
}
public static void main(String[] args)
{
PolynomialLinkedList first = new PolynomialLinkedList();
PolynomialLinkedList second = new PolynomialLinkedList();
System.out.println( "first" );
first.addTerm(1, 2.1);
first.addTerm(4, 2);
first.addTerm(3, 1);
first.addTerm(0, 1.3);
first.addTerm(4, 0.3);
System.out.println( first );
System.out.println( );
System.out.println( "second" );
second.addTerm(4, -2.3);
second.addTerm(2, 1);
second.addTerm(0, -1.3);
second.addTerm(1, 0.3);
System.out.println( second );
System.out.println( );
System.out.println( "compare first with second" );
System.out.println( first.equals(second) );
System.out.println( "compare first wih first" );
System.out.println( first.equals(first) );
System.out.println( );
System.out.println( "add first and second" );
PolynomialLinkedList third = first.add(second);
System.out.println( third );
System.out.println( first );
System.out.println( second );
System.out.println( );
System.out.println( "multiply first by 0.2" );
PolynomialLinkedList fourth = first.multiply(0.2);
System.out.println( fourth );
System.out.println( first );
System.out.println( );
System.out.println( "differentiate first" );
PolynomialLinkedList diff = first.diff();
System.out.println( diff );
System.out.println( first );
System.out.println( );
System.out.println( "eval first at x = 1.5" );
System.out.println( first.eval(1.5) );
System.out.println( );
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.