#include<iostream>
#include <cstdlib>
#include <string>
#include <cctype>
#include <fstream>
#include <sstream>
#include <cmath>

using namespace std;

enum { CTE, VAR, SUM, RES, CHS, MUL, DIV, EXPO, 
       SIN, COS };
//
//  Nodo:  Clase abstracta
//      Es la clase de la que se desprenden los nodos de los
//      arboles que representan expresiones.
//
 
class Nodo {
    public:
      virtual double Ev(void) const = 0;         // evaluacion
      virtual ostream& Pr(ostream&) const = 0;	 // impresion
      virtual Nodo* Dv(void) const = 0;		 // derivada
      virtual Nodo* Sm(void) const = 0;		 // simplificacion
      virtual int   Tipo(void) const = 0;	 // tipo de nodo
      virtual Nodo* Cp(void) const = 0;          // copia
      virtual Nodo* Izq(void) const;             // hijo izquierdo
      virtual Nodo* Der(void) const;             // hijo derecho
};

ostream& operator << (ostream& out, const Nodo& n);

//
// Cte:   Clase de las constantes.
//    guarda un valor double
//
class Cte : public Nodo {
    private:
      double val;
    public:
      Cte(double v=0);
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo* Dv(void) const;
      virtual Nodo* Sm(void) const;
      virtual int   Tipo(void) const;
      virtual Nodo* Cp(void) const;
};

//
//   Var:  Clase de la variable "x".
//       Estas clases deben hacer referencia hacia una cierta varibla x
//       y debe ser la misma para todos las instancias de la clase.
//
class Var : public Nodo {
    private:
      double* val;
    public:
      Var(double* v);
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo* Dv(void) const;
      virtual Nodo* Sm(void) const;
      virtual int   Tipo(void) const;
      virtual Nodo* Cp(void) const;
};

//
// Funcion:   Clase abstracta de la que se derivan las funciones
//
class Funcion : public Nodo {
    protected:
       Nodo* der; 
    public:
      Funcion(Nodo*);
      virtual ~Funcion(void);
      virtual double Ev(void) const = 0;
      virtual ostream& Pr(ostream&) const = 0;
      virtual Nodo* Dv(void) const = 0;
      virtual Nodo* Sm(void) const = 0;
      virtual int   Tipo(void) const = 0;
      virtual Nodo* Cp(void) const = 0;
      virtual Nodo* Der(void) const { return der; };  // hijo derecho
};

class Chs : public Funcion {
    public:
      Chs(Nodo* d) : Funcion(d) {};
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo*  Dv(void) const;
      virtual Nodo*  Sm(void) const;
      virtual int    Tipo(void) const;
      virtual Nodo*  Cp(void) const;
};

class Sin : public Funcion {
    public:
      Sin(Nodo* d) : Funcion(d) {};
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo* Dv(void) const;
      virtual Nodo* Sm(void) const;
      virtual int   Tipo(void) const;
      virtual Nodo* Cp(void) const;
};

class Cos : public Funcion {
    public:
      Cos(Nodo* d) : Funcion(d) {};
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo* Dv(void) const;
      virtual Nodo* Sm(void) const;
      virtual int   Tipo(void) const;
      virtual Nodo* Cp(void) const;
};


// BinOp:  Clase abstracta que representa a los operadores binarios.
//    Define los apuntadores hacia los hijos de los operadores binarios.
//    Su constructor da valores iniciales a dichos apuntadores.
//
class BinOp : public Nodo {
    protected:
      Nodo* izq;
      Nodo* der;
    public:
      BinOp(Nodo*, Nodo*);
      virtual ~BinOp(void);
      virtual ostream& Pr(ostream&) const = 0;
      virtual Nodo* Dv(void) const = 0;
      virtual Nodo* Sm(void) const = 0;
      virtual int   Tipo(void) const = 0;
      virtual Nodo* Cp(void) const = 0;
      virtual Nodo* Izq(void) const { return izq; };  // hijo izquierdo
      virtual Nodo* Der(void) const { return der; };  // hijo derecho
};

//  Sum:   Clase del operador suma.

class Sum : public BinOp {
    public:
      Sum(Nodo* i, Nodo* d) : BinOp(i,d) {};
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo* Dv(void) const;
      virtual Nodo* Sm(void) const;
      virtual int   Tipo(void) const;
      virtual Nodo* Cp(void) const;
};

