class Literal
{
int content;
int exponent;
Literal next;
Literal() //three constructor methods
{
this(null);
}
Literal(Literal n)
{
this(0,0,n);
}
Literal(int c,int e)
{
this(c,e,null);
}
Literal(int c,int e,Literal n)
{
content = c;
exponent = e;
next = n;
}
public String toString() //print strings such as "5X(100)"
{
if(content >0)
return Integer.toString(content)+"X["+Integer.toString(exponent)+"]";
else if(content == 0)
return "";
else return "("+Integer.toString(content)+")X["+Integer.toString(exponent)+"]";
}
}
class LinkedListItr
{
Literal current;
LinkedListItr(Literal theNode)
{
current = theNode;
}
public int content()
{
return current.content;
}
public int exponent()
{
return current.exponent;
}
public boolean isPastEnd()
{
return current == null;
}
public void advance()
{
if(!isPastEnd())
current=current.next;
}
}
public class Polynomial
{
private Literal header=new Literal();
public boolean isEmpty() //about empty
{
return header.next == null;
}
public void makeEmpty()
{
header.next = null;
}
public LinkedListItr zeroth() //0th
{
return new LinkedListItr(header);
}
public LinkedListItr first() //1st
{
return new LinkedListItr(header.next);
}
public void insert(Literal x,LinkedListItr itr) //insert
{
if(itr != null && itr.current != null)
{
x.next = itr.current.next;
itr.current.next = x;
}
}
public void insertAtEnd(Literal x) //insert a literal at end
{
LinkedListItr pointer=zeroth();
while(pointer.current.next != null)
pointer.advance();
insert(x,pointer);
}
public void printList() //print list
{
if(isEmpty())
System.out.println("Empty polynomial.");
else
{
LinkedListItr itr = first();
while(!itr.isPastEnd())
{
System.out.print(itr.current.toString());
itr.advance();
if(!itr.isPastEnd()) //draw such as 5X(100)"+"3X(98)
System.out.print(" + ");
}
}
System.out.println();
}
public static Polynomial addTwoPolys(Polynomial poly1,Polynomial poly2) //the add polynomial method
{
Polynomial poly3 = new Polynomial();
LinkedListItr pointer1 = poly1.zeroth();
LinkedListItr pointer2 = poly2.zeroth();
LinkedListItr pointer3 = poly3.zeroth();
/************ test whether polynomial is empty ************/
if(poly1.isEmpty() && poly2.isEmpty())
System.out.println("Error:both the added polynomials are empty.");
else if(poly1.isEmpty())
return poly2;
else if(poly2.isEmpty())
return poly1;
/************************** else **************************/
else
{
for(;;)
{
if(pointer1.isPastEnd() && pointer2.isPastEnd())
break; //finish
else if(pointer1.isPastEnd())
{
pointer3.current.next = pointer2.current;
pointer3.advance();
pointer2.advance();
}
else if(pointer2.isPastEnd())
{
pointer3.current.next = pointer1.current;
pointer3.advance();
pointer1.advance();
}
else //compare the exponent values
{
if(pointer1.exponent() > pointer2.exponent())
{
pointer3.current.next = pointer1.current;
pointer3.advance();
pointer1.advance();
}
else if(pointer1.exponent() < pointer2.exponent())
{
pointer3.current.next = pointer2.current;
pointer3.advance();
pointer2.advance();
}
else //exponents are equal
{
if((pointer1.content() + pointer2.content()) == 0) //the special case
{
pointer1.advance();
pointer2.advance();
}
else
{
int newContent = pointer1.content()+pointer2.content();
pointer3.current.next = new Literal(newContent,pointer1.exponent(),null);
pointer3.advance();
pointer2.advance();
pointer1.advance();
}
}
}
}
return poly3;
}
return poly3; //because not void,return a value again
}
}
public class TheDriver
{
public static void main(String[] args)
{
Polynomial poly1=new Polynomial();
Polynomial poly2=new Polynomial();
Polynomial poly3=new Polynomial();
//assume poly1 has 4 elements and poly 2 has 3 elements
/******** assignment ********/
int exponent=100;
for(int i=0;i<4;i++)
{
poly1.insertAtEnd(new Literal(10-i,exponent,null));
exponent--;
}
poly2.insertAtEnd(new Literal(-10,100,null));
poly2.insertAtEnd(new Literal(-5,98));
poly2.insertAtEnd(new Literal(5,50));
System.out.println("Attention : [**] means the exponent is **.\n\n");
//print the polynomials
System.out.print("The polynomial(1) is : ");
poly1.printList();
System.out.print("\nThe polynomial(2) is : ");
poly2.printList();
poly3=Polynomial.addTwoPolys(poly1,poly2);
System.out.print("\nThe adding result is : ");
poly3.printList();
System.out.println();
}
}
