Interprete de funciones mediante  un árbol  binario de expresiones

Introducción

En muchos problemas de programación numérica es necesario trabajar con los valores obtenidos al evaluar una expresión matemática determinada, generalmente la solución a este problema radica en escribir directamente en el código fuente dicha expresión para luego usarla. La vía anterior trae como inconveniente la recompilación del código fuente cada vez que se quiera definir otra expresión matemática, lo que a su vez nos limita si queremos hacer un programa que sea genérico en ese sentido. Al usar un intérprete de funciones se puede solucionar este problema, al poder evaluar de forma dinámica cualquier expresión matemática. Sin embargo, prácticamente ningún lenguaje de programación trae en su implementación estándar de funciones y/o clases algún soporte para interpretar funciones dinámicamente.

El presente trabajo pretende explicar los algoritmos usados en la creación del intérprete, así como constituir un pequeño manual de usuario. Al final del artículo está el código fuente, espero que a alguien lo sea de utilidad.

Conceptos importantes

Es necesario para una mejor comprensión de este trabajo definir una serie términos que serán usados con frecuencia:

Notación polaca (notación prefija): Es una forma de notación de expresiones matemáticas donde los operadores se colocan a la izquierda de los operandos. Su invención se debe al matemático polaco Jan Łukasiewicz, quién la creó alrededor de 1920. Una característica distintiva de este tipo de notación es que se puede prescindir del uso de paréntesis como se hace en la notación infija (notación tradicional).

Notación polaca inversa (notación postfija): Este es el tipo de notación que tiene una aplicación práctica en este trabajo, a diferencia de la notación prefija, en la notación postfija los operadores son colocados a la derecha de los operandos. En la siguiente tabla se muestran ejemplos de notación polaca inversa:

Notación Tradicional         Notación Polaca Inversa
a + b                        a b +
(a+b) * c                    a b  + c *

Pila (''stack'' en inglés): es una estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Cuando se trata de extraer un elemento almacenado en este tipo de estructura, la extracción se realiza en el orden inverso del que fueron almacenados, es decir el último elemento almacenado es el primero en salir y el primero que fue almacenado es el último que puede ser extraído.

Las operaciones básicas que se realizan sobre una pila son las siguientes:

  • Apilar un elemento: introducir (almacenar) un nuevo elemento en la pila
  • Despilar un elemento: extraer un elemento de la pila, este elemento será el último en ser apilado

Operadores binarios: Acordaremos en llamar operadores binarios a todos aquellos que actúen sobre dos operandos, estos son: suma (+), resta (-), multiplicación (*), ...., ect.

Operadores unarios: Acordaremos en llamar operadores unarios a todos aquellos que actúen sobre s/sólo un operando, estos son las funciones matemáticas básicas : seno, coseno, tangente, raíz cuadrada, logarítmo natural, ...., ect.

De notación infija a notación postfija

Para contruir el árbol de expresiones que represente nuestra expresión matemática es necesario construir primero la misma expresión pero en la notación polaca correspondiente y a partir de esta es que se construye el árbol. El algoritmo usado para transformar una expresión infija a prefija es explicado a continuación.

Sea A una expresión infija cualquiera, formada por operadores, paréntesis (izquierdos y derechos) y operandos, también se usará una pila para los operadores. El procedimiento seguido es el siguiente:

Se lee un elemento de A, si este es un operador o un paréntesis izquierdo, entonces se actúa según la regla I y si es un operando entonces se envía directamente a la expresión de notación polaca. Si el elemento leído de A es un paréntesis derecho, entonces se desapilarán elementos de la pila de operadores hasta encontrar el correspodiente paréntesis izquierdo. Cada elemento desapilado pasa a formar parte de la notación polaca, excepto los paréntesis. Cuando no queden elementos en A, entonces se desapilan operadores de la pila, hasta que esta quede vacía.

Regla I:

Existe un orden de prioridad para los operadores, que de menor a mayor es el siguiente: suma (+) y resta (-), multiplicación (*) y división (/), exponenciación (^), operadores unarios. El paréntesis izquierdo lo trataremos como un operador (aunque no lo es) cuyo orden de prioridad es el mayor de todos cuando se quiera apilar y el menor de todos cuando esté en la cima de la pila.

Cuando se intente apilar algún operador se hará lo siguiente: si es un operador unario entonces se apila, si es un operador binario, se comparará su prioridad con el último insertado en la pila (el de la cima), si su prioridad es mayor, entonces se apilará. Si ocurre lo contrario (su prioridad es menor o igual) entonces el operador de la cima de la pila se desapilará y pasará a formar parte de la notación polaca. Se volverá a intentar apilar el operador siguiendo la misma regla, hasta que se pueda apilar, si la pila queda vacía también se apila. El paréntesis izquierdo siempre se apilará y no podrá ser desapilado por ningún operador y por tanto no formará parte de la notación polaca inversa.