//  Resta
//
class Res : public BinOp {
    public:
      Res(Nodo* i, Nodo* d) : BinOp(i,d) {};
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo* Dv(void) const;
      virtual Nodo* Sm(void) const;
      virtual int   Tipo(void) const;
      virtual Nodo* Cp(void) const;
};

class Mul : public BinOp {
    public:
      Mul(Nodo* i, Nodo* d) : BinOp(i,d) {};
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo* Dv(void) const;
      virtual Nodo* Sm(void) const;
      virtual int   Tipo(void) const;
      virtual Nodo* Cp(void) const;
};

class Div : public BinOp {
    public:
      Div(Nodo* i, Nodo* d) : BinOp(i,d) {};
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo* Dv(void) const;
      virtual Nodo* Sm(void) const;
      virtual int   Tipo(void) const;
      virtual Nodo* Cp(void) const;
};

class Expo : public BinOp {
    public:
      Expo(Nodo* i, Nodo* d) : BinOp(i,d) {};
      virtual double Ev(void) const;
      virtual ostream& Pr(ostream&) const;
      virtual Nodo* Dv(void) const;
      virtual Nodo* Sm(void) const;
      virtual int   Tipo(void) const;
      virtual Nodo* Cp(void) const;
};




class Pila {
    private:
       Nodo* P[32];
       int   cnt;

    public:
       Pila(void) { cnt= 0; };
       ~Pila(void);
       Nodo* pop(void)      {  return P[--cnt]; };
       void push(Nodo* x)   {  P[cnt++]= x; };
       bool empty()         {  return cnt==0; };
};

Pila::~Pila(void)
{
    while (!empty())
       delete pop();
}

//
//   Analizador del lexico
//

string lex(istream& inp)
{
   int c;
   do {
     c= inp.get();
   } while (c!= EOF && isspace(c));

   string sim="";

   if (c==EOF)
     sim= "#EOF";
   else
   if (isalpha(c))
     {
      do {
         sim+= char(c);
         c= inp.get();
      }  while (isalpha(c));
      inp.putback(c);
     }
   else
   if (isdigit(c))
     {
      inp.putback(c);
      double x;
      inp >> x;
      ostringstream out;
      out << x;
      sim= out.str();
     }
   else
     switch (c) {
       case '(':
       case ')':
       case '+':
       case '-':
       case '*':
       case '/':
       case '^':
       case ';':  sim+= char(c);
                  break;
       default:   cerr << "caracter no identificado: " << char(c) << endl; 
                  sim= "#MAL";
                  break;
      }
   return sim;
}

string atomo;

Nodo* expr(istream& inp, double* x, Nodo* izq, Nodo* der);

Nodo* prim(istream& inp, double* x, Nodo* izq, Nodo* der)
{
   if (isdigit(atomo[0]))
     {
      istringstream a(atomo);
      double x;
      a >> x;
      atomo=lex(inp);
      return new Cte(x);
     }


  if (atomo=="x" || atomo=="X")
     {
      atomo= lex(inp);
      return new Var(x); 
     }

  if (atomo=="der")
     {
      atomo= lex(inp);
      return der->Cp();
     }

  if (atomo=="izq")
     {
      atomo= lex(inp);
      return izq->Cp();
     }

  if (atomo=="(")
     {
      atomo= lex(inp);
      Nodo* p= expr(inp, x, izq, der);
      if (atomo==")")
        {
         atomo= lex(inp);
         return p; 
        }
      else
        {
         cerr << "Falta un parentesis )\n";
         exit(1);
        }
     }

   if (atomo=="-")
     {
      atomo= lex(inp);
      return new Chs( prim(inp, x, izq, der));
     }

   if (atomo=="+")
     {
      atomo= lex(inp);
      return prim(inp, x, izq, der);
     }

   if (atomo=="dv")
     {
      atomo= lex(inp);
      if (atomo=="(")
        {
         Nodo* p= prim(inp, x, izq, der);
         return p->Dv();
        }  
     }

   if (atomo=="sin")
     {
      atomo=lex(inp);
      if (atomo=="(")
        return new Sin(prim(inp, x, izq, der));
     }

   if (atomo=="cos")
     {
      atomo=lex(inp);
      if (atomo=="(")
        return new Cos(prim(inp, x, izq, der));
     }

   cerr << "Falta un <primario> ultimo atomo=" << atomo << endl;
   exit(1);
}


