Java Programming Polynomial Addition and Subtraction Write a program that adds a
ID: 3857976 • Letter: J
Question
Java Programming
Polynomial Addition and Subtraction
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. + 4X4 - 2X3 + 4X = 8X4 - X3 + 4X – 3 The three ways to implement the requirement:
1. Create and array or ArrayList of nodes, each node holding a term of the polynomial
2. Use a linked list of terms using pointers.
3. Polynomials are linked lists in one static array.
Implementations 1, 2, and 3 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. This algorithm resembles the method merge() found on page 642-643 of the text. In the fourth implementation 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 and initialized once by the first instantiation of a polynomial.
There are two challenges in the first implementation. The first is converting the polynomial string given to 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 class that I will provide. Your code must use the Demo class that I will provide. Below is the syntax for working with the interface:
public PolynomialInterface add(PolynomialInterface other)
{
ArrayWithExponentAsIndex answer = new ArrayWithExponentAsIndex ();
ArrayWithExponentAsIndex parameter = (ArrayWithExponentAsIndex)other;}
3 Here is code that can guide you in the third implementation. It creates an array of nodes and connects them into the freeStore.
public class LinkedListInArrayPolynomial implements PolynomialInterface
{
private static final int NUL = -1; private static int free;
//*** Reference to the first node on the free list
private static LLInArrayPolyNode[] nodeArray= new LLInArrayPolyNode[1000];
private static boolean nodeArrayIsInitialized = false;
private String polyString; private int polynomial = NUL;
//*** Reference to the first node on the list
public LinkedListInArrayPolynomial()
{
if(!nodeArrayIsInitialized) initializeStaticArray();
}
public LinkedListInArrayPolynomial(String polyString)
{
if(!nodeArrayIsInitialized) initializeStaticArray();
this.polyString = polyString; storePolynomial();
}
private void initializeStaticArray() {
// fill array with nodes
for(int x = 0; x < nodeArray.length; x++)
{
nodeArray[x] = new LLInArrayPolyNode();
}
for (int index = 1; index < nodeArray.length; index++)
{
nodeArray[index - 1].setNext(index);
}
nodeArray[ nodeArray.length - 1].setNext(NUL);
free = 0;
nodeArrayIsInitialized = true;
}
protected int getNode() /
/*** Returns the index of the next available node from the freeStore
//*** and updates the freeStore index
{
int hold;
hold = free;
free = nodes[free].next;
return hold;
}
Explanation / Answer
ArraySortedPolynomial.java
----------------------------------------
public class ArraySortedPolynomial implements PolynomialInterface {
public node finalAnswer [] = new node [100];
public node constructor [] = new node [100];
public node secondPoly [] = new node [100];
public node firstPoly [] = new node [100];
public int counter = 0;
public ArraySortedPolynomial(String s1)
{
String value = "";
String expo = "";
boolean isValue = true;
boolean isExpo = false;
try
{
for (int i = 0; i <= s1.length()+1; i++)
{
String num = s1.charAt(i)+"";
if ((isInteger(num)||num.equals("-")||num.equals("+"))&&(isValue))
{value = value + num;
isExpo = false;
} else if (num.equals("x")){
isExpo = true;
}else if (num.equals("^"))
{isValue = false; }
else if (isInteger(num)) {expo = expo + num;
}else if (num.equals("-")||(num.equals("+"))){
isValue = true;
isExpo = false;
constructor [counter] = new node(Integer.parseInt(value), Integer.parseInt(expo));
counter++;
value = num;
expo = "";}}}
catch(StringIndexOutOfBoundsException e) {
if (isExpo == true) {
if (expo.equals(""))
{constructor [counter] = new node (Integer.parseInt(value), 1);
counter++;}else{constructor [counter] = new node (Integer.parseInt(value), Integer.parseInt(expo)); counter++;}}else{
constructor [counter] = new node (Integer.parseInt(value), 0);
counter ++;}}counter = 0; }
public boolean isInteger(String s)
{if (s.equals("0")||s.equals("1")||s.equals("2")||s.equals("3")||s.equals("4")||s.equals("5")||
s.equals("6")||s.equals("7")||s.equals("8")||s.equals("9"))
{return true;
}elsereturn false;
}@Override
public PolynomialInterface add(PolynomialInterface other)
{
setArray(this+"", firstPoly);
setArray(other+"", secondPoly);
int num1 = 0;
int num2 = 0;
int f = 0;
int s = 0;
int d = 0;
while (true)
{try {num1 = firstPoly[f].getExpo();}
catch (NullPointerException e)
{break; }
try {num2 = secondPoly[s].getExpo();}
catch (NullPointerException e)
{break; }
if (num1 > num2)
{//add num1 to answer
//add num1 while it's greater than num2
finalAnswer[d] = firstPoly[f];
d++;
f++;}
else if (num2 > num1)
{//add num2 to answer
//add num1 while it's greater than num2
finalAnswer[d] = secondPoly[s];
s++;
d++;}
else
{//add them and add to answer
try
{if ((firstPoly[f].getValue() + secondPoly[s].getValue()) != 0)
{finalAnswer[d] = new node((firstPoly[f].getValue() + secondPoly[s].getValue()), num1);
d++;
}s++;
f++;
}catch (NullPointerException e)
{break; }}}
String a = "";
String b = "";
try
{for (int i=0; i <= finalAnswer.length-1; i++)
{String value = finalAnswer[i].getValue() + "";
if(!((value).charAt(0)+"").equals("-"))
{value = "+" + value;
}if (finalAnswer[i].getValue() != 0)
{a = value + "x^" + finalAnswer[i].getExpo();
b = b + a;
}}}
catch(NullPointerException e)
{
}clearArrays(firstPoly, secondPoly, finalAnswer);
return new ArraySortedPolynomial(b);
}
private void clearArrays(node[] firstPoly2, node[] secondPoly2, node[] finalAnswer2)
{for (int i =0; i <= firstPoly2.length-1;i++)
{try
{firstPoly2 [i].setValue(0);
firstPoly2 [i].setExpo(0);
secondPoly2 [i].setValue(0);
secondPoly2 [i].setExpo(0);
finalAnswer2 [i].setValue(0);
finalAnswer2 [i].setExpo(0);
}catch (NullPointerException e)
{
}
}
}
private void setArray(String s1, node[] array)
{
String value = "";
String expo = "";
boolean isValue = true;
boolean isExpo = false;
try
{for (int i = 0; i <= s1.length()+1; i++)
{String num = s1.charAt(i)+"";
if ((isInteger(num)||num.equals("-")||num.equals("+"))&&(isValue))
{value = value + num;
isExpo = false;
}else if (num.equals("x"))
{isExpo = true;
}else if (num.equals("^"))
{isValue = false;
}else if (isInteger(num))
{expo = expo + num;
}else if (num.equals("-")||(num.equals("+")))
{isValue = true;
isExpo = false;
array [counter] = new node(Integer.parseInt(value), Integer.parseInt(expo));
counter++;
value = num;
expo = ""; }}}
catch(StringIndexOutOfBoundsException e)
{if (isExpo == true)
{if (expo.equals(""))
{array [counter] = new node (Integer.parseInt(value), 1);
counter++;
}
else
{array [counter] = new node (Integer.parseInt(value), Integer.parseInt(expo));
counter++;
}
}
else
{array [counter] = new node (Integer.parseInt(value), 0);
counter ++;
}
}
counter = 0;
}
@Override
public PolynomialInterface subtract(PolynomialInterface other)
{
setArray(this+"", firstPoly);
setArray(other+"", secondPoly);
int num1 = 0;
int num2 = 0;
int f = 0;
int s = 0;
int d = 0;
while (true)
{
try {num1 = firstPoly[f].getExpo();}
catch (NullPointerException e)
{
break;
}
try {num2 = secondPoly[s].getExpo();}
catch (NullPointerException e)
{
break;
}
if (num1 > num2)
{
//add num1 to answer
//add num1 while it's greater than num2
finalAnswer[d] = firstPoly[f];
d++;
f++;
}
else if (num2 > num1)
{
//add num2 to answer
//add num1 while it's greater than num2
finalAnswer[d] = secondPoly[s];
s++;
d++;
}
else
{
//add them and add to answer
try
{
if ((firstPoly[f].getValue() - secondPoly[s].getValue()) != 0)
{
finalAnswer[d] = new node((firstPoly[f].getValue() - secondPoly[s].getValue()), num1);
d++;
}
s++;
f++;
}
catch (NullPointerException e)
{
break;
}
}
}
String a = "";
String b = "";
try
{
for (int i=0; i <= finalAnswer.length-1; i++)
{
String value = finalAnswer[i].getValue() + "";
if(!((value).charAt(0)+"").equals("-"))
{
value = "+" + value;
}
if (finalAnswer[i].getValue() != 0)
{
a = value + "x^" + finalAnswer[i].getExpo();
b = b + a;
}
}
}
catch(NullPointerException e)
{
}
clearArrays(firstPoly, secondPoly, finalAnswer);
return new ArraySortedPolynomial(b);
}
@Override
public void readPolynomial() {
// TODO Auto-generated method stub
}
public String toString()
{
String a = "";
String b = "";
try
{for (int i=0; i <= constructor.length-1; i++)
{String value = constructor[i].getValue() + "";
if(!((value).charAt(0)+"").equals("-"))
{value = "+" + value;
}a = value + "x^" + constructor[i].getExpo();
b = b + a;}}
catch(NullPointerException e)
{
}return b;
}
---------------------------
LinkListPolynomial.java
--------------------------
import java.util.LinkedList;
public class LinkListPolynomial implements PolynomialInterface {
private ListNode front;
private ListNode rear;
private ListNode front1;
private ListNode rear1;
private ListNode front2;
private ListNode rear2;
private ListNode frontFinal;
private ListNode rearFinal;
private int [] array = new int [100];
public LinkListPolynomial()
{
this.front = null;
this.rear = null;
}
public LinkListPolynomial(String s1)
{s1 = sort(s1);
clearArray();
String value = "";
String expo = "";
boolean isValue = true;
boolean isExpo = false;
try
{for (int i = 0; i <= s1.length()+1; i++)
{String num = s1.charAt(i)+"";
if ((isInteger(num)||num.equals("-")||num.equals("+"))&&(isValue))
{value = value + num;
isExpo = false;
}else if (num.equals("x"))
{isExpo = true;
}else if (num.equals("^"))
{isValue = false;
}
else if (isInteger(num))
{expo = expo + num;
}else if (num.equals("-")||(num.equals("+")))
{isValue = true;
isExpo = false;
//constructor [counter] = new node(Integer.parseInt(value), Integer.parseInt(expo));
addLast (Integer.parseInt(value), Integer.parseInt(expo));
value = num;
expo = "";}}}
catch(StringIndexOutOfBoundsException e)
{if (isExpo == true)
{if (expo.equals(""))
{//constructor [counter] = new node (Integer.parseInt(value), 1);
addLast (Integer.parseInt(value), 1);
}else
{//constructor [counter] = new node (Integer.parseInt(value), Integer.parseInt(expo));
addLast (Integer.parseInt(value), Integer.parseInt(expo));}}
else
{//constructor [counter] = new node (Integer.parseInt(value), 0);
addLast (Integer.parseInt(value), 0);}}}
public void clearArray()
{for (int i =0; i <= array.length-1;i++)
{array [i] = 0;
}
} public String sort (String s1)
{String value = "";
String expo = "";
boolean isValue = true;
boolean isExpo = false;
try
{
for (int i = 0; i <= s1.length()+1; i++)
{String num = s1.charAt(i)+"";
if ((isInteger(num)||num.equals("-")||num.equals("+"))&&(isValue))
{
value = value + num;
isExpo = false;
}
else if (num.equals("x"))
{
isExpo = true;
}
else if (num.equals("^"))
{
isValue = false;
}
else if (isInteger(num))
{
expo = expo + num;
}
else if (num.equals("-")||(num.equals("+")))
{
isValue = true;
isExpo = false;
array [Integer.parseInt(expo)] = Integer.parseInt(value);
value = num;
expo = "";
}
}
}
catch(StringIndexOutOfBoundsException e)
{
if (isExpo == true)
{
if (expo.equals(""))
{
array [1] = Integer.parseInt(value);
}
else
{
array [Integer.parseInt(expo)] = Integer.parseInt(value);
}
}
else
{
array [0] = Integer.parseInt(value);
}
}
String a = "";
for (int i=0; i <= array.length-1; i++)
{
String num = array[i] + "";
if (!num.equals("0"))
{
if(!((num).charAt(0)+"").equals("-"))
{
num = "+" + num;
}
a = num + "x^" + i + a;
}
}
return a;
}
public void showList()
{
ListNode position = front;
while (position != null)
{
System.out.println("Value = " + position.getCoefficient() + " Expo = " + position.getExponent());
position = position.getLink();
}
}
public void addFirst(int a, int b)
{
front = new ListNode(a, b, front);
}
public void addLast(int a, int b)
{
ListNode position = new ListNode(a, b, null);
if (rear == null)
{
front = position;
rear = front;
}
else
{
rear.setLink(position);
rear = position;
}
}
public void add1(int a, int b)
{
ListNode position = new ListNode(a, b, null);
if (rear1 == null)
{
front1 = position;
rear1 = front1;
}
else
{
rear1.setLink(position);
rear1 = position;
}
}
public void add2(int a, int b)
{
ListNode position = new ListNode(a, b, null);
if (rear2 == null)
{
front2 = position;
rear2 = front2;
}
else
{
rear2.setLink(position);
rear2 = position;
}
}
public void addFinal(int a, int b)
{
ListNode position = new ListNode(a, b, null);
if (rearFinal == null)
{
frontFinal = position;
rearFinal = frontFinal;
}
else
{
rearFinal.setLink(position);
rearFinal = position;
}
}
public boolean isInteger(String s)
{
if (s.equals("0")||s.equals("1")||s.equals("2")||s.equals("3")||s.equals("4")||s.equals("5")||
s.equals("6")||s.equals("7")||s.equals("8")||s.equals("9"))
{
return true;
}
else
return false;
}
public void setList1(String s1)
{
String value = "";
String expo = "";
boolean isValue = true;
boolean isExpo = false;
try
{
for (int i = 0; i <= s1.length()+1; i++)
{
String num = s1.charAt(i)+"";
if ((isInteger(num)||num.equals("-")||num.equals("+"))&&(isValue))
{
value = value + num;
isExpo = false;
}
else if (num.equals("x"))
{
isExpo = true;
}
else if (num.equals("^"))
{
isValue = false;
}
else if (isInteger(num))
{
expo = expo + num;
}
else if (num.equals("-")||(num.equals("+")))
{
isValue = true;
isExpo = false;
add1 (Integer.parseInt(value), Integer.parseInt(expo));
value = num;
expo = "";
}
}
}
catch(StringIndexOutOfBoundsException e)
{
if (isExpo == true)
{
if (expo.equals(""))
{
add1 (Integer.parseInt(value), 1);
}
else
{
add1 (Integer.parseInt(value), Integer.parseInt(expo));
}
}
else
{
add1 (Integer.parseInt(value), 0);
}
}
}
public void setList2(String s1)
{
String value = "";
String expo = "";
boolean isValue = true;
boolean isExpo = false;
try
{
for (int i = 0; i <= s1.length()+1; i++)
{
String num = s1.charAt(i)+"";
if ((isInteger(num)||num.equals("-")||num.equals("+"))&&(isValue))
{
value = value + num;
isExpo = false;
}
else if (num.equals("x"))
{
isExpo = true;
}
else if (num.equals("^"))
{
isValue = false;
}
else if (isInteger(num))
{
expo = expo + num;
}
else if (num.equals("-")||(num.equals("+")))
{
isValue = true;
isExpo = false;
add2 (Integer.parseInt(value), Integer.parseInt(expo));
value = num;
expo = "";
}
}
}
catch(StringIndexOutOfBoundsException e)
{
if (isExpo == true)
{
if (expo.equals(""))
{
add2 (Integer.parseInt(value), 1);
}
else
{
add2 (Integer.parseInt(value), Integer.parseInt(expo));
}
}
else
{
add2 (Integer.parseInt(value), 0);
}
}
}
public PolynomialInterface add(PolynomialInterface other)
{
setList1(this+"");
setList2(other+"");
int num1 = 0;
int num2 = 0;
while (true)
{
try {num1 = front1.getExponent();}
catch (NullPointerException e)
{
break;
}
try {num2 = front2.getExponent();}
catch (NullPointerException e)
{
break;
}
if (num1 > num2)
{
addFinal(front1.getCoefficient(), front1.getExponent());
front1 = front1.getLink();
}
else if (num2 > num1)
{
addFinal(front2.getCoefficient(), front2.getExponent());
front2 = front2.getLink();
}
else
{
try
{
if ((front1.getCoefficient() + front2.getCoefficient()) != 0)
{
addFinal((front1.getCoefficient()+front2.getCoefficient()), num1);
}
front1 = front1.getLink();
front2 = front2.getLink();
}
catch (NullPointerException e)
{
break;
}
}
}
String a = "";
try
{
ListNode position = frontFinal;
while (position != null)
{
String value = position.getCoefficient() +"";
if(!((value).charAt(0)+"").equals("-"))
{
value = "+" + value;
}
a = a + value + "x^" + position.getExponent();
position = position.getLink();
}
}
catch(NullPointerException e)
{
}
clearAll();
return new LinkListPolynomial(a);
}
public void clearAll()
{
front1 = null;
rear1 = null;
front2 = null;
rear2 = null;
frontFinal = null;
rearFinal = null;
try
{
while(true)
{
ListNode temp = front1.getLink();
front1.setLink(null);
front1 = temp;
}
}
catch (NullPointerException e){}
try
{
while(true)
{
ListNode temp = front2.getLink();
front2.setLink(null);
front2 = temp;
}
}
catch (NullPointerException e){}
try
{
while(true)
{
ListNode temp = frontFinal.getLink();
frontFinal.setLink(null);
frontFinal = temp;
}
}
catch (NullPointerException e){}
}
@Override
public PolynomialInterface subtract(PolynomialInterface other)
{
setList1(this+"");
setList2(other+"");
int num1 = 0;
int num2 = 0;
while (true)
{
try {num1 = front1.getExponent();}
catch (NullPointerException e)
{
break;
}
try {num2 = front2.getExponent();}
catch (NullPointerException e)
{
break;
}
if (num1 > num2)
{
addFinal(front1.getCoefficient(), front1.getExponent());
front1 = front1.getLink();
}
else if (num2 > num1)
{
addFinal(front2.getCoefficient(), front2.getExponent());
front2 = front2.getLink();
}
else
{
try
{
if ((front1.getCoefficient() - front2.getCoefficient()) != 0)
{
addFinal((front1.getCoefficient() - front2.getCoefficient()), num1);
}
front1 = front1.getLink();
front2 = front2.getLink();
}
catch (NullPointerException e)
{
break;
}
}
}
String a = "";
try
{
ListNode position = frontFinal;
while (position != null)
{
String value = position.getCoefficient() +"";
if(!((value).charAt(0)+"").equals("-"))
{
value = "+" + value;
}
a = a + value + "x^" + position.getExponent();
position = position.getLink();
}
}
catch(NullPointerException e)
{
}
clearAll();
return new LinkListPolynomial(a);
}
@Override
public void readPolynomial() {
// TODO Auto-generated method stub
}
public String toString()
{
ListNode position = front;
String a = "";
while (position != null)
{
String value = position.getCoefficient() +"";
if(!((value).charAt(0)+"").equals("-"))
{
value = "+" + value;
}
a = a + value + "x^" + position.getExponent();
position = position.getLink();
}
return a;
}
}
--------------------------
Listnode.java
--------------------------
public class ListNode {
private int coefficient;
private int exponent;
private ListNode link;
public int next;
public ListNode()
{
this.coefficient = 0;
this.exponent =0;
this.link = null;
this.next= 0;
}
public ListNode (int value, int expo, int next)
{
this.coefficient = value;
this.exponent = expo;
this.next = next;
}
public ListNode (int value, int expo, ListNode link)
{
this.coefficient = value;
this.exponent = expo;
this.link = link;
}
public int getNext()
{
return next;
}
public void setNext(int a)
{
next = a;
}
public ListNode getLink()
{
return link;
}
public void setLink(ListNode a)
{
link = a;
}
public int getCoefficient()
{
return coefficient;
}
public int getExponent()
{
return exponent;
}
public void setCoefficient(int n)
{
coefficient = n;
}
public void setExponent(int n)
{
exponent = n;
}
public void setInArray(int a, int b)
{
coefficient = a;
exponent = b;
}
public String toString()
{
String a = "Value= " + getCoefficient() + " Expo= " + getExponent();
return a;
}
}
------------------
node.java
------------------
public class node {
public int value = 0;
public int expo = 0;
public node()
{
value = 0;
expo = 0;
}
public node(int a, int b)
{
value = a;
expo = b;
}
public int getValue()
{
return value;
}
public int getExpo()
{
return expo;
}
public void setValue(int n)
{
value = n;
}
public void setExpo(int n)
{
expo = n;
}
}
---------------------------
PolynomialInterface.java
---------------------------
public interface PolynomialInterface {
PolynomialInterface add (PolynomialInterface other);
PolynomialInterface subtract(PolynomialInterface other);
void readPolynomial();
String toString();
}
--------------------------
PolynomialsDemo.java
--------------------------
public class PolynomialsDemo {
public static void main(String[] args) {
System.out.println();
/* THIS IS WHERE YOU TEST THE POLYNOMIALS */
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.