El siguiente ejemplo, ayudará a entender mejor lo dicho anteriomente. Sea la siguiente expresión infija: 2^sin(y+x)–ln(x).
En la siguiente tabla se muestra paso a paso la conversión a notación postfija. Se usa el color rojo para señalar los casos en que es necesario desapilar operadores de la pila.

Construccion del árbol binario de expresiones

Una vez obtenida la expresión en notación postfija, se puede evaluar mediante el uso nuevamente de una pila. Sin embargo, en nuestro caso se trabaja con una árbol binario de expresiones, así que lo que se hace es construir el árbol. El algoritmo usado para construir el árbol no usa como tal la expresión postfija ya conformada, sino que el árbol se va construyendo usando las mismas reglas con las que se construye la notación postfija, una pila para los operadores y otra para los nodos del árbol, ambas no son necesitadas al terminar el árbol. El algoritmo es el siguiente:

Se siguen las mismas reglas expuestas anteriormente usando la pila de operadores, pero cuando se encuentra un operando o un operador es desapilado, entonces se crea el nodo correspondiente y se actúa según la regla II. Al finalizar el algoritmo solo debe quedar un nodo apilado en la pila de nodos, el que constituye el nodo raíz de nuestro árbol de expresiones.

Regla II.

Si el nodo corresponde a un operando, entonces se apila. Si el nodo corresponde a una operador unario entonces se desapila un nodo de la pila de nodos y es enlazado a la rama izquierda del nodo correspondiente al operador unario y este último es apilado. Si el nodo corresponde a un operador binario entonces dos nodos son desapilados de la pila de nodos, el primero es enlazado a la rama derecha del nodo binario y el segundo a la rama izquierda, nuevamente este nodo es apilado.

En el siguiente ejemplo se usa la misma expresión infija anterior (2^sin(y+x) – ln (x)) para ilustrar el procedimiento para construir el árbol:


Evaluación de la expresión representada por el árbol

Luego de que se tiene el árbol conformado, la evaluación de la expresión contenida se realiza mediante un procedimiento recursivo. El algoritmo en seudocódigo es el siguiente:

resultado = evaluar (raiz_arbol)

evaluar (nodo)
{
     Si el nodo corresponde a un operando entonces : {
        Se retorna el valor del operando
     }
     Si el nodo corresponde a un operador unario A entonces: {
        Se retorna: A( evaluar(nodo->rama_izquierda) )
     }
     Si el nodo corresponde a un operador binario X entonces: {
        Se retorna: evaluar(nodo->rama_izquierada) X evaluar(nodo->rama_derecha)
     }
}

El intérprete implementado

Para crear el intérprete se construyó la clase exp_tree, la cual contiene funciones miembro que permiten construir un árbol de expresiones a partir de una notación infija y evaluar la expresión. La notación infija a interpretar solo debe contener carácteres alfanuméricos, paréntesis (izquierdos y derechos) y espacios. Los carácteres x, y, z y t están reservados para las variables permitidas por el intérprete. Los operadores permitidos son los siguientes: +, -, /, *, ^ y varias funciones como sin(), cos(), tan(), exp().., ect. También se han incluido las constantes más usadas: el número pi (PI) y el número e (E).

Añadir una nueva variable, constante o operador (en especial unario) al intérprete es una tarea relativamente sencilla, se ha comentareado el código fuente con ese objetivo.

La clase exp_tree.

A continuación se hará una breve descripción de sus principlaes métodos:

exp_tree::exp_tree(const char *tex);
exp_tree::exp_tree(const std::string &tex);

Las funciones anteriores constituyen los constructores simples de la clase, ellas permiten crear el árbol binario de expresiones a partir de una expresión infija contenida en el argumento “tex” (que puede ser un arreglo de caracteres o un objeto del tipo string respectivamente).

void exp_tree::setFunc(const char *tex);
void exp_tree::setFunc(const std::string &tex);

Mediante esta función se puede crear un nuevo árbol de expresiones a partir de de la expresión infija contenida en “tex”, el árbol anterior es eliminado.

double exp_tree::eval(double x = 0, double y = 0, double z = 0, double t = 0);
double exp_tree::operator()(double x = 0, double y = 0, double z = 0, double t = 0);

