CSCI1913 Poly Linked List

0. Introduction.

Polynomial arithmetic is a classic application of linked data structures like the ones discussed in the lectures. In this project, you will write a Java class that represents polynomials using singly linked linear lists. Its methods will add, subtract, and print these polynomials.

1. Theory.

For the purposes of this project, a polynomial is a finite sum of zero or more terms, like this.

a_nxⁿ + a_n-1x^n-1 + a_n-2x^n-2 ... + a₂x² + a₁x¹ + a₀x⁰

Each term has a coefficient, shown as a subscripted a. It also has a variable, shown as x, with an exponent. All coefficients are nonzero integers, and all exponents are nonnegative integers. No two exponents are equal, and the terms appear in strictly decreasing order of their exponents. A polynomial with no terms is assumed to be 0. Now suppose that we have two polynomials p and q that look like this.

p = 3x³ - 2x² + 5x⁰
q = 7x⁵ + 1x³ + 2x² - 1x¹

Then their sum r can be computed in the following way.

r = p + q = 7x⁵ + (3 + 1)x³ + (−2 + 2)x² − 1x¹ + 5x⁰ = 7x⁵ + 4x³ − 1x¹ + 5x⁰

This suggests an algorithm for adding p and q, which can be written informally as follows.

1. Let r be a copy of q.
2. For each term in p, do steps 36.
3. Search for a term in r with the same exponent as the one from p.
4. If there is such a term in r, then add the coefficient of the term from p to the coefficient of the term from r.
5. If the term from step 4 has a coefficient of 0, then delete that term from r.
6. If there is no term in r with the same exponent as the one from p, then make a copy of the term from p, and add the copy to r. Keep the terms in decreasing order of their exponents.
7. Continue in this way until all terms of p have been visited. Then r is the sum of p and q.

We can also find the difference of two polynomials p and q by computing p + ( q) according to the same algorithm. The negation q is obtained by simply reversing the signs of qs coefficients.

−q = −(7x⁵ + 1x³ + 2x² − 1x¹) = −7x⁵ − 1x³ − 2x² + 1x¹

As before, this suggests an algorithm for negating q.

1. Let r be the polynomial 0, with no terms.
2. For each term in q, do step 3.
3. Make a copy of the term from q, but change the sign of its coefficient. Add the copied term to r. Keep the terms in decreasing order of their exponents.
4. Continue in this way until all terms of q have been visited. Then r is the negation of q.

Algorithms like these may be implemented using singly linked linear lists with head nodes, as described in the next section.

2. Implementation.

You must implement a Java class called Poly . Each instance of Poly represents a polynomial in x, as in the previous section. The class Poly must look like this, with your code in place of the three dots.

class Poly
{
⋮
}

To simplify grading, you must use the same names for classes and methods that are shown here. The class Poly must have a private nested class called Term , whose instances represent the terms of the polynomial. The class Term must have three slots: an int slot called coef , an int slot called expo , and a Term slot called next . As these names suggest, coef is the terms coefficient, expo is the terms exponent, and next points to the next Term in a linked list (or to null ). Along with Term , the class Poly must have the following methods.

public Poly()

This constructor makes a new polynomial with no Term s. It must initialize a private variable called head that points to the head node in a singly linked list of Term s. This list must be empty.

public Poly term(int coef, int expo)

The method term adds a new Term to this . The new Term s coefficient is coef and its exponent is expo .

If expo is negative, then throw an IllegalArgumentException . Otherwise, visit each Term in this . If you visit a Term whose expo slot is less than the parameter expo , then add the new Term immediately before that Term , and stop visiting Term s. If you visit a Term whose expo slot is greater than the parameter expo , then skip that Term and go on to the next one. If you visit a Term whose expo slot equals the parameter expo , then throw an IllegalArgumentException . If youve visited all the Term s, but didnt add a new Term , then add the new Term at the end of the list. Finally, return this so that more Term s can be added later (see the example at the end of this description).

public Poly plus(Poly that)

The method plus returns a new polynomial that is the sum of this and that .

