#include <iostream>
#include <cstdlib>

using namespace std;

class term {
        public:
          double coef;
          int    expo;
          term*  sgte;
          term(double co=0.0, int in=0, term* sg=NULL);
          ~term(void);
          term*  cpy(void) const;
          ostream& print(ostream& out) const;
};

ostream& operator << (ostream& out, const term& t)
{
   double c= t.coef;
   if (c >=0)
      out << "+";
   else
      {
       out << "-";
       c= -c;
      }

   if ( t.expo == 0 )
       out << c;
   else
      {
       if (c != 1)
          out << c;
       out << "x";
       if (t.expo >1)
         out << "^" << t.expo;
      }
   if (t.sgte != NULL)
      out << *(t.sgte);
   return out;
}


term::term(double co, int ex, term* sg)
{
   coef= co; expo= ex;
   sgte= sg;
}

term::~term(void)
{
   if (sgte!=NULL)
      delete sgte;
}


term* term::cpy(void) const
{
   return new term(coef, expo, NULL );
}


ostream& term::print(ostream& out) const
{
   out << expo << " ";
   if (sgte != NULL)
      sgte->print(out);
   return out;
}

void ins(term*& cab, term* obj)
{
   if (cab==NULL)
      {
       obj->sgte= NULL;
       cab= obj;
      }
   else
      if (cab->expo < obj->expo)
         {
          obj->sgte= cab;
          cab= obj;
         }
      else
      if (cab->expo == obj->expo)
         {
          double s= cab->coef + obj->coef;
          cerr << "***sumando " << cab->coef << " + "
                             << obj->coef << " = "
                             << s << endl;
          if (s==0.0)
            {
             term* des= cab;
             cab= cab->sgte;
             des->sgte=NULL;
             delete des;
             delete obj;
            }
          else
            {
             cab->coef= s;
             delete obj;
            }
         }
      else
      if (cab->expo > obj->expo)
         {
          ins(cab->sgte, obj);         
         }
}

class poli {
    private:
       term* cab;
    public:
       poli(void);
       ~poli(void);
       int  gr(void) const;
       poli& operator = (const poli& p);
       poli& operator += (const term& t);
       ostream& print(ostream& out) const;
       poli operator + (const poli& q);
       poli operator - (const poli& q);
       poli operator * (const poli& q);
}; 

poli::poli(void)
{
   cab= NULL;
}

poli::~poli(void)
{
   if (cab != NULL)
       delete cab;
}

int poli::gr(void) const
{
    if (cab==NULL)
        return 0;
    else
        return cab->expo;
}

poli& poli::operator= (const poli& p)
{
   delete cab;
   cab= NULL;
   for (term* r= p.cab; r!=NULL; r= r->sgte)
      *this+= *r;
   return *this; 
}


poli& poli::operator+= (const term& t)
{
   ins(cab, t.cpy());
   return *this;
}

poli poli::operator + (const poli& q)
{
    poli p;
    for (term* r= cab; r!=NULL; r= r->sgte)
       p+= *r;
    for (term* r= q.cab; r!=NULL; r= r->sgte)
       p+= *r;
    return p;
}

poli poli::operator - (const poli& q)
{
    poli p;
    for (term* r= cab; r!=NULL; r= r->sgte)
       p+= *r;
    for (term* r= q.cab; r!=NULL; r= r->sgte)
       p+= term(-(r->coef), r->expo);
    return p;
}

poli poli::operator * (const poli& q)
{
    poli p;
    for (term* a= cab; a!=NULL; a= a->sgte)
      for (term* b= q.cab; b!=NULL; b= b->sgte)
        p+=term(a->coef * b->coef, a->expo + b->expo);
    return p;
}


ostream& poli::print(ostream& out) const
{
   if (cab == NULL)
     out << 0;
   else
     out << *cab;
   return out;
}

ostream& operator << (ostream& out, const poli& p)
{
   return p.print(out);
}


int main(void)
{
    poli p, q;
    for (int k=0; k<8; k++)
       p+= term(1,k);

    cout << "p= " << p << endl;

    q += term( 1, 5 );
    q += term(-1, 0 );

    cout << "q= " << q << endl;

    cout << "p-q= " << p-q << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}