Las dos funciones anteriores hacen posible la evaluación de la expresión contenida en el árbol de expresiones. En la primera forma se hace a través de la función miembro “eval()” y en el segundo caso se ha sobrecargado el operador paréntesis, para lograr el mismo objetivo. En el siguiente fragmento de código se usan las dos formas:

exp_tree ob("sin(x+y) * exp(t)" )

a = ob.eval(2, 90, 0, 0.45);
a = ob(2, 90, 0, 0.45); // esta sentencia es equivalente a la anterior

Además un objeto del tipo exp_tree puede ser asignado a otro objeto usando el operador "=" (que también ha sido sobrecargado) y puede ser pasado como argumento de una función por referencia y por valor.

Código fuente

El código fuente ha sido comentareado con la sintaxis de Doxygen.

arbol_exp.h

/*
Roberto C. Cruz Rodríguez
    rcruz@instec.cu
*/
/**
*    @author Roberto C. Cruz Rodríguez <rcruz@instec.cu>
*/
#ifndef ARBOL_EXP_H
#define ARBOL_EXP_H

#include <string>

namespace alg {

/**
* Contiene una lista de las operaciones y funciones soportadas por el interprete.
*
* CONST, PI, E, VARX, VARY, VARZ, VART : siempre serán nodos hojas poque representan un valor (operando)
*
* SUMA, RESTA, MULT, DIV, POT : son los operadores binarios soportados por el intérprete, siempre serán nodos binarios
*
* SIN, COS, LN, ABS, .... : son los operadores unarios soportados, siempre serán nodos unarios     
*/
enum type_node { CONST, PI, E, VARX, VARY, VARZ, VART,
                 PAR,                           
                 SUMA, RESTA, MULT, DIV, POT,  
                 SIN, COS, TAN, SINH, COSH, ATAN, TANH, ASIN,
                 ACOS, EXP, ABS, LN, LG, SQRT          
               };                                                              

/**
*  Node del árbol binario de expresiones.
*/
struct exp_node
{
/**
* c_const : este campo almacena un valor númerico, que puede el valor de una variable (x, y, z, t)
* o bien un valor constante contenido en la expresión matemática. Este campo solo es usado cuando el nodo
* no tiene más ramificaciones (nodo hoja)  
*/
double c_const;

/**
* type : indica el tipo de nodo, en el árbol de expresiones cada nodo indica una operación a realizar
* o bien almacena un valor númerico (que estará en c_const), en cuyo caso la operación a realizar es
* retornar dicho valor. 
*/
type_node type;

/**
* left : es un puntero a otro nodo, es la rama izquierda del nodo, cuando left contiene el valor NULL
* entones el nodo no tiene rama izquierda.
*/
exp_node *left;

/**
* rigth : es un puntero a otro nodo, es la rama derecha del nodo, cuando rigth contiene el valor NULL
* entones el nodo no tiene rama derecha.
*/
exp_node *rigth;
};

/**
*  La clase  exp_tree define un arbol binario de expresiones.
*  Esta clase implementa un interprete de funciones de cuatro variables
*  x, y, z, y t.
*/
class exp_tree
{
public :
/**
* Constructor simple.
*/
exp_tree();

/**
* Constructor simple.
* @param tex : es una referencia a un objeto string
* donde esta contenida la expresión matemática, dicha expresión
* debe contener solamente carácteres alfanúmericos y espacios en blanco  
*/
exp_tree(const std::string &tex);

/**
* Constructor simple.
* @param tex : es un puntero a una cadena de carácteres
* donde esta contenida la expresión matemática, dicha cadena
* debe contener solamente carácteres alfanúmericos y espacios en blanco  
*/
exp_tree(const char *tex);

/**
* Constructor de copia.
* @param other : es una referencia a otra objeto del tipo exp_tree,
*   
*/
exp_tree(const exp_tree & other);
~exp_tree();

/**
* Establece una nueva expresión matemática.
* @param tex : es una referencia a un objeto string
* donde esta contenida la expresión matemática, dicha expresión
* debe contener solamente carácteres alfanúmericos y espacios en blanco  
*/
void setFunc(const std::string &tex);

/**
* Establece una nueva expresión matemática.
* @param tex : es un puntero a una cadena de carácteres
* donde esta contenida la expresión matemática, dicha cadena
* debe contener solamente carácteres alfanúmericos y espacios en blanco  
*/
void setFunc(const char *tex);

/**
* Evalua la expresión matemática.
* @param x : variable x (double)
* @param y : variable y (double)
* @param z : variable z (double)
* @param t : variable t (double) 
* @return Se retorna el resultado de evaluar la expresión matemática.
*/
double eval(double x = 0, double y = 0, double z = 0, double t = 0);

/**
* Operador de asignación.
*/
exp_tree &operator=(const exp_tree & other);

/**
* Operador de paréntesis ().
* El operador de paréntesis, es una alternativa
* a la función miembro eval, para evaluar la expresión matemática.
* @param x : variable x (double)
* @param y : variable y (double)
* @param z : variable z (double)
* @param t : variable t (double)
* @return Se retorna resultado de evaluar la expresión. 
*/
double operator()(double x = 0, double y = 0, double z = 0, double t = 0);

private :

void delete_tree(exp_node *nod);
exp_node *make_cpy(exp_node *nod);

double eval_tree(exp_node *nod);
void build_tree(std::string &in_exp);

exp_node *root;
double x, y, z, t;
};

/**
*   Pila de Nodos
*/
class pilaNode
{
    public:
        pilaNode() {n=0; head =0;}
        ~pilaNode();
        exp_node* top() {return head->ptr;}
        void      pop();
        void push(exp_node *ptr);
        bool empty() {return (n) ? false : true;}
    private:
        struct node
        {
            exp_node *ptr;
            node *next;
        } *head;
        unsigned n;
};

/**
*   Pila de Operadores
*/
class pilaOp
{
    public:
        pilaOp() {n=0; head = 0;}
        ~pilaOp();
        type_node top() {return head->value;}
        void      pop();
        void push(type_node value);
        bool empty() {return (n) ? false : true;}
    private:
        struct node
        {
            type_node value;
            node *next;
        } *head;
        unsigned n;
};

};
#endif