Nodo* factor(istream& inp, double* x, Nodo* izq, Nodo* der)
{
    Nodo* f= prim(inp, x, izq, der); 
    while (atomo=="^")
      {
       atomo= lex(inp);
       f= new Expo(f, prim(inp, x, izq, der));
      }
    return f;
}
   

Nodo* term(istream& inp, double* x, Nodo* izq, Nodo* der)
{
   Nodo* t= factor(inp, x, izq, der);
   do {
      if (atomo=="*")
        {
         atomo= lex(inp);
         t= new Mul(t, factor(inp, x, izq, der));
        }
      else
      if (atomo=="/")
        {
         atomo= lex(inp);
         t= new Div(t, factor(inp, x, izq, der));
        }
   } while (atomo=="*" || atomo=="/");
   return t;
}

Nodo* expr(istream& inp, double* x, Nodo* izq, Nodo* der)
{
   Nodo* t= term(inp, x, izq, der);
   do {
      if (atomo=="+")
        {
         atomo= lex(inp);
         t= new Sum(t, term(inp, x, izq, der));
        }
      else
      if (atomo=="-")
        {
         atomo= lex(inp);
         t= new Res(t, term(inp, x, izq, der));
        }
   } while (atomo=="+" || atomo=="-");
   return t;
}


Nodo* Leer(istream& inp, double* x, Nodo* izq, Nodo* der)
{
   atomo= lex(inp);
   Nodo* p= expr(inp, x, izq, der);
   if (atomo==";")
      return p;
   else
      {
       cerr << "Falta un ; al final de la expresion\n";
       exit(1);
      } 
}


//
// Metodos de los nodos.
//
Nodo* Nodo::Izq(void) const
{
    return NULL;
}

Nodo* Nodo::Der(void) const
{
    return NULL;
}

//
//  Para simplificar la forma de imprimir un nodo,
//  definimos el operador << para escribir sobre streams.
//
ostream& operator << (ostream& out, const Nodo& n)
{
   n.Pr(out); 
   return out;
}

//
//  Metodos de las constantes
//

Cte::Cte(double v)
{
   val= v;
}

ostream& Cte::Pr(ostream& out) const
{
   return out << val;
}

double Cte::Ev(void) const
{
   return val;
}

//
// la derivada de una constante es la constante 0
//
Nodo* Cte::Dv(void) const
{
   return new Cte(0);
}

// las constantes no pueden simplificarse
// solo se copian.
//
Nodo* Cte::Sm(void) const
{
   return new Cte(val);
}

// copia de una constante
//
Nodo* Cte::Cp(void) const
{
   return new Cte(val);
}

int Cte::Tipo(void) const
{
   return CTE;
}


//
//   Metodos de las variables
//

Var::Var(double* v)
{
   val= v;
}

//  El nombre de la variable es "x" 
//
ostream& Var::Pr(ostream& out) const
{
   return out << "x";
}

//  La evaluacion depende del valor de la variable x.
//
double Var::Ev(void) const
{
   return *val;
}

//  La derivada de la variable es la constante 1
// 
Nodo* Var::Dv(void) const
{
   return new Cte(1);
}

// Las variables no pueden simplificarse
//
Nodo* Var::Sm(void) const
{
   return new Var(val);
}

Nodo* Var::Cp(void) const
{
   return new Var(val);
}

int Var::Tipo(void) const
{
   return VAR;
}

//
//  Metodos de las funciones
//

Funcion::Funcion(Nodo* d)
{
   der= d;
}

Funcion::~Funcion(void)
{
   if (der != NULL) 
     delete der;
}

//
//  Metodos de Chs
//

double Chs::Ev(void) const
{
   return - (der->Ev());
}

ostream& Chs::Pr(ostream& out) const
{
    int td= der->Tipo();
    if (td==SUM || td==RES || td==CHS)
       out << "- (" << *der << ")";
    else
       out << "-" << *der;
    return out;
}


Nodo* Chs::Dv(void) const
{
   return new Chs( der->Dv() );
}

Nodo* Chs::Sm(void) const
{
    return Cp();
}

int Chs::Tipo(void) const
{
   return CHS;
}

Nodo* Chs::Cp(void) const
{
   return new Chs( der->Cp() );
}

//
//  Metodos de Sin
//

double Sin::Ev(void) const
{
   return sin(der->Ev());
}

ostream& Sin::Pr(ostream& out) const
{
   return out << "sin(" << *der << ")";
}


