\"The ArrayList Class\" The Term Class Create a class to represent a term in an
ID: 3776414 • Letter: #
Question
"The ArrayList Class"
The Term Class
Create a class to represent a term in an algebraic expression. As defined here, a term consists of an integer coefficient and a nonnegative integer exponent. E.g.
in the term 4x2, the coefficient is 4 and the exponent 2
in -6x8, the coefficient is -6 and the exponent 8
Your Term class will have a constructor that creates a Term object with a coefficient and exponent passed as parameters, accessor methods that return the coefficient and the exponent. Your class will also have a toString() method that returns a Term object as a String, formatted as shown in these examples:
Coefficient Exponent returns
5 3 5x^3
8 1 8x
4 0 4
The Polynomial Class
Now create a class to represent a polynomial. As defined here, a polynomial is a sequence of terms. E.g.
1. 3x^2 + 4x^4 x^6
2. 2 + 5x^2 + 6x^3 + 2x^7
3. 4x^10
The terms of polynomial 1 are (3,2), (4,4) and (1,6). The terms of polynomial 2 are (2,0), (5,2), (6,3) and (2,7). Polynomial 3 has only one term (4,10)
To receive credit for this assignment, your class must use a generic “ArrayList of Term” to store the terms of a Polynomial object
Your class will have a constructor that creates an empty list and additional methods to do each of the following:
insert a new term in its proper place in a polynomial (see “Additional Specifications,” below)
return all the terms of a polynomial as a single line string, as shown here:
3x^2 + 4x^4 + x^6
Hint: for each Term in the Polynomial, call the toString() method of the Term class and concatenate
delete a term from a polynomial (see “Additional Specifications,” below)
compute and return the product of all the terms of a polynomial
reverse the order of the terms in a polynomial (see “Additional Specifications,” below)
The Test Class
The main method of your test class will create a Polynomial object and then read and process a series of operations until end of file.
The operations are:
1. INSERT X Y
Insert a new term with coefficient X and exponent Y into its proper place in the polynomial
2. DELETE X Y
Remove the term with coefficient X and exponent Y from the polynomial
3. REVERSE
Reverse the order of the terms of the polynomial
4. PRODUCT
Compute and return the product of all the terms
Each operation is to be carried out by calling a method of the Polynomial class
Each operation read must be “echo printed” to the screen
After each operation, print the updated polynomial by calling the toString() method
For the PRODUCT operation, print the string returned
Additional Specifications
All instance variables must be private
The skeleton of the Polynomial class you are to use is online. No credit will be given if the method declarations are changed in any way
The operations are to be read from a data file which I will provide
You may assume correct input
Also assume that no insertions will be made into a reversed polynomial. (But you might want to think about how this could be accomplished)
Regarding the delete() method: if the specified term does not occur in the polynomial then print an appropriate message
Regarding the reverse() method: you must write your own algorithm to reverse the order of the elements of an ArrayList. No credit will be given for calling the reverse method of Java’s Collections class or any other method. No credit will be given for merely printing the terms in reverse order.
(Hint: You may want to use a temporary ArrayList to create the reversed list)
Regarding the insert() method: The terms of a polynomial are to be inserted in ascending order by exponent. There will never be a need to “sort” the list. Multiple terms with the same exponent may appear in any order, but will appear after all terms with a lesser exponent and before all terms with a greater exponent
An algorithm to insert a term in its proper place in an ordered list will be discussed in class
For maximum credit, make sure your classes adhere to all the style and documentation standards presented in Unit 6 and discussed in class. (Note that the Javadoc comments for the Polynomial class have already been done)
https://users.cs.fiu.edu/~crahn/COP2210/Content/Unit8/Polynomial.java = polynomial skeleton
https://users.cs.fiu.edu/~crahn/COP2210/Content/Unit8/operations.txt = input file
Explanation / Answer
import java.util.ArrayList;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
import java.text.DecimalFormat;
public class Polynomial extends ArrayList<Integer> {
public boolean debug = true;
public Polynomial() {
super(1);
this.add(0,0);
}
public int getDegree() { return this.size() - 1; }
public Polynomial(int [] coeffs) {
super(coeffs.length);
for (int i=0;i<coeffs.length;i++) {
this.add(0,coeffs[i]);
}
}
public String toString() {
String result = "";
DecimalFormat df = new DecimalFormat("#");
if (this.getDegree() == 0) {
return df.format(this.get(0));
}
int firstTerm = (this.get(this.getDegree()));
if (firstTerm < 0) {
result += "-";
}
if (Math.abs(firstTerm) != 1) {
result += df.format(Math.abs(firstTerm));
}
result +="x";
if (this.getDegree() > 1) {
result += "^" + this.getDegree();
}
for (int i=this.getDegree() - 1; i>=0; i--) {
if (this.get(i)==0) {
continue;
}
result += (this.get(i) < 0) ? " - " : " + ";
if (Math.abs(this.get(i))!=1) {
result += df.format(Math.abs(this.get(i)));
}
if (i>=2) {
result += "x" + "^" + i;
} else if (i==1) {
result += "x";
}; // else i==0 and we do nothing. :-)
}
return result;
}
public Polynomial(String s) {
super(1);
if (debug) {System.out.println("In Polynomial(String s), s=" + s);}
Pattern integerConstantPattern =
Pattern.compile("^-?\d+$");
Matcher integerConstantMatcher = integerConstantPattern.matcher(s);
if (integerConstantMatcher.matches()) {
this.add(0,Integer.parseInt(s));
return; // we are done!
}
Pattern degreeOnePattern =
Pattern.compile("^(-?)(\d*)x( ([+-]) (\d+))?$");
Matcher degreeOneMatcher = degreeOnePattern.matcher(s);
if (degreeOneMatcher.matches()) {
int xCoeff = 1;
int constantTerm = 0;
String xCoeffSign = degreeOneMatcher.group(1);
String xCoeffString = degreeOneMatcher.group(2);
String constantTermSign = degreeOneMatcher.group(4);
String constantTermString = degreeOneMatcher.group(5);
if (xCoeffString != null && !xCoeffString.equals("")) {
xCoeff = Integer.parseInt(xCoeffString);
}
if (xCoeffSign != null && xCoeffSign.equals("-")) {
xCoeff *= -1;
}
if (constantTermString != null && !constantTermString.equals("")) {
constantTerm = Integer.parseInt(constantTermString);
}
if (constantTermSign != null && constantTermSign.equals("-")) {
constantTerm *= -1;
}
this.add(0,constantTerm);
this.add(1,xCoeff);
return;
}
String twoOrMoreRe =
"^" // start of the string
+ "([-]?)(\d*)x\^(\d+)" // first x^d term, groups 1,2,3
+ "(( [+-] \d*x\^\d+)*)" // zero or more x^k terms group 4 (and 5)
+ "( [+-] \d*x)?" // optional x term (group 6)
+ "( [+-] \d+)?" // optional constant term (group 7)
+ "$"; // the end of the string
Pattern degreeTwoOrMorePattern = Pattern.compile(twoOrMoreRe);
Matcher degreeTwoOrMoreMatcher = degreeTwoOrMorePattern.matcher(s);
if (degreeTwoOrMoreMatcher.matches()) {
int firstCoeff = 1;
String startSign = degreeTwoOrMoreMatcher.group(1);
String coeffString = degreeTwoOrMoreMatcher.group(2);
String degreeString = degreeTwoOrMoreMatcher.group(3);
String middleXtoTheTerms = degreeTwoOrMoreMatcher.group(4);
String optionalXTermPart = degreeTwoOrMoreMatcher.group(6);
String optionalConstantTermPart = degreeTwoOrMoreMatcher.group(7);
if (coeffString != null && !coeffString.equals("")) {
firstCoeff = Integer.parseInt(coeffString);
}
if (startSign != null && startSign.equals("-")) {
firstCoeff *= -1;
}
int degree = Integer.parseInt(degreeString);
this.ensureCapacity(degree+1); // method of ArrayList<Integer>
for(int i=0; i<=degree; i++) // initialize all to zero
this.add(0,0);
this.set(degree,firstCoeff);
if (middleXtoTheTerms!=null && !middleXtoTheTerms.equals("")) {
Pattern addlXtoThePowerTermPattern =
Pattern.compile(" ([+-]) (\d+)(x\^)(\d+)");
Matcher addlXtoThePowerTermMatcher
= addlXtoThePowerTermPattern.matcher(middleXtoTheTerms);
while (addlXtoThePowerTermMatcher.find()) {
int coeff = 1;
String sign = addlXtoThePowerTermMatcher.group(1);
String nextCoeffString = addlXtoThePowerTermMatcher.group(2);
String nextDegreeString = addlXtoThePowerTermMatcher.group(4);
if (nextCoeffString != null && !nextCoeffString.equals("")) {
coeff = Integer.parseInt(nextCoeffString);
}
if (sign != null && sign.equals("-")) {
coeff *= -1;
}
this.set(Integer.parseInt(nextDegreeString),coeff);
}
}
if (optionalXTermPart != null && !optionalXTermPart.equals("")) {
if (debug) {System.out.println("optionalXTermPart=" +
optionalXTermPart);}
Pattern optXTermPattern =
Pattern.compile("^ ([+-]) (\d*)x$");
Matcher optXTermMatcher = optXTermPattern.matcher(optionalXTermPart);
optXTermMatcher.find();
int xCoeff = 1;
int constantTerm = 0;
String xCoeffSign = optXTermMatcher.group(1);
String xCoeffString = optXTermMatcher.group(2);
if (xCoeffString != null && !xCoeffString.equals("")) {
xCoeff = Integer.parseInt(xCoeffString);
}
if (xCoeffSign != null && xCoeffSign.equals("-")) {
xCoeff *= -1;
}
this.set(1,xCoeff);
}
if (optionalConstantTermPart != null
&& !optionalConstantTermPart.equals("")) {
Pattern constantTermPattern =
Pattern.compile("^ ([+-]) (\d+)$");
Matcher constantTermMatcher
= constantTermPattern.matcher(optionalConstantTermPart);
constantTermMatcher.find();
int constant = 0;
String sign = constantTermMatcher.group(1);
String constantString = constantTermMatcher.group(2);
if (constantString != null && !constantString.equals("")) {
constant = Integer.parseInt(constantString);
}
if (sign!=null && sign.equals("-")) {
constant *= -1;
}
this.set(0,constant);
}
return;
}
if (debug) {System.out.println("at bottom");}
throw new IllegalArgumentException("Bad Polynomial String: [" + s + "]");
}
public boolean equals(Object o) {
if (o == null)
return false;
if (!(o instanceof Polynomial))
return false;
Polynomial p = (Polynomial) o;
if (this.size() != p.size())
return false;
for (int i=0; i<this.size(); i++) {
if ( this.get(i)!= p.get(i))
return false;
}
return true;
}
private int indexHighestNonZeroTerm(int [] coeffs) {
for (int i=coeffs.length - 1; i>=0; i--) {
if (coeffs[i]!=0) {
return i;
}
}
return 0;
}
private int [] findHighestNonZeroAndInvert(int [] coeffs) {
int highestNonZeroTerm = indexHighestNonZeroTerm(coeffs);
int [] finalCoeffs = new int [highestNonZeroTerm+1];
int j=0;
for (int i=highestNonZeroTerm; i>= 0; i--) {
finalCoeffs[i] = coeffs[j];
j++;
}
return finalCoeffs;
}
public Polynomial plus (Polynomial p) {
int thisDegree = this.getDegree();
int thatDegree = p.getDegree();
int numCoeffs =
(thisDegree > thatDegree)? thisDegree + 1 : thatDegree + 1;
int [] coeffs = new int[numCoeffs];
for (int i=0; i< numCoeffs ; i++) {
coeffs[i] = 0;
}
for (int i=0; i<= thisDegree;i++) {
coeffs[i] += this.get(i);
}
for (int i=0; i<= thatDegree; i++) {
coeffs[i] += p.get(i);
}
int [] finalCoeffs = findHighestNonZeroAndInvert(coeffs);
return new Polynomial (finalCoeffs);
}
public Polynomial times (Polynomial p) {
int newDegree = this.getDegree() + p.getDegree();
int [] newCoeffs = new int[newDegree+1];
for (int i=0; i<newCoeffs.length; i++)
newCoeffs[i] = 0;
for (int i=this.getDegree(); i>=0; i--) {
int thisCoeff = this.get(i);
for (int j=p.getDegree(); j>=0; j--) {
int thisTermPower = i+j;
newCoeffs[thisTermPower] += thisCoeff * p.get(j);
}
}
int [] finalCoeffs = findHighestNonZeroAndInvert(newCoeffs);
return new Polynomial (finalCoeffs);
}
public Polynomial minus (Polynomial p) {
Polynomial minusOne = new Polynomial(new int[] {-1});
Polynomial negP = p.times(minusOne);
return this.plus(negP);
}
public static void main (String [] args) {
if (args.length != 1) {
System.err.println("Usage: java Polynomial 'string'");
}
Polynomial p = new Polynomial(args[0]);
System.out.println("p=" + p);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.