arbol_exp.h

/*
Roberto C. Cruz Rodríguez
    rcruz@instec.cu
*/

// Este interprete de funciones se basa en la creación de un árbol binario de expresiones
// donde cada nodo representa una operación a realizar y cada hoja un valor númerico

#include "arbol_exp.h"

#include <cstdlib>
#include <cctype>
#include <cmath>

namespace alg {

//////////////////////////////////////////
// IMPLEMENTACION DE LA CLASE arbol_exp //
//////////////////////////////////////////
exp_tree::exp_tree()
{
root = 0;
}

exp_tree::exp_tree(const char *tex)
{
root = 0;
std::string in_exp = tex;

std::string::size_type pos = 0;                                                   // aquí se eliminan los espacios en blanco de la entrada  
while (std::string::npos != ( pos = in_exp.find(" ",pos) ) ) in_exp.erase(pos,1); // para facilitar la lectura de la expresión matemática

build_tree(in_exp);
}

exp_tree::exp_tree(const std::string &tex)
{
root = 0;
std::string in_exp = tex;

std::string::size_type pos = 0;                                                   // aquí se eliminan los espacios en blanco de la entrada  
while (std::string::npos != ( pos = in_exp.find(" ",pos) ) ) in_exp.erase(pos,1); // para facilitar la lectura de la expresión matemática

build_tree(in_exp);
}

exp_tree::exp_tree(const exp_tree &other )                                            // constructor de copia 
{
this->root = make_cpy( other.root );
}

exp_tree::~exp_tree()                                                                 // destructor
{
delete_tree(root);
}

/********************************************************       
* void exp_tree::setFunc(const std::string &tex)        *
*********************************************************
* Con esta función se elimina el
* árbol actual y se construye otro
* a partir de una nueva expresión
*/
void exp_tree::setFunc(const std::string &tex)                                      
{                                                                                    
delete_tree(root);                                                               
std::string in_exp = tex;

std::string::size_type pos = 0;                                                   // aquí se eliminan los espacios en blanco de la entrada  
while (std::string::npos != ( pos = in_exp.find(" ",pos) ) ) in_exp.erase(pos,1); // para facilitar la lectura de la expresión matemática

build_tree(in_exp);
}

/********************************************************       
* void exp_tree::setFunc(const char *tex)               *
*********************************************************
*         La misma que la anterior
*/
void exp_tree::setFunc(const char *tex)
{
delete_tree(root);
std::string in_exp = tex;

std::string::size_type pos = 0;                                                   // aquí se eliminan los espacios en blanco de la entrada  
while (std::string::npos != ( pos = in_exp.find(" ",pos) ) ) in_exp.erase(pos,1); // para facilitar la lectura de la expresión matemática

build_tree(in_exp);
}

/********************************************************       
* exp_tree &exp_tree::operator=(const exp_tree &other)  *
*********************************************************
* Esta función nos permite evaluar
* la expresión matemática
*/
double exp_tree::eval(double xx , double yy , double zz , double tt)                 
{                                                                                     
x = xx;
y = yy;
z = zz;
t = tt;

return eval_tree(root);
}

/********************************************************       
* exp_tree &exp_tree::operator=(const exp_tree &other)  *
*********************************************************
* la homonimia del operador '=', nos
* permite especificar como debe ser la 
* asignacion de un objeto del tipo exp_tree 
* a otro ......
*/
exp_tree &exp_tree::operator=(const exp_tree &other)                                 
{                                                                                    
delete_tree(root);                                                                
root = make_cpy(other.root);                                                      
}

/*****************************************************************************       
* double exp_tree::operator()(double xx , double yy , double zz , double tt) *
******************************************************************************
* la homonimia del operador '()' nos permite
* evaluar la expresion usando parentesis
* de esta forma result = function(78,0,0,1)
*/
double exp_tree::operator()(double xx , double yy , double zz , double tt)   
{                                                                            
x = xx;                                                                  
y = yy;
z = zz;
t = tt;

return eval_tree(root);                                                          
}                                                                                    
                                                                                      
/********************************************************       
*    double exp_tree::eval_tree(exp_node *nod)          *
*********************************************************
* esta es la función más importante de la clase ...
* es una función recursiva que recorre el arbol binario
* de expresiones y realiza la operacion matemática corres-
* pondiente en cada nodo para finalmete, devolver el resultado
* de evaluar la expresión contenida en el arbol .......
*/
double exp_tree::eval_tree(exp_node *nod) 
{                                        
                                         
switch (nod->type)                   
{                                    
case CONST :
return nod->c_const;

case VARX  :
return x;

case VARY  :
return y;

case VARZ  :
return z;

case VART  :
return t;

        case E:
            return M_E;

        case PI:
            return M_PI;

case SUMA :
return eval_tree(nod->left) + eval_tree(nod->rigth);     

case RESTA :
return eval_tree(nod->left) - eval_tree(nod->rigth);

case MULT :
return eval_tree(nod->left) * eval_tree(nod->rigth);

case DIV :
return eval_tree(nod->left) / eval_tree(nod->rigth);

case POT :
return pow (eval_tree(nod->left),  eval_tree(nod->rigth) );

case SIN :
return sin ( eval_tree(nod->left) );

case COS :
return cos ( eval_tree(nod->left) );

case SQRT :
return sqrt( eval_tree(nod->left) );

case TAN :
return tan ( eval_tree(nod->left) );

case ATAN :
return atan ( eval_tree(nod->left) );

case SINH :
return sinh ( eval_tree(nod->left) );

case COSH :
return cosh ( eval_tree(nod->left) );

case TANH :
return tanh ( eval_tree(nod->left) );

case ASIN :
return asin ( eval_tree(nod->left) );

case ACOS :
return acos ( eval_tree(nod->left) );

case EXP :
return exp ( eval_tree(nod->left) );

case ABS :
return fabs ( eval_tree(nod->left) );

case LN :
return log ( eval_tree(nod->left) );

case LG :
return log10 ( eval_tree(nod->left) );

/* si se ha añadido otra función, entoces solo agregue otro 'case ' y defina la operación a realizar */

}
}
                                                       
/********************************************************       
* void exp_tree::delete_tree(exp_node *nod)             *
*********************************************************
* esta función se encarga de eliminar un subarbol
* a partir de su nodo raiz, recorriendo el arbol
* en post-orden. Es usada para eliminar el arbol de
* expresiones cuando se le pasa como argumento 'root'
*        ... es una función recursiva .........
*/
void exp_tree::delete_tree(exp_node *nod)                                             
{                                                                                      
if (!nod)                                                                         
return;                                                                      
                                                                                 
delete_tree(nod->left);                                                          
delete_tree(nod->rigth);
delete nod;
}

/********************************************************       
*      exp_node *exp_tree::make_cpy(exp_node *nod)      *
*********************************************************
* esta es otra función recursiva, que recorre el árbol
* en pre-orden y por cada nodo crea una nuevo con la misma
* información, para finalmente devolver un puntero a un nuevo 
* árbol de expresiones que es una copia del recorrido
* ..... es usada por el constrcutor de copia y por el operador '='
*/
exp_node *exp_tree::make_cpy(exp_node *nod)                                           
{                                                                                      
if (!nod) return 0;                                                                
                                                                                       
exp_node *ptr = new exp_node;                                                       
ptr->type  = nod->type;                                                           
ptr->c_const = nod->c_const;

ptr->left = make_cpy(nod->left);
ptr->rigth = make_cpy(nod->rigth);

return ptr;
}

/********************************************************       
* void exp_tree::build_tree(std::string &in_exp)        *
**********************************************************/
// Con esta función se construye el árbol binario de expresiones
// a partir de la expresión infija contenida en 'in_exp'

void exp_tree::build_tree(std::string &in_exp)                                          
{                                                                                        
pilaOp   pila_op  ;  // pila de operadores                          
//std::stack <exp_node *>  pila_nod ;  // pila de nodos                            
    pilaNode pila_nod;  
                                                                                       
std::string tmp_str;

std::string::size_type i, pos = 0, len = in_exp.length();

while (pos < len)
{
if ( in_exp[pos] == '(' )  // Ej. "(......" o "....(........"                                           
{                                                                   
pila_op.push(PAR); ++pos;    // se apila siempre                                       
}                                                                    
else if ( in_exp[pos] ==')' )
{                                                                    
while ( pila_op.top() != PAR )  // se desapilan operadores hasta que se encuentre '(' PAR                               
{                                                                
root = new exp_node;                                         
root->type = pila_op.top();                                       
if (root->type  < SIN) // si es un operador binario                                        
{                                                            
root->rigth = pila_nod.top(); pila_nod.pop();        
root->left = pila_nod.top(); pila_nod.pop();        
}                                                            
else                   // si es unario                                                       
{
root->left = pila_nod.top(); pila_nod.pop();      
                        root->rigth = 0; 
}                                                           
pila_op.pop();      
pila_nod.push(root);
}
pila_op.pop(); // se desapila PAR            
++pos;                  
}
else if (!pos && in_exp[pos] == '-' && isdigit(in_exp[pos+1]) ) // Ej. : "-34.89....." (constante negativa) Forma 1        
{                                                                    
root = new exp_node;                                              
root->left = 0;                                                   
root->rigth = 0;                                                  
root->type = CONST;                                                  
                                                                               
i = pos++;                                                          
while ( isdigit(in_exp[pos]) || in_exp[pos] == '.' ) ++pos; // se lee la constante completa       
                                                                               
root->c_const = atof( in_exp.substr(i, pos - i).c_str() );        
pila_nod.push(root);                                               
}    
else if ( pos && in_exp[pos] == '-' && in_exp[pos-1] == '(' && isdigit(in_exp[pos+1]) )//Ej. "..(-34.89...." (constante negativa) 
{                                                                     
root = new exp_node;                                             
root->left = 0;                                                  
root->rigth = 0;                                                 
root->type = CONST;                                              
                                                                             
i = pos++;                                                         
while ( isdigit(in_exp[pos]) || in_exp[pos] == '.' ) ++pos;      

root->c_const = atof( in_exp.substr(i, pos-i).c_str() );
pila_nod.push(root);
}
else if ( isdigit(in_exp[pos]) )// Ej. : "....67.009.." ( constante positiva )                                    
{                                                                   
root = new exp_node;                                           
root->left = 0;                                                 
root->rigth = 0;                                                
root->type = CONST;                                             
                                                                            
i = pos;                                                        
while ( isdigit(in_exp[pos]) || in_exp[pos] == '.' ) ++pos;     
                                                                            
root->c_const = atof( in_exp.substr(i, pos-i).c_str() );
pila_nod.push(root);
}
        else if ( in_exp[pos] == 'E' || in_exp[pos] == 'P' ) // Las constantes PI y el numero E      
        {                                                                 
            root = new exp_node;                                              
            root->left = 0;                                                   
            root->rigth = 0;      
            if (in_exp[pos] == 'E')
            {
                root->type = E;
                pos++;                                           
            }
            else
            {
                root->type = PI;
                pos+=2;                                               
            }                                                                   
            pila_nod.push(root);                                               
        }    
else if ( in_exp[pos] == 'x' ) //Ej. : "......x......." (variable x)                                    
{                                                                   
root = new exp_node;                                            
root->left = 0;                                                 
root->rigth = 0;                                                
root->type = VARX;                                              
pila_nod.push(root);                                            
++pos;
}
else if ( in_exp[pos] == 'y' )//Ej. : "......y......." (variable y)                                       
{                                                                    
root = new exp_node;                                             
root->left = 0;                                                 
root->rigth = 0;                                                
root->type = VARY;
pila_nod.push(root);
++pos;                                                          
}
else if ( in_exp[pos] == 'z' )//Ej. : "......z......." (variable z)                                      
{
root = new exp_node;
root->left = 0;
root->rigth = 0;
root->type = VARZ;
pila_nod.push(root);
++pos;
}
else if ( pos == len-1 && in_exp[pos] == 't')//Ej. : "......t" (variable t)                          
{                                                                      
root = new exp_node;
root->left = 0;
root->rigth = 0;
root->type = VART;
pila_nod.push(root);
++pos;
}
else if ( in_exp[pos] == 't' && in_exp[pos+1] != 'a'  )//Ej. : "......t......." (variable t) !!!! no tangente !!!!!
{
root = new exp_node;
root->left = 0;
root->rigth = 0;
root->type = VART;
pila_nod.push(root);
++pos;
}
else if ( !pos && in_exp[pos] == '-' ) // Ej. : "-sin(.........." o "-x........" (- unario) Forma 1
{                                      // En este caso una expresión del tipo "-sin(.........." ó "-x........"             
root = new exp_node;               // será tratada como "-1*sin(.........." y  "-1*x........"
root->type = CONST;
root->left = 0;
root->rigth = 0;
root->c_const = -1.0000000000000000000;
pila_nod.push(root);

while ( !pila_op.empty() && pila_op.top() > RESTA )
{
root = new exp_node;
root->type = pila_op.top();
if  ( root->type < SIN )
{
root->rigth = pila_nod.top(); pila_nod.pop();
root->left = pila_nod.top(); pila_nod.pop();
}
else
{
root->left = pila_nod.top(); pila_nod.pop();
root->rigth = 0;
}
pila_nod.push(root);
pila_op.pop();
}
pila_op.push(MULT);
++pos;
}
else if ( in_exp[pos] == '-' && in_exp[pos-1] == '(' ) // Ej. : "...(-sin..." o "...(-x..." (- unario) Forma 2
{                                                      // En este caso una expresión del tipo "...(-sin..." ó "...(-x..."
root = new exp_node;                               // será tratada como "..(-1*sin...." y  "...(-1*x...."
root->type = CONST;
root->left = 0;
root->rigth = 0;
root->c_const = -1.0000000000000000000;
pila_nod.push(root);

while ( !pila_op.empty() && pila_op.top() > RESTA )
{
root = new exp_node;
root->type = pila_op.top();
if  ( root->type < SIN )
{
root->rigth = pila_nod.top(); pila_nod.pop();
root->left = pila_nod.top(); pila_nod.pop();
}
else
{
root->left = pila_nod.top(); pila_nod.pop();
root->rigth = 0;
}
pila_nod.push(root);
pila_op.pop();
}
pila_op.push(MULT);
++pos;
}
else if ( in_exp[pos] == '-' ) // Ej: "....x-y..."     operador '-' binario
{
while ( !pila_op.empty() && pila_op.top() != PAR )
{
root = new exp_node;
root->type = pila_op.top();

if  ( root->type < SIN )
{
root->rigth = pila_nod.top(); pila_nod.pop();
root->left  = pila_nod.top(); pila_nod.pop();
}
else
{
root->left  = pila_nod.top(); pila_nod.pop();
root->rigth = 0;
}
pila_nod.push(root);
pila_op.pop();
}
pila_op.push(RESTA);
++pos;
}
else if ( in_exp[pos] == '+' ) // Ej: "....x+y..."     operador '+' binario
{
while ( !pila_op.empty() && pila_op.top() != PAR )
{
root = new exp_node;
root->type = pila_op.top();
if  ( root->type < SIN )
{
root->rigth = pila_nod.top(); pila_nod.pop();
root->left = pila_nod.top(); pila_nod.pop();
}
else
{
root->left = pila_nod.top(); pila_nod.pop();
root->rigth = 0;
}
pila_nod.push(root);
pila_op.pop();
}
pila_op.push(SUMA);
++pos;
}
else if ( in_exp[pos] == '/' )// Ej: "....x/y..."     operador '/' binario
{
while ( !pila_op.empty() && pila_op.top() > RESTA )
{
root = new exp_node;
root->type = pila_op.top();
if  ( root->type < SIN )
{
root->rigth = pila_nod.top(); pila_nod.pop();
root->left = pila_nod.top(); pila_nod.pop();
}
else
{
root->left = pila_nod.top(); pila_nod.pop();
root->rigth = 0;
}
pila_nod.push(root);
pila_op.pop();
}
pila_op.push(DIV);
++pos;
}
else if ( in_exp[pos] == '*' )// Ej: "....x*y..."     operador '*' binario
{
while ( !pila_op.empty() && pila_op.top() > RESTA )
{
root = new exp_node;
root->type = pila_op.top();
if  ( root->type < SIN )
{
root->rigth = pila_nod.top(); pila_nod.pop();
root->left = pila_nod.top();  pila_nod.pop();
}
else
{
root->left = pila_nod.top(); pila_nod.pop();
root->rigth = 0;
}
pila_nod.push(root);
pila_op.pop();
}
pila_op.push(MULT);
++pos;
}
else if ( in_exp[pos] == '^' ) // Ej: "....x^y..."     operador '^' binario
{
while ( !pila_op.empty() && pila_op.top() > DIV )
{
root = new exp_node;
root->type = pila_op.top();
if  ( root->type == POT )
{
root->rigth = pila_nod.top(); pila_nod.pop();
root->left = pila_nod.top(); pila_nod.pop();
}
else
{
root->left = pila_nod.top(); pila_nod.pop();
root->rigth = 0;
}
pila_nod.push(root);
pila_op.pop();
}
pila_op.push(POT);
++pos;
}
else  // operadores unarios o funciones
{
i = pos;
while ( in_exp[pos] != '(' ) ++pos;

tmp_str = in_exp.substr(i, pos-i);

if (tmp_str == "sin" )
pila_op.push(SIN);

else if (tmp_str == "cos" )
pila_op.push(COS);

else if (tmp_str == "tan" )
pila_op.push(TAN);

else if (tmp_str == "atan" )
pila_op.push(ATAN);

else if (tmp_str == "exp" )
pila_op.push(EXP);

else if (tmp_str == "sinh" )
pila_op.push(SINH);

else if (tmp_str == "cosh" )
pila_op.push(COSH);

else if (tmp_str == "abs" )
pila_op.push(ABS);

else if (tmp_str == "ln" )
pila_op.push(LN);

else if (tmp_str == "lg" )
pila_op.push(LG);

else if (tmp_str == "asin" )
pila_op.push(ASIN);

else if (tmp_str == "acos" )
pila_op.push(ACOS);
else if (tmp_str == "sqrt")
pila_op.push(SQRT);
/*se pueden añadir más funciones, poniendo un nuevo else if ()
  y modificando el 'enun type_node' y la función 'eval_tree(..)' */

}
}

while ( !pila_op.empty() )
{
root = new exp_node;
root->type = pila_op.top();

if ( root->type < SIN )
{
root->rigth = pila_nod.top(); pila_nod.pop();
root->left = pila_nod.top(); pila_nod.pop();
}
else
{
root->left = pila_nod.top(); pila_nod.pop();
root->rigth = 0;
}
pila_op.pop();
pila_nod.push(root);
}

root  = pila_nod.top(); pila_nod.pop();

}

//////////////////////////////////////////
// IMPLEMENTACION DE LA CLASE pilaNode  //
//////////////////////////////////////////
void pilaNode::pop()
{
    if (!n)
        return;
    else
    {
        node *ptr_tmp = head->next;  //se guarda la dirección del segundo nodo
        delete head;                 //se borra el nodo de la cabecera
        head = ptr_tmp;              //se restablece la cabecera al segundo nodo
        --n;
    }       
}

void pilaNode::push(exp_node *ptr)
{

    if (!n)
    {
       
        head = new node;   
        head->ptr = ptr;
        head->next = 0;
        ++n;
    }
    else
    {
        node *ptr_tmp = new node;
        ptr_tmp->next = head;
        head = ptr_tmp;
        head->ptr = ptr;
        ++n;               
    }
}

pilaNode::~pilaNode()
{
        node *ptr_tmp = head;
        while (ptr_tmp)             //mientras que no se encuentre el final de la lista
        {
            ptr_tmp = head->next;   //ptr_tmp apunta al nodo siguiente
            delete head;            //se borra el nodo actual
            head = ptr_tmp;         //head y ptr_tmp vuelven a apuntar al mismo nodo (el siguinte)
        }
}

//////////////////////////////////////////
// IMPLEMENTACION DE LA CLASE pilaOp    //
//////////////////////////////////////////
void pilaOp::pop()
{
    if (!n)
        return;
    else
    {
        node *ptr_tmp = head->next;
        delete head;
        head = ptr_tmp;
        --n;
    }       
}

void pilaOp::push(type_node value)
{

    if (!n)
    {      
        head = new node;   
        head->value = value;
        head->next = 0;
        ++n;
    }
    else
    {
        node *ptr_tmp = new node;
        ptr_tmp->next = head;
        head = ptr_tmp;
        head->value = value;
        ++n;               
    }
}

pilaOp::~pilaOp()
{
        node *ptr_tmp = head;
        while (ptr_tmp)
        {
            ptr_tmp = head->next;
            delete head;
            head = ptr_tmp;
        }
}

};