Polynomial Representation Using Singly Linked List: Addition and Evaluation of Polynomials in C++

Hi GuyZ,
    Another important application of Singly Linked List is representation of sparse matrix efficiently. Polynomial also can be represent using arrays. But linked list will be better choice than arrays.

Addition of Polynomial:

Image Source: http://www.mathwarehouse.com/algebra/polynomial/how-to-add-subtract-polynomials.php

Evaluation of Polynomial:

Polynomial: 2x²+1x+10
Value of x = 3
=> 2 x 3²+ 1 x 3 + 10
=> 2 x 9  + 3 + 10
=> 18 + 3 + 10
=> 31

Solution

#include <iostream>
#include <cmath>
using namespace std;
struct polynode{
 int coe, exp;
 polynode *link = NULL;
};
class polynomial{
 int i, n;
 polynode *tmp, *nn;
 polynode *poly;
public:
 polynomial(){
   poly = new polynode;
 }
 void read(){
  cout<<"Enter the number: ";
  cin>>n;
  cout<<"Enter items: ";
  nn = new polynode;
  cin>>nn->coe>>nn->exp;
  poly = nn;
  tmp = poly;
  for(i=1;i<n;i++){
   nn = new polynode;
   cin>>nn->coe>>nn->exp;
   tmp->link = nn;
   tmp = nn;
  }
 }
 void evaluation(){
  polynode *tmp = poly;
  int x, sum=0;
  cout<<"Enter value for `x`: ";
  cin>>x;
  while(tmp){
   sum+=(tmp->coe * pow(x, tmp->exp));
   tmp=tmp->link;
  }
  cout<<"Evaluation polynomial ";
  show();
  cout<<" result: "<<sum;
 }
 polynomial operator+(polynomial pol){
  polynomial sum;
  polynode *t1, *t2, *t;
  t1 = poly;
  t2 = pol.poly;
  nn = new polynode;
  if(t1->exp==t2->exp){
   nn->exp = t1->exp;
   nn->coe = t1->coe+t2->coe;
   t1 = t1->link;
   t2 = t2->link;
  }
  else if(t1->exp > t2->exp){
   nn->exp = t1->exp;
   nn->coe = t1->coe;
   t1 = t1->link;
  }
  else{
   nn->exp = t2->exp;
   nn->coe = t2->coe;
   t2 = t2->link;
  }
  sum.poly = nn;
  t = sum.poly;
  while(t1 && t2){
   nn = new polynode;
   if(t1->exp==t2->exp){
    nn->exp = t1->exp;
    nn->coe = t1->coe+t2->coe;
    t1 = t1->link;
    t2 = t2->link;
    t->link = nn;
    t = nn;
   }
   else if(t1->exp > t2->exp){
    nn->exp = t1->exp;
    nn->coe = t1->coe;
    t1 = t1->link;
    t->link = nn;
    t = nn;
   }
   else{
    nn->exp = t2->exp;
    nn->coe = t2->coe;
    t2 = t2->link;
    t->link = nn;
    t = nn;
   }
  }
  while(t1){
   nn = new polynode;
   nn->exp = t1->exp;
   nn->coe = t1->coe;
   t->link = nn;
   t = nn;
   t1 = t1->link;
  }
  while(t2){
   nn->exp = t2->exp;
   nn->coe = t2->coe;
   t->link = nn;
   t = nn;
   t2 = t2->link;
  }
  return sum;
 }
 void show(){
  tmp = poly;
  polynode *nl;
  char str;
  while(tmp->link){
   nl = tmp->link;
   str=(nl->coe<0)?' ':'+';
   cout<<tmp->coe<<"x^"<<tmp->exp<<str;
   tmp=tmp->link;
  }
  cout<<tmp->coe<<"x^"<<tmp->exp;
 }
};
class polyops{
public:
 void menu(){
  int op = 0;
  cout<<"\t\t\tMENU\n1. Add Polynomials\n2. Evaluate Polynomial\n3. Exit";
  while(op!=3){
   cout<<"\nOption: ";
   cin>>op;
   switch(op){
    case 1:  
     add(); 
     break;
    case 2:
     eval();
     break;
    case 3:
     break;
    default:
     cout<<"Error: Try again...";
     break;
   }
  }
 }
 void add(){
  polynomial p1, p2, sum;
  p1.read();
  cout<<"Polynomial 1: ";
  p1.show();
  cout<<endl;
  p2.read();
  cout<<"Polynomial 2: ";
  p2.show();
  cout<<endl;
  sum = p1+p2;  
  cout<<"Sum: ";
  sum.show();
 }
 void eval(){
  polynomial p;
  p.read();
  p.evaluation();
 }
};
int main(){
 polyops p;
 p.menu();
 return 0;
}