Nodo* Sin::Dv(void) const
{
   return new Mul(new Cos( der->Cp() ), der->Dv() );
}

Nodo* Sin::Sm(void) const
{
    return Cp();
}

int Sin::Tipo(void) const
{
   return SIN;
}

Nodo* Sin::Cp(void) const
{
   return new Sin( der->Cp() );
}


//
//  Metodos de Cos
//

double Cos::Ev(void) const
{
   return cos(der->Ev());
}

ostream& Cos::Pr(ostream& out) const
{
    out << "cos(" << *der << ")";
    return out;
}


Nodo* Cos::Dv(void) const
{
   istringstream dv("-sin(der)*dv(der);");
   return Leer( dv, NULL, NULL, der );
}


Nodo* Cos::Sm(void) const
{
    return Cp();
}

int Cos::Tipo(void) const
{
   return COS;
}

Nodo* Cos::Cp(void) const
{
   return new Cos( der->Cp() );
}




//
//  Metodos de BinOp
//

BinOp::BinOp(Nodo* i, Nodo* d)
{
   izq= i;
   der= d;
}

//  El destructor elimina a ambos hijos
//
BinOp::~BinOp(void)
{
   if (der != NULL) 
     delete der;
   if (izq != NULL) 
     delete izq;
}


//
//  Metodos de Sum
//

//  El operador suma tiene la precedencia de asociacion mas baja.
//  sus operandos no necesitan escribirse entre parentesis.
//
ostream& Sum::Pr(ostream& out) const
{
   out << "DEB: " << *izq << endl;
   out << "DEB: " << *der << endl;
   return out << *izq << "+" << *der;
}

//  El valor de la suma es la suma de los valores de los hijos.
//
double Sum::Ev(void) const
{
   return izq->Ev() + der->Ev();
}

// La derivada de la suma es la suma de las derivadas de los hijos.
//
Nodo* Sum::Dv(void) const
{
   istringstream dv("dv(izq) + dv(der) ; ");
   return Leer( dv, NULL, izq, der );
}

// Simplificacion de la suma
//    se encuentra la simplificacion de los hijos
//    cte + cte ->  cte
//    0 + expr -> expr
//    expr + 0 -> expr
//    se construye la suma de las simplificaciones de los hijos.
// 
Nodo* Sum::Sm(void) const
{
   Nodo* iz= izq->Sm();
   Nodo* de= der->Sm();
   
   int ti= iz->Tipo();
   int td= de->Tipo();

   if (ti==CTE && td==CTE)
     {
      double c= iz->Ev() + de->Ev();
      delete iz;
      delete de;
      return new Cte(c);
     }

   if (ti==CTE && iz->Ev()==0)
     {
      delete iz;
      return de;
     }

   if (td==CTE && de->Ev()==0)
     {
      delete de;
      return iz;
     }

   if ( td==CHS )
     {
      Nodo* r= new Res(iz, de->Der()->Cp()); 
      delete de;
      return r;
     }

   return new Sum(iz,de);
}


Nodo* Sum::Cp(void) const
{
   return new Sum(izq->Cp(), der->Cp());
}

int Sum::Tipo(void) const
{
   return SUM;
}

//
//   Metodos de la Resta
//
ostream& Res::Pr(ostream& out) const
{
   out << *izq << "-";
   if (der->Tipo()==SUM || der->Tipo()==RES)
      out << "(" << *der << ")";
   else
      out << *der;
   return out;
}

double Res::Ev(void) const
{
   return izq->Ev() - der->Ev();
}

Nodo* Res::Dv(void) const
{
   return new Res(izq->Dv(), der->Dv());
}

Nodo* Res::Sm(void) const
{
   Nodo* iz= izq->Sm();
   Nodo* de= der->Sm();
   
   int ti= iz->Tipo();
   int td= de->Tipo();

   if (ti==CTE && td==CTE)
     {
      double c= iz->Ev() - de->Ev();
      delete iz;
      delete de;
      return new Cte(c);
     }

   if (td==CTE && de->Ev()==0)
     {
      delete de;
      return iz;
     }

   if ( td==CHS )
     {
      Nodo* r= new Sum(iz, de->Der()->Cp()); 
      delete de;
      return r;
     }

   return new Res(iz,de);
}

Nodo* Res::Cp(void) const
{
   return new Res(izq->Cp(), der->Cp());
}

int Res::Tipo(void) const
{
   return RES;
}

