Polynomial Addition and Subtraction Write a program that adds and subtracts two
ID: 3857933 • Letter: P
Question
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
Using Linked List:
#include<conio.h>
#include<ostream.h>
#include<process.h>
// Creating a NODE Structure
struct node
{
int coe,exp; // data
struct node *next; // link to next node and previous node
};
// Creating a class Polynomial
class polynomial
{
struct node *start,*ptrn,*ptrp;
public:
void get_poly(); // to get a polynomial
void show(); // show
void add(polynomial p1,polynomial p2); // Add two polynomials
void subtract(polynomial p1,polynomial p2); //Subtract2 polynomials
};
void polynomial::get_poly() // Get Polynomial
{
char c='y';
ptrn=ptrp=start=NULL;
while(c=='y' || c=='Y')
{
ptrn=new node;
ptrp->next=ptrn;
if(start==NULL)
start=ptrn;
ptrp=ptrn;
cout<<" Enter the coefficient: ";
cin>>ptrn->coe;
cout<<"Enter the exponent: ";
cin>>ptrn->exp;
ptrn->next=NULL;
cout<<"Enter y to add more nodes: ";
cin>>c;
}
return;
}
void polynomial::show() // Show Polynomial
{
struct node *ptr;
ptr=start;
while(ptr!=NULL)
{
cout<<ptr->coe<<"X^"<<ptr->exp<<" + ";
ptr=ptr->next;
}
cout<<" ";
}
void polynomial::add(polynomial p1,polynomial p2) // Add Polynomials
{
struct node *p1ptr,*p2ptr;
int coe,exp;
ptrn=ptrp=start=NULL;
p1ptr=p1.start;
p2ptr=p2.start;
while(p1ptr!=NULL && p2ptr!=NULL)
{
if(p1ptr->exp==p2ptr->exp) // If coefficients are equal
{
coe=p1ptr->coe+p2ptr->coe;
exp=p1ptr->exp;
p1ptr=p1ptr->next;
p2ptr=p2ptr->next;
}
else if(p1ptr->exp>p2ptr->exp)
{
coe=p1ptr->coe;
exp=p1ptr->exp;
p1ptr=p1ptr->next;
}
else if(p1ptr->exp<p2ptr->exp)
{
coe=p2ptr->coe;
exp=p2ptr->exp;
p2ptr=p2ptr->next;
}
ptrn=new node;
if(start==NULL)
start=ptrn;
ptrn->coe=coe;
ptrn->exp=exp;
ptrn->next=NULL;
ptrp->next=ptrn;
ptrp=ptrn;
} // End of While
if(p1ptr==NULL)
{
while(p2ptr!=NULL)
{
coe=p2ptr->coe;
exp=p2ptr->exp;
p2ptr=p2ptr->next;
ptrn=new node;
if(start==NULL)
start=ptrn;
ptrn->coe=coe;
ptrn->exp=exp;
ptrn->next=NULL;
ptrp->next=ptrn;
ptrp=ptrn;
}
}
else if(p2ptr==NULL)
{
while(p1ptr!=NULL)
{
coe=p1ptr->coe;
exp=p1ptr->exp;
p1ptr=p1ptr->next;
ptrn=new node;
if(start==NULL)
start=ptrn;
ptrn->coe=coe;
ptrn->exp=exp;
ptrn->next=NULL;
ptrp->next=ptrn;
ptrp=ptrn;
}
}
} // End of addition
// Subtract two polynomials
void polynomial::subtract(polynomial p1,polynomial p2) // Subtract
{
struct node *p1ptr,*p2ptr;
int coe,exp;
ptrn=ptrp=start=NULL;
p1ptr=p1.start;
p2ptr=p2.start;
while(p1ptr!=NULL && p2ptr!=NULL)
{
if(p1ptr->exp==p2ptr->exp) // If coefficients are equal
{
coe=p1ptr->coe-p2ptr->coe;
exp=p1ptr->exp;
p1ptr=p1ptr->next;
p2ptr=p2ptr->next;
}
else if(p1ptr->exp>p2ptr->exp)
{
coe=p1ptr->coe;
exp=p1ptr->exp;
p1ptr=p1ptr->next;
}
else if(p1ptr->exp<p2ptr->exp)
{
coe=0-p2ptr->coe;
exp=p2ptr->exp;
p2ptr=p2ptr->next;
}
ptrn=new node;
if(start==NULL)
start=ptrn;
ptrn->coe=coe;
ptrn->exp=exp;
ptrn->next=NULL;
ptrp->next=ptrn;
ptrp=ptrn;
} // End of While
if(p1ptr==NULL)
{
while(p2ptr!=NULL)
{
coe=0-p2ptr->coe;
exp=p2ptr->exp;
p2ptr=p2ptr->next;
ptrn=new node;
if(start==NULL)
start=ptrn;
ptrn->coe=coe;
ptrn->exp=exp;
ptrn->next=NULL;
ptrp->next=ptrn;
ptrp=ptrn;
}
}
else if(p2ptr==NULL)
{
while(p1ptr!=NULL)
{
coe=p1ptr->coe;
exp=p1ptr->exp;
p1ptr=p1ptr->next;
ptrn=new node;
if(start==NULL)
start=ptrn;
ptrn->coe=coe;
ptrn->exp=exp;
ptrn->next=NULL;
ptrp->next=ptrn;
ptrp=ptrn;
}
}
} // End of subtraction
int main()
{
clrscr();
polynomial p1,p2,sum,diff;
cout<<"First Polynomial. ";
p1.get_poly();
cout<<" Second polynomial. ";
p2.get_poly();
clrscr();
cout<<" The First polynomial is: ";
p1.show();
cout<<" The second polynomial is: ";
p2.show();
cout<<" The sum of two polynomials is: ";
sum.add(p1,p2);
sum.show();
cout<<" The difference of two polynomials is: ";
diff.subtract(p1,p2);
diff.show();
getch();
return 0;
}
Using arrays:
#include<stdio.h>
#include<conio.h>
main()
{
int a[10], b[10], c[10],m,n,k,k1,i,j,x;
clrscr();
printf(" Polynomial Addition ");
printf(" =================== ");
printf(" Enter the no. of terms of the polynomial:");
scanf("%d", &m);
printf(" Enter the degrees and coefficients:");
for (i=0;i<2*m;i++)
scanf("%d", &a[i]);
printf(" First polynomial is:");
k1=0;
if(a[k1+1]==1)
printf("x^%d", a[k1]);
else
printf("%dx^%d", a[k1+1],a[k1]);
k1+=2;
while (k1<i)
{
printf("+%dx^%d", a[k1+1],a[k1]);
k1+=2;
}
printf(" Enter the no. of terms of 2nd polynomial:");
scanf("%d", &n);
printf(" Enter the degrees and co-efficients:");
for(j=0;j<2*n;j++)
scanf("%d", &b[j]);
printf(" Second polynomial is:");
k1=0;
if(b[k1+1]==1)
printf("x^%d", b[k1]);
else
printf("%dx^%d",b[k1+1],b[k1]);
k1+=2;
while (k1<2*n)
{
printf("+%dx^%d", b[k1+1],b[k1]);
k1+=2;
}
i=0;
j=0;
k=0;
while (m>0 && n>0)
{
if (a[i]==b[j])
{
c[k+1]=a[i+1]+b[j+1];
c[k]=a[i];
m--;
n--;
i+=2;
j+=2;
}
else if (a[i]>b[j])
{
c[k+1]=a[i+1];
c[k]=a[i];
m--;
i+=2;
}
else
{
c[k+1]=b[j+1];
c[k]=b[j];
n--;
j+=2;
}
k+=2;
}
while (m>0)
{
c[k+1]=a[i+1];
c[k]=a[i];
k+=2;
i+=2;
m--;
}
while (n>0)
{
c[k+1]=b[j+1];
c[k]=b[j];
k+=2;
j+=2;
n--;
}
printf(" Sum of the two polynomials is:");
k1=0;
if (c[k1+1]==1)
printf("x^%d", c[k1]);
else
printf("%dx^%d", c[k1+1],c[k1]);
k1+=2;
while (k1<k)
{
if (c[k1+1]==1)
printf("+x^%d", c[k1]);
else
printf("+%dx^%d", c[k1+1], c[k1]);
k1+=2;
}
getch();
return 0;
}