Question 23 Polynomial Addition and Subtraction Write a program that adds and su
ID: 666658 • Letter: Q
Question
Question 23
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.
Example: 4X4 + X3 - 3
+ 4X4 - 2X3 + 4X
8X4 - X3 + 4X – 3
The four ways to implement the requirements:
Create an array or ArrayList holding coefficients with the array indexes as exponents
Create and array or ArrayList of nodes, each node holding a term of the polynomial
Use a linked list of terms using pointers.
Polynomials are linked lists in one static array.
Implementations 2, 3, and 4 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 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 in 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 andtoString() methods.
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;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.