//
//  Metodos de la multiplicacion
//
ostream& Mul::Pr(ostream& out) const
{
   if (izq->Tipo()==SUM || izq->Tipo()==RES)
      out << "(" << *izq << ")";
   else
      out << *izq;

   out << "*";

   if (der->Tipo()==SUM || der->Tipo()==RES)
      out << "(" << *der << ")";
   else
      out << *der;

   return out;
}

double Mul::Ev(void) const
{
   return izq->Ev() * der->Ev();
}

Nodo* Mul::Dv(void) const
{
   return  new Sum(
             new Mul(izq->Dv(), der->Cp()),
             new Mul(izq->Cp(), der->Dv())
           );
}

Nodo* Mul::Sm(void) const
{
   Nodo* iz= izq->Sm();
   Nodo* de= der->Sm();
   
   int ti= iz->Tipo();
   int td= de->Tipo();

   if (ti==CTE && td==CTE)
     {
      double c= iz->Ev() * de->Ev();
      delete iz;
      delete de;
      return new Cte(c);
     }

   if (td==CTE && de->Ev()==0)
     {
      delete iz;
      return de;
     }

   if (ti==CTE && iz->Ev()==0)
     {
      delete de;
      return iz;
     }

   if (td==CTE && de->Ev()==1)
     {
      delete de;
      return iz;
     }

   if (ti==CTE && iz->Ev()==1)
     {
      delete iz;
      return de;
     }

   return new Mul(iz,de);
}

Nodo* Mul::Cp(void) const
{
   return new Mul(izq->Cp(), der->Cp());
}

int Mul::Tipo(void) const
{
   return MUL;
}


//  Metodos de la Division
//
ostream& Div::Pr(ostream& out) const
{
   if (izq->Tipo()==SUM || izq->Tipo()==RES)
      out << "(" << *izq << ")";
   else
      out << *izq;

   out << "/";

   if (der->Tipo()==SUM || der->Tipo()==RES 
    || der->Tipo()==MUL || der->Tipo()==DIV )
      out << "(" << *der << ")";
   else
      out << *der;

   return out;
}

double Div::Ev(void) const
{
   return izq->Ev() / der->Ev();
}

Nodo* Div::Dv(void) const
{  // esta derivada esta mal.
   return  new Sum(
             new Mul(izq->Dv(), der->Cp()),
             new Mul(izq->Cp(), der->Dv())
           );
}

Nodo* Div::Sm(void) const
{  // no se esta simplificando.
   return Cp();
}

Nodo* Div::Cp(void) const
{
   return new Div(izq->Cp(), der->Cp());
}

int Div::Tipo(void) const
{
   return DIV;
}

//
//  Metodos de la Exponenciacion
//
ostream& Expo::Pr(ostream& out) const
{
   if (izq->Tipo()==SUM || izq->Tipo()==RES 
    || izq->Tipo()==MUL || izq->Tipo()==DIV 
    || izq->Tipo()==EXPO )
      out << "(" << *izq << ")";
   else
      out << *izq;

   out << "^";

   if (der->Tipo()==SUM || der->Tipo()==RES 
    || der->Tipo()==MUL || der->Tipo()==DIV
    || der->Tipo()==EXPO  )
      out << "(" << *der << ")";
   else
      out << *der;

   return out;
}

double Expo::Ev(void) const
{
   return pow(izq->Ev(), der->Ev());
}

Nodo* Expo::Dv(void) const
{  // esta derivada esta mal.
   return  new Sum(
             new Mul(izq->Dv(), der->Cp()),
             new Mul(izq->Cp(), der->Dv())
           );
}

Nodo* Expo::Sm(void) const
{  // no se esta simplificando.
   return Cp();
}

Nodo* Expo::Cp(void) const
{
   return new Expo(izq->Cp(), der->Cp());
}

int Expo::Tipo(void) const
{
   return EXPO;
}



int main(int nargs, char* args[])
{
   double x;
   Pila p; 
   Nodo* s;
 
   s= Leer(cin, &x, NULL, NULL);

   cout << "f(x)= " << *s << endl;
   
   Nodo* d= s->Dv();

   cout <<  "f'(x)= " << *d << endl;

   Nodo* sd= d->Sm();

   cout <<  "f'(x)= " << *sd << endl;

   delete sd;
   delete d;
   delete s; 

   system("PAUSE");
   return EXIT_SUCCESS;
}