First, make a new polynomial with no Term s. Then visit each Term in this . Each time you visit a Term , add it to the new polynomial by calling term . After all the Term s have been visited, the new polynomial will be a copy of this . Next, visit each Term in the polynomial that. Each time you visit a Term , add it to the new polynomial by calling add . After all the Term s have been visited, return the new polynomial.

private void add(int coef, int expo)

The method add may add a Term to this , it may change a Term in this , or it may delete a Term from this .

If expo is negative, then throw an IllegalArgumentException . Otherwise, visit each Term in this . If you visit a Term whose expo slot is less than the parameter expo , then add a new Term immediately before that Term , and return. The new Term s coef slot is the parameter coef , and its expo slot is the parameter expo . If you visit a Term whose expo slot is greater than the parameter expo , then skip that Term and go on to the next one. If you visit a Term whose expo slot equals the parameter expo , then add the parameter coef to that Term s coef slot. If the coef slot becomes 0 as a result, then delete that Term and return.

public Poly minus()

The method minus returns a new polynomial like this , but with Term s whose coef slots have the opposite signs.

First, make a new polynomial with no Term s. Then visit each Term in this . Each time you visit a Term , add a new Term to the new polynomial by calling term . The new Term has the same expo slot as the Term youre visiting, but its coef slot has the opposite sign. After youve visited all the terms, return the new polynomial.

public String toString()

The method toString returns a String for printing this . The String must be constructed using a StringBuilder.

If this has no Term s, then return the String "0" . Otherwise, visit each Term in this , and construct a String from the coef and expo slots of the visited terms. See the example to find out what the String must look like. Finally, return the String .

Here are some comments, hints, and warnings.

• All these methods keep lists of Term s in decreasing order of their expo slots. They never make two Term s with the same expo slots. They also delete Term s whose coef slots are 0. You will lose points if your program doesnt do all these things.
• The methods use head nodes to avoid special cases. The head node ensures that each important Term has a predecessor, which makes adding and deleting Term s easier. You will lose points if your program doesnt use head nodes correctly.
• If you use the left-right trick as discussed in the lectures, then your program will be easier to write.
• If k is an int , then write k to negate it. Dont write 1 k . The first way is faster and simpler than the second.
• Write the methods term and toString first. Make sure they work correctly. They will help you debug your other methods.
• An earlier lecture discussed a toString method for Sequence s. You can use ideas from that method when you write the toString method for Poly . Specifically, your toString method may be easier to write if you treat the first Term in a list differently from the others.
• If you wish, your toString method can show exponents using superscript Unicode digits. For example, it can show a Term whose coef slot is 2 and whose expo slot as 2x . The private method appendExponent makes this easy. It takes a StringBuilder and an int as its arguments, turns the int into superscript digits, and appends them to the StringBuilder . For example, appendExponent(builder, 12) appends to builder . If you dont want to do this, or if your computer doesnt support Unicode, then you can show exponents using boring old ASCII digits instead, like 2x12

3. Example.

You must also write a driver class, with a main method, along with the class Poly . Its worth no points, but you wont be able to debug your program without it. The following is a possible driver class. The comments show what each call to println should print, assuming that toString uses superscript digits as described above.

class PollyEsther
{
public static void main(String[] args)
{
Poly p0 = new Poly();
Poly p1 = new Poly().term(1, 3).term(1, 1).term(1, 2);
Poly p2 = new Poly().term(2, 1).term(3, 2);
Poly p3 = p2.minus();
System.out.println(p0); // 0
System.out.println(p1); // 1x³ + 1x² + 1x¹
System.out.println(p2); // 3x² + 2x¹
System.out.println(p3); // −3x2 − 2x¹
System.out.println(p1.plus(p2)); // 1x³ + 4x² + 3x¹
System.out.println(p1.plus(p3)); // 1x³ − 2x² − 1x¹
}
}

This is not a complete set of tests. It may not be sufficient to find all the bugs in your Poly class. To be safe, you should write your own tests.