#ifndef __EXPRESSION_AMV
	#define __EXPRESSION_AMV

/*
Clase para representar una expresión matemática. El tipo para construir la expresión debe
contar con los siguientes operadores:
+ para la suma
- para la resta
* para multiplicación
/ para la división
^ para la potenciación

aparte de esto, si cuenta con funciones que apliquen sobre sus instancias (del tipo), deben tener
el siguiente prototipo:

tipo nombre_funcion(const tipo &t);

De esta manera, una expresión válida sería:

x+5*sin(4)

	donde: - la función sin() está definida para el tipo con el que se construyó la expresión
			- se puede crear una variable del tipo en cuestión, a partir de una constante numérica

El operador - monario no está implementado todavía, no intente usarlo


	P.I.S.C. Ariel Alonzo Medina Vázquez - 21 de diciembre del 2003

*/

#include <iostream>
#include <strstream>
#include <sstream>
#include <cctype>
#include <string>
#include <fstream>
#include "algorithm.h"
#include "stringAMV.h"
#include "REEvaluator.h"
#include "binaryTree.h"
#include "vector.h"
#include "deque.h"
#include "exception.h"
#include "function.h"
#include "variable.h"
#include "mathAMV.h"
#include "amvdefs.h"

namespace amv	{

template <class X, class s>
X fact1(const X &e);

template <class X, class s>
X exp(const X &e);

template <class X, class s>
X log(const X &e);

template <class X, class s>
X ln(const X &e);

template <class X, class s>
X sin(const X &e);

template <class X, class s>
X sinh(const X &e);

template <class X, class s>
X asin(const X &e);

template <class X, class s>
X cos(const X &e);

template <class X, class s>
X cosh(const X &e);

template <class X, class s>
X acos(const X &e);

template <class X, class s>
X tan(const X &e);

template <class X, class s>
X tanh(const X &e);

template <class X, class s>
X atan(const X &e);

template <class X, class s>
X ctg(const X &e);

template <class X, class s>
X actg(const X &e);

template <class X, class s>
X sec(const X &e);

template <class X, class s>
X asec(const X &e);

template <class X, class s>
X csc(const X &e);

template <class X, class s>
X acsc(const X &e);

template <class X, class s>
X min(const X &e1, const X &e2);

template <class X, class s>
X max(const X &e1, const X &e2);

template <class X, class s>
X pow(const X &e1, const X &e2);

template <class X, class s>
X root(const X &e1, const X &e2);

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
class expression;

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
bool compare(const expression<type,ptf,ptv> &e1, const expression<type,ptf,ptv> &e2);

/*
template <class type>
bool compare(const type &e1, const type &e2);
*/
int precedence(char Operator);//Para uso de una expresión construida
int precedence(char Operator, bool unary);//para construir la expresión
bool associatesByLeft(char Operator);
int cost(char Operator);

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
class expression	{
	protected:
	
	class infoPatternNode;

	class expressionNode	{
	public:
		enum value_type	{ OPERATOR, FUNCTION, NUMBER,VARIABLE };
		value_type vt;
		union	{
			char Operator;
			const function<type> *pFunction;
			type *pNumber;
			const variable<type> *pVariable;
		};
		expressionNode *subExpression1, *subExpression2;
		int childs;
		int level;
		bool sign;
		string label;
		bool unary;

		expressionNode(const type &n=type(), bool s=true): vt(NUMBER), pNumber(new type(n)), subExpression1(0),
		subExpression2(0), childs(0), level(0), sign(s)
			{
			}

		expressionNode(const char sourceOperator, bool s=true): vt(OPERATOR), Operator(sourceOperator),
		subExpression1(0), subExpression2(0), childs(0), level(0), sign(s), unary(false)
			{
			}

		expressionNode(const function<type> *pf, bool s=true): vt(FUNCTION), pFunction(pf), subExpression1(0),
		subExpression2(0), childs(0), level(0), sign(s)
			{
			}

		expressionNode(const variable<type> *pv, bool s=true): vt(VARIABLE), pVariable(pv), subExpression1(0),
		subExpression2(0), childs(0), level(0), sign(s)
			{
			}

		expressionNode(const expressionNode &e): vt(e.vt), sign(e.sign)
			{
			if(vt==NUMBER)
				pNumber=new type(*(e.pNumber));
			else if(vt==OPERATOR)
				{
				Operator=e.Operator;
				unary=e.unary;
				}
			else if(vt==FUNCTION)
				pFunction=e.pFunction;
			else if(vt==VARIABLE)
				pVariable=e.pVariable;
			if(e.subExpression1)
				subExpression1=new expressionNode(*(e.subExpression1));
			else
				subExpression1=0;
			if(e.subExpression2)
				subExpression2=new expressionNode(*(e.subExpression2));
			else
				subExpression2=0;
			childs=e.childs;
			setExpressionLevel();
			}

		expressionNode(char sourceOperator, const expressionNode &op1, const expressionNode &op2, bool s=true):
		vt(OPERATOR), Operator(sourceOperator),
		subExpression1(new expressionNode(op1)),
		subExpression2(new expressionNode(op2)),
		childs(op1.childs+op2.childs+2), level(0), sign(s), unary(false)
			{
			setExpressionLevel();
			}

		expressionNode(const expressionNode *pattern,const deque<expressionNode> &ds, const deque<expressionNode> &dn):
		vt(pattern->vt), subExpression1(0), subExpression2(0), childs(0), level(0), sign(pattern->sign)
			{
			if(vt==NUMBER)
				pNumber=new type(*(pattern->pNumber));
			else if(vt==OPERATOR)
				{
				Operator=pattern->Operator;
				unary=pattern->unary;
				}
			else if(vt==FUNCTION)
				pFunction=pattern->pFunction;
			else if(vt==VARIABLE)
				{
				for(int i=0; i<ds.size(); ++i)
					{
					if(pattern->pVariable->getName()==ds[i].pVariable->getName())
						{
						if(sign)
							*this=dn[i];
						else
							*this=-dn[i];
						break;
						}
					}
				return;
				}
			if(pattern->subExpression1)
				{
				subExpression1=new expressionNode(pattern->subExpression1,ds,dn);
				childs+=subExpression1->childs+1;
				}
			else
				subExpression1=0;
			if(pattern->subExpression2)
				{
				subExpression2=new expressionNode(pattern->subExpression2,ds,dn);
				childs+=subExpression2->childs+1;
				}
			else
				subExpression2=0;
			setExpressionLevel();
			}

		void clear()
			{
			if(vt==NUMBER)
				delete pNumber;

			delete subExpression1;
			delete subExpression2;
			}

		~expressionNode()
			{
			clear();
			}

		expressionNode &operator=(const expressionNode &e)
			{
			clear();

			vt=e.vt;
			if(vt==NUMBER)
				pNumber=new type(*(e.pNumber));
			else if(vt==OPERATOR)
				{
				Operator=e.Operator;
				unary=e.unary;
				}
			else if(vt==FUNCTION)
				pFunction=e.pFunction;
			else if(vt==VARIABLE)
				pVariable=e.pVariable;
			if(e.subExpression1)
				subExpression1=new expressionNode(*(e.subExpression1));
			else
				subExpression1=0;
			if(e.subExpression2)
				subExpression2=new expressionNode(*(e.subExpression2));
			else
				subExpression2=0;
			childs=e.childs;
			setExpressionLevel();
			sign=e.sign;
		
			return *this;
			}

		type getNumber() const
			{
			return (sign? *pNumber: -(*pNumber));
			}

		expressionNode operator-() const
			{
			static expressionNode zero;
			if(*this==zero)
				return *this;

			if(vt==NUMBER)
				{
				if(sign)
					return expressionNode(-(*pNumber));
				else
					return expressionNode(*pNumber);
				}
			else
				{
				expressionNode temp(*this);
				temp.sign=!temp.sign;
				return temp;
				}
			}

		expressionNode abs() const
			{
			if(sign)
				return *this;
			else
				{
				expressionNode temp(*this);
				temp.sign=true;

				return temp;
				}
			}

//Busca una parte del árbol que coincida exactamente con el patrón, rápida pero no siempre encuentra
//el patrón, ya que pueden haber factores o sumandos conmutados

		const expressionNode *findEqualPattern(const expressionNode &e) const
			{
			deque<expressionNode> dr,df;
			if(this->findEqualStructure(e,dr,df))
				{
				return this;
				}
			else
				{
				const expressionNode *p;
				if(subExpression1 && !subExpression2)
					{
					if(p=subExpression1->findEqualPattern(e))
						return p;
					else
						return 0;
					}
				else if(!subExpression1 && subExpression2)
					{
					if(p=subExpression2->findEqualPattern(e))
						return p;
					else
						return 0;
					}
				else if(subExpression1 && subExpression2)
					{
					if(p=subExpression1->findEqualPattern(e))
						return p;
					else if(p=subExpression2->findEqualPattern(e))
						return p;
					else
						return 0;
					}
				else
					return 0;
				}
			}

//Hace una búsqueda exhaustiva del patrón, aún cuando haya factores o sumandos conmutados, trata
//de encontrarlo

		const expressionNode *findEquivalentPattern(const expressionNode &e, deque<infoPatternNode> &info) const
			{
			deque<expressionNode> dr,df;
			expressionNode *oF=0, *oT=0;
			if(this->findEquivalentStructure(e,dr,df,'\0',0,oF,oT))
				{
				info.push_back(infoPatternNode(this,&e,0,df,dr,oF,oT));
				delete oF;
				delete oT;
				//¿Se debería buscar este patrón también en los hijos, aunque ya se haya encontrado aquí?
				return this;
				}
			else
				{
				const expressionNode *p;
				if(subExpression1 && !subExpression2)
					{
					if(p=subExpression1->findEquivalentPattern(e,info))
						return p;
					else
						return 0;
					}
				else if(!subExpression1 && subExpression2)
					{
					if(p=subExpression2->findEquivalentPattern(e,info))
						return p;
					else
						return 0;
					}
				else if(subExpression1 && subExpression2)
					{
					if(p=subExpression1->findEquivalentPattern(e,info))
						return p;
					else if(p=subExpression2->findEquivalentPattern(e,info))
						return p;
					else
						return 0;
					}
				else
					return 0;
				}
			}

//Usada por findEqualPattern()

		const expressionNode *findEqualStructure(const expressionNode &e, deque<expressionNode> &dr, deque<expressionNode> &df) const
			{
			if(e.isOperator() && isOperator() && e.getOperator()==getOperator())
				{//se supone que todos los operadores son binarios
				const expressionNode *p1,*p2;

				if((e.getSign()==getSign()) &&
					(p1=subExpression1->findEqualStructure(*(e.subExpression1),dr,df)) &&
					(p2=subExpression2->findEqualStructure(*(e.subExpression2),dr,df)))
					return this;
				else
					return 0;
				}
			else if(e.isOperator() && isOperator() && e.getOperator()!=getOperator())
				{
				return 0;
				}
			else if(e.isOperator() && !isOperator())
				{
				return 0;
				}
			else if(e.isVariable())
				{
				bool found=false;
				for(deque<expressionNode>::size_type i=0; i<df.size(); ++i)
					{
					if(df[i]==e.abs())
						{
						found=true;
						break;
						}
					}

				if(found)
					{
					if(e.sign)
						{
						if(dr[i]==*this)
							return this;
						else
							return 0;
						}
					else
						{
						if(dr[i]==-*this)
							return this;
						else
							return 0;
						}
					}
				else
					{
/*					if(isVariable())//cuando sean variable(patrón) y variable(expresión)
						{//deberán ser iguales hasta en el signo
						if(e.sign==sign)
							{
							if(e.sign)
								{
								dr.push_back(*this);
								df.push_back(e);
								}
							else
								{
								dr.push_back(-*this);
								df.push_back(e.abs());
								}

							return this;
							}
						else
							return 0;
						}
					else
						{*/
						if(e.sign)
							{
							dr.push_back(*this);
							df.push_back(e);
							}
						else
							{
							dr.push_back(-*this);
							df.push_back(e.abs());
							}

						return this;
						//}
					}
				}
			else if(e.isNumber() && isNumber() && e.getNumber()==getNumber())
				{
				return this;
				}
			else if(e.isNumber() && isNumber() && !(e.getNumber()==getNumber()))
				{
				return 0;
				}
			else if(e.isNumber() && !isNumber())
				{
				return 0;
				}
			else if(e.isFunction() && isFunction() && e.pFunction->getName()==pFunction->getName())
				{
				const expressionNode *p1;
				if((e.getSign()==getSign()) && (p1=subExpression1->findEqualStructure(*(e.subExpression1),dr,df)))
					return this;
				else
					return 0;
				}
			else if(e.isFunction() && isFunction() && !(e.pFunction->getName()==pFunction->getName()))
				{
				return 0;
				}
			else if(e.isFunction() && !isFunction())
				{
				return 0;
				}
			}

//Usada por findEquivalentPattern()

		const expressionNode *findEquivalentStructure(const expressionNode &e, deque<expressionNode> &dr, deque<expressionNode> &df, char lastop, int currentDepth, expressionNode * &oF, expressionNode * &oT) const
			{
			static expressionNode zero;//peligroso si hay un sumando o un factor 0
			if(e.isOperator() && isOperator() && e.getOperator()==getOperator())
				{
				const expressionNode *p1,*p2;

				if(getOperator()=='*')
					{//el orden de los factores no altera el producto
					deque<expressionNode> factors1, factors2;
					getFactors(factors1,level);
					e.getFactors(factors2,e.level);
					if(lastop=='+' || lastop=='=' || currentDepth>0)
						{
						if(factors1.size()!=factors2.size())
							return 0;
						else
							{
							int nper=fact(factors1.size());
							deque<expressionNode> factors3(factors1);
							int found=0;
							const expressionNode *p;
							//deque<expressionNode> dr,df;
							int sd=dr.size();
							for(int k=0; k<nper;)
								{
								for(int i=0; i<factors2.size(); ++i)
									{
									for(int j=0; j<factors3.size(); ++j)
										{
										if(factors3[j]==zero)
											continue;
										if(p=factors3[j].findEquivalentStructure(factors2[i],dr,df,'=',currentDepth+1,oF,oT))//buscaremos igualdad de factores en las demas llamadas
											{
											++found;
											factors3[j]=zero;
											break;
											}
										}
									}
								if(found==factors2.size())
									return this;
								else
									{
									while(dr.size()!=sd)
										{
										dr.pop_back();
										df.pop_back();
										}
									//return 0;
									++k;
									if(k<nper)
										{
										permutk(factors1,factors3,k);
										found=0;
										}
									else
										return 0;
									}
								}
							}
						}
					else
						{
						if(factors1.size()<factors2.size())
							return 0;
						else
							{
							int nper=fact(factors1.size());
							deque<expressionNode> factors3(factors1);
							deque<bool> selectedFactors(factors3.size());
							int found=0;
							const expressionNode *p;
							//deque<expressionNode> dr,df;
							int sd=dr.size();
							for(int k=0; k<nper;)
								{
								fill(selectedFactors,false);
								for(int i=0; i<factors2.size(); ++i)
									{
									for(int j=0; j<factors3.size(); ++j)
										{
										if(selectedFactors[j])
											continue;
										if(p=factors3[j].findEquivalentStructure(factors2[i],dr,df,'*',currentDepth+1,oF,oT))
											{
											++found;
											selectedFactors[j]=true;
											break;
											}
										}
									}
								if(found>=factors2.size())//==
									{
									if(count(selectedFactors,false))
										{
										deque<bool>::size_type index=findIndex(selectedFactors,false);
										oF=new expressionNode(factors3[index]);
										++index;
										for(;index<selectedFactors.size(); ++index)
											{
											if(!selectedFactors[index])
												(*oF)*=factors3[index];
											}
										}
									return this;
									}
								else
									{
									while(dr.size()!=sd)
										{
										dr.pop_back();
										df.pop_back();
										}
									//return 0;
									++k;
									if(k<nper)
										{
										permutk(factors1,factors3,k);
										found=0;
										}
									else
										return 0;
									}
								}
							}
						}
					}
				else if(getOperator()=='+')
					{//el orden de los sumandos no altera la suma
					deque<expressionNode> terms1, terms2;
					getTerms(terms1,level);
					e.getTerms(terms2,e.level);
					if(lastop=='*' || lastop=='=' || currentDepth>0)
						{
						if(terms1.size()!=terms2.size())
							return 0;
						else
							{
							int nper=fact(terms1.size());
							deque<expressionNode> terms3(terms1);
							int found=0;
							const expressionNode *p;
							//deque<expressionNode> dr,df;
							int sd=dr.size();
							for(int k=0; k<nper;)
								{
								for(int i=0; i<terms2.size(); ++i)
									{
									for(int j=0; j<terms3.size(); ++j)
										{
										if(terms3[j]==zero)
											continue;
										if(p=terms3[j].findEquivalentStructure(terms2[i],dr,df,'=',currentDepth+1,oF,oT))
											{
											++found;
											terms3[j]=zero;
											break;
											}
										}
									}
								if(found==terms2.size())
									return this;
								else
									{
									while(dr.size()!=sd)
										{
										dr.pop_back();
										df.pop_back();
										}
									//return 0;
									++k;
									if(k<nper)
										{
										permutk(terms1,terms3,k);
										found=0;
										}
									else
										return 0;
									}
								}
							}
						}
					else
						{
						if(terms1.size()<terms2.size())
							return 0;
						else
							{
							int nper=fact(terms1.size());
							deque<expressionNode> terms3(terms1);
							deque<bool> selectedTerms(terms3.size());
							int found=0;
							const expressionNode *p;
							//deque<expressionNode> dr,df;
							int sd=dr.size();
							for(int k=0; k<nper;)
								{
								fill(selectedTerms,false);
								for(int i=0; i<terms2.size(); ++i)
									{
									for(int j=0; j<terms3.size(); ++j)
										{
										if(selectedTerms[j])
											continue;
										if(p=terms3[j].findEquivalentStructure(terms2[i],dr,df,'+',currentDepth+1,oF,oT))
											{
											++found;
											selectedTerms[j]=true;
											break;
											}
										}
									}
								if(found>=terms2.size())//==
									{
									if(count(selectedTerms,false))
										{
										deque<bool>::size_type index=findIndex(selectedTerms,false);
										oT=new expressionNode(terms3[index]);
										++index;
										for(;index<selectedTerms.size(); ++index)
											{
											if(!selectedTerms[index])
												(*oT)+=terms3[index];
											}
										}
									return this;
									}
								else
									{
									while(dr.size()!=sd)
										{
										dr.pop_back();
										df.pop_back();
										}
									//return 0;
									++k;
									if(k<nper)
										{
										permutk(terms1,terms3,k);
										found=0;
										}
									else
										return 0;
									}
								}
							}
						}
					}
				else
					{//********* No considerar el getSign() para los operadores '+' y '*' (anteriores)
					//porque getFactors() y getTerms() los consideran
					if((e.getSign()==getSign()) &&
					(p1=subExpression1->findEquivalentStructure(*(e.subExpression1),dr,df,'\0',currentDepth+1,oF,oT)) &&
						(p2=subExpression2->findEquivalentStructure(*(e.subExpression2),dr,df,'\0',currentDepth+1,oF,oT)))
						return this;
					else
						return 0;
					}
				}
			else if(e.isOperator() && isOperator() && e.getOperator()!=getOperator())
				{
				return 0;
				}
			else if(e.isOperator() && !isOperator())
				{
				return 0;
				}
			else if(e.isVariable())
				{
				bool found=false;
				deque<expressionNode>::size_type i;
				for(i=0; i<df.size(); ++i)
					{
					if(df[i]==e.abs())
						{
						found=true;
						break;
						}
					}

				if(found)
					{
					if(e.sign)
						{
						if(dr[i]==*this)
							return this;
						else
							return 0;
						}
					else
						{
						if(dr[i]==-*this)
							return this;
						else
							return 0;
						}
					}
				else
					{
/*					if(isVariable())//cuando sean variable(patrón) y variable(expresión)
						{//deberán ser iguales hasta en el signo
						if(e.sign==sign)
							{
							if(e.sign)
								{
								dr.push_back(*this);
								df.push_back(e);
								}
							else
								{
								dr.push_back(-*this);
								df.push_back(e.abs());
								}

							return this;
							}
						else
							return 0;
						}
					else
						{*/
						if(e.sign)
							{
							dr.push_back(*this);
							df.push_back(e);
							}
						else
							{
							dr.push_back(-*this);
							df.push_back(e.abs());
							}

						return this;
						//}
					}
				}
			else if(e.isNumber() && isNumber() && e.getNumber()==getNumber())
				{
				return this;
				}
			else if(e.isNumber() && isNumber() && !(e.getNumber()==getNumber()))
				{
				return 0;
				}
			else if(e.isNumber() && !isNumber())
				{
				return 0;
				}
			else if(e.isFunction() && isFunction() && e.pFunction->getName()==pFunction->getName())
				{
				const expressionNode *p1;
				if((e.getSign()==getSign()) && (p1=subExpression1->findEquivalentStructure(*(e.subExpression1),dr,df,'\0',currentDepth+1,oF,oT)))
					return this;
				else
					return 0;
				}
			else if(e.isFunction() && isFunction() && !(e.pFunction->getName()==pFunction->getName()))
				{
				return 0;
				}
			else if(e.isFunction() && !isFunction())
				{
				return 0;
				}
			}

//************
		
		//requiere que las etiquetas ya esten puestas setLabel();
		bool isChild(const expressionNode &e) const
			{
			if(e.label.size()<=label.size())
				return false;
			
			return equal(label.begin(),label.end(),e.label.begin());
			}

		//requiere que las etiquetas ya esten puestas setLabel();
		void substitute(const string &s, const expressionNode &e)
			{
			string::const_iterator i=s.begin();
			expressionNode *p=this;
			if(i==s.end())
				return;

			while(true)
				{
				++i;
				if(i==s.end())
					{
					*p=e;
					break;
					}

				if(*i=='1' && p->subExpression1)
					p=p->subExpression1;
				else if(*i=='2' && p->subExpression2)
					p=p->subExpression2;
				else
					return;
				}
			setLabel();
			}

		expressionNode doExplicitPlusSign() const
			{
			if(vt==NUMBER)
				return *this;
			else if(vt==VARIABLE)
				return *this;
			else if(vt==FUNCTION)
				return *this;
			else if(vt==OPERATOR)
				{
				if(Operator=='-')
					{
					expressionNode temp(-(*subExpression2));
					return expressionNode('+',subExpression1->doExplicitPlusSign(),temp.doExplicitPlusSign(),sign);
					}
				else
					return expressionNode(Operator,subExpression1->doExplicitPlusSign(),subExpression2->doExplicitPlusSign(),sign);
				}
			}

		void setLabel(expressionNode *p=0)
			{
			if(p)
				{
				if(p->subExpression1==this)
					label=p->label+"1";
				else
					label=p->label+"2";
				}
			else
				label="0";

			if(subExpression1)
				subExpression1->setLabel(this);
			if(subExpression2)
				subExpression2->setLabel(this);
			}

		const string &getLabel() const
			{
			return label;
			}

		void setExpressionLevel(expressionNode *p=0)
			{
			//establece los niveles de expresión a los que pertenecen los nodos
			//permite obtener los terminos y los factores para la simplificacion
			//también sirve para parentizar cuando se vuelca a un flujo
			if(p)
				{
				if(vt==OPERATOR && p->vt==OPERATOR)
					{
					if(precedence(Operator)<precedence(p->Operator))
						level=p->level+1;
					else if(precedence(Operator)==precedence(p->Operator))
						{
						//if(!associatesByLeft(Operator) ||
						//(Operator=='*' && p->Operator=='/' &&
						if((!associatesByLeft(Operator) && this==p->subExpression1)||
						(p->Operator=='/' &&
						this==p->subExpression2))
							level=p->level+1;
						else
							level=p->level;
						}
					else
						level=p->level;
					}
				else
					level=p->level;
				}
			else
				level=0;

			if(subExpression1)
				subExpression1->setExpressionLevel(this);
			if(subExpression2)
				subExpression2->setExpressionLevel(this);

			}

		const expressionNode &getExponent() const
			{
			return *subExpression2;
			}

		const expressionNode &getBase() const
			{
			if(vt==OPERATOR && Operator=='^')
				return *subExpression1;
			else
				return *this;
			}

		expressionNode reduceSimilarTerms() const
			{
			deque<expressionNode> d,results;
			getTerms(d,level);
			type c1,c2, one(true), tzero(false), mOne(-one);
			expressionNode f1,f2, zero;
			bool hasCo1,hasCo2;
			deque<expressionNode>::size_type i;

			for(i=0; i<d.size()-1; ++i)
				{
				if(d[i]==zero)
					continue;
				for(deque<expressionNode>::size_type j=i+1; j<d.size(); ++j)
					{
					if(d[j]==zero)
						continue;
					if(d[i].vt==NUMBER && d[j].vt==NUMBER)
						{
						type result=d[i].getNumber()+d[j].getNumber();
						if(result==tzero)
							{
							d[i]=zero;
							d[j]=zero;
							break;
							}
						else
							{
							d[i]=expressionNode(result);
							d[j]=zero;
							continue;
							}
						}
					if(d[i]==d[j])
						{
						d[i]=expressionNode('*',type(2),d[i]);
						d[j]=zero;
						continue;
						}
					if(d[i]==-(d[j]))
						{
						d[i]=zero;
						d[j]=zero;
						break;
						}

					hasCo1=d[i].getCoefficient(c1,f1);
					hasCo2=d[j].getCoefficient(c2,f2);
					if(hasCo1 || hasCo2)
						{
						if(hasCo1 && !hasCo2)
							{
							c2=one;
							f2=d[j];
							}
						else if(!hasCo1 && hasCo2)
							{
							c1=one;
							f1=d[i];
							}
						if(f1==f2)
							{
							type result=c1+c2;
							if(result==one)
								d[i]=f1;
							else if(result==mOne)
								d[i]=-f1;
							else if(result==tzero)
								{
								d[i]=zero;
								d[j]=zero;
								break;
								}
							else
								d[i]=expressionNode('*',result,f1);
							d[j]=zero;
							}
						else if(f1==-f2)
							{
							if(!f1.sign)
								{
								c1=-c1;
								type result=c1+c2;
								if(result==one)
									d[i]=f2;
								else if(result==mOne)
									d[i]=-f2;
								else if(result==tzero)
									{
									d[i]=zero;
									d[j]=zero;
									break;
									}
								else
									d[i]=expressionNode('*',result,f2);
								}
							else
								{
								c2=-c2;
								type result=c1+c2;
								if(result==one)
									d[i]=f1;
								else if(result==mOne)
									d[i]=-f1;
								else if(result==tzero)
									{
									d[i]=zero;
									d[j]=zero;
									break;
									}
								else
									d[i]=expressionNode('*',result,f1);
								}
							d[j]=zero;
							}
						}
					}
				}
	
			for(i=0; i<d.size(); ++i)
				{
				if(!(d[i]==zero))
					results.push_back(d[i]);
				}
			if(d.size()==results.size())
				return *this;
			else
				return gatherTerms(results);
			}

		bool getCoefficient(type &c,expressionNode &f) const
			{
			if(vt==NUMBER)
				return false;

			type coefficient(true);
			deque<expressionNode> d, factors;
			getFactors(d,level);
			deque<expressionNode>::size_type n=0;
			for(deque<expressionNode>::size_type i=0; i<d.size(); ++i)
				{
				if(d[i].vt==NUMBER)
					{
					coefficient=coefficient*(*(d[i].pNumber));
					++n;
					}
				else
					factors.push_back(d[i]);
				}

			if(n)
				{
				c=coefficient;
				f=gatherFactors(factors);

				return true;
				}

			return false;
			}

		bool hasExplicitCoefficient(type &t) const
			{
			if(vt==OPERATOR && Operator=='*')
				{
				if(subExpression1->vt==NUMBER)
					{
					t=*(subExpression1->pNumber);
					return true;
					}
				else if(subExpression2->vt==NUMBER)
					{
					t=*(subExpression2->pNumber);
					return true;
					}
				else if(subExpression1->hasExplicitCoefficient(t))
					return true;
				else if(subExpression2->hasExplicitCoefficient(t))
					return true;
					
				return false;
				}
			else if(vt==OPERATOR && Operator=='/' && subExpression1->hasExplicitCoefficient(t))
				return true;
			else
				return false;
			}

		//************ Pendientes de esta función *****************
		void getTerms(deque<expressionNode> &d, int l) const
			{
			getTerms1(d,l);
			if(level==l && isOperator() && (Operator=='+' || Operator=='-') && !sign)
				{
				for(deque<expressionNode>::iterator it=d.begin(); it!=d.end(); ++it)
					it->sign=!it->sign;
				}
			}

		void getTerms1(deque<expressionNode> &d, int l) const
			{
			if(level==l && vt==OPERATOR)
				{//*********** Considerar si el '+' está negado y negar cada término (getTerms())
				if(Operator=='+')
					{
					subExpression1->getTerms1(d,l);
					subExpression2->getTerms1(d,l);
					return;
					}
				else if(Operator=='-')
					{
					expressionNode temp(*subExpression2);
					temp.sign=!temp.sign;
					subExpression1->getTerms1(d,l);
					temp.getTerms1(d,l);
					return;
					}
				else
					{
					d.push_back(*this);
					return;
					}
				}
			else if(level==l && vt!=OPERATOR)
				{
				d.push_back(*this);
				return;
				}
			else if(level>l)
				{
				d.push_back(*this);
				return;
				}
			}

		void getFactors(deque<expressionNode> &d, int l) const
			{
			if(level==l && vt==OPERATOR)
				{
				if(Operator=='*')
					{
					if(!sign)
						{
						expressionNode temp(*subExpression1);
						temp.sign=false;
						temp.getFactors(d,l);
						subExpression2->getFactors(d,l);
						}
					else
						{
						subExpression1->getFactors(d,l);
						subExpression2->getFactors(d,l);
						}

					return;
					}
				else if(Operator=='/')
					{
					expressionNode temp('/');
					temp.sign=sign;
					subExpression1->getFactors(d,l);
//					temp.getTerms(d,l);
					temp.subExpression1=new expressionNode(d.back());
					d.pop_back();
					temp.subExpression2=new expressionNode(*subExpression2);
					temp.childs=temp.subExpression1->childs+temp.subExpression2->childs+2;
					d.push_back(temp);

					return;
					}
				else
					{
					d.push_back(*this);
					return;
					}
				}
			else if(level==l && vt!=OPERATOR)
				{
				d.push_back(*this);
				return;
				}
			else if(level>l)
				{
				d.push_back(*this);
				return;
				}
			}

		bool isFactor(const expressionNode &e) const
			{
			deque<expressionNode> dn;
			getFactors(dn,level);
			for(deque<expressionNode>::iterator it=dn.begin(); it!=dn.end(); ++it)
				{
				if(e.getBase()==it->getBase())
					return true;
				}

			return false;
			}

		expressionNode &operator+=(const expressionNode &e)
			{
			expressionNode temp('+',*this,e);
			*this=temp;

			return *this;
			}

		expressionNode &operator*=(const expressionNode &e)
			{
			expressionNode temp('*',*this,e);
			*this=temp;

			return *this;
			}

		expressionNode operator*(const expressionNode &e) const
			{
			expressionNode temp(*this);
			temp*=e;

			return temp;
			}

		expressionNode gatherTerms(const deque<expressionNode> &d) const
			{
			if(!d.size())
				return expressionNode();
			if(d.size()==1)
				return d[0];

			expressionNode temp(d[0]);

			for(deque<expressionNode>::size_type i=1; i<d.size(); ++i)
				temp+=d[i];

			return temp;
			}

		expressionNode gatherFactors(const deque<expressionNode> &d) const
			{
			if(!d.size())
				return expressionNode(type(true));
			if(d.size()==1)
				return d[0];

			expressionNode temp(d[0]);

			for(deque<expressionNode>::size_type i=1; i<d.size(); ++i)
				temp*=d[i];

			return temp;
			}

		bool operator<(const expressionNode &e) const
			{
			if(vt==NUMBER && e.vt==NUMBER)
				return (*pNumber<*(e.pNumber));
			else if(vt==NUMBER && (e.vt==VARIABLE || e.vt==FUNCTION))
				return true;
			else if(vt==VARIABLE && e.vt==NUMBER)
				return false;
			else if(vt==VARIABLE && e.vt==VARIABLE)
				return (pVariable->getName()<e.pVariable->getName());
			else if(vt==FUNCTION && (e.vt==VARIABLE || e.vt==NUMBER))
				return false;
			else if(vt==VARIABLE && e.vt==FUNCTION)
				return true;
			else if(vt==FUNCTION && e.vt==FUNCTION)
				return (pFunction->getName()<e.pFunction->getName());
			else
				{
				if(vt==OPERATOR && e.vt!=OPERATOR)
					return false;
				else if(e.vt==OPERATOR && vt!=OPERATOR)
					return true;
				else
					{
					ostrstream os1, os2;
					os1<<*this<<ends;
					os2<<e<<ends;

					char *p1=os1.str(), *p2=os2.str();
					string s1(p1), s2(p2);
					delete [] p1;
					delete [] p2;

					return s1<s2;
					}
				}
			}

		expressionNode &normalize()
			{
			if(vt==NUMBER)
				{
				if(!sign)
					{
					sign=true;
					*pNumber=-*(pNumber);

					return *this;
					}
				else
					return *this;
				}
			else if(vt==VARIABLE)
				return *this;
			else if(vt==FUNCTION)
				{
				subExpression1->normalize();
				childs=subExpression1->childs+1;
				setExpressionLevel();

				return *this;
				}
			else if(vt==OPERATOR)
				{
//				subExpression1->normalize();
//				subExpression2->normalize();

				if(Operator=='+' || Operator=='-')
					{
					deque<expressionNode> d;
					getTerms(d,level);
					for(deque<expressionNode>::size_type i=0; i<d.size(); ++i)
						{
						d[i].normalize();
						}
					sort(d.begin(),d.end());
					*this=gatherTerms(d);

					return *this;
					}
				else if(Operator=='*')
					{
					type c;
					expressionNode f;
					bool hasCo=getCoefficient(c,f);
					if(hasCo)
						{
						if(!f.sign)
							{
							expressionNode temp('*',-c,-f);
							deque<expressionNode> d;
							temp.getFactors(d,temp.level);
							for(deque<expressionNode>::size_type i=0; i<d.size(); ++i)
								{
								d[i].normalize();
								}
							sort(d.begin(),d.end());
							*this=gatherFactors(d);

							return *this;
							}
						}

					deque<expressionNode> d;
					getFactors(d,level);
					for(deque<expressionNode>::size_type i=0; i<d.size(); ++i)
						{
						d[i].normalize();
						}
					sort(d.begin(),d.end());
					*this=gatherFactors(d);

					return *this;
					}
				else if(Operator=='/')
					{
					subExpression1->normalize();
					subExpression2->normalize();
					childs=subExpression1->childs+subExpression2->childs+2;
					setExpressionLevel();

					return *this;
					}
				else if(Operator=='^')
					{
					subExpression1->normalize();
					subExpression2->normalize();
					childs=subExpression1->childs+subExpression2->childs+2;
					setExpressionLevel();

					return *this;
					}
				}

			return *this;
			}

		expressionNode findFactors() const
			{/*
						deque<expressionNode> factors1, factors2;
						subExpression1->getFactors(factors1,level);
						subExpression2->getFactors(factors2,level);
						for(int i=0; i<factors1.size(); ++i)
							{
							int reps=0;
							for(int j=0; j<factors2.size(); ++j)
								{
//								if(factors1[i]==factors2[j])
								

								}
							}
*/
			}
		
		expressionNode getNumerator() const
			{
			return *subExpression1;
			}

		expressionNode getDenominator() const
			{
			return *subExpression2;
			}

		bool getSign() const
			{
			return sign;
			}

		expressionNode reduceDivision() const
			{//supone que el nodo es el operador '/'
			deque<expressionNode> factors1, factors2, results1, results2;
			expressionNode one(type(true));
			bool sign1(true), sign2(true);
			subExpression1->getFactors(factors1,level);
			if(subExpression2->vt==OPERATOR)
				subExpression2->getFactors(factors2,subExpression2->level);
			else
				subExpression2->getFactors(factors2,level);
			deque<expressionNode>::size_type i;
			for(i=0; i<factors1.size(); ++i)
				{
				if(factors1[i]==one || factors1[i]==-one)
					continue;
				for(deque<expressionNode>::size_type j=0; j<factors2.size(); ++j)
					{
					if(factors2[j]==one || factors2[j]==-one)
						continue;
					if(factors1[i]==factors2[j])
						{
						factors1[i]=one;
						factors2[j]=one;
						break;
						}
					else if(factors1[i]==-factors2[j])
						{
						factors1[i]=-one;
						factors2[j]=one;
						break;
						}
					}
				}
			for(i=0; i<factors1.size(); ++i)
				{
				if(factors1[i]==-one)
					sign1=!sign1;
				else if(!(factors1[i]==one))
					{
					results1.push_back(factors1[i]);
					}
				}
			for(i=0; i<factors2.size(); ++i)
				{
				if(factors2[i]==-one)
					sign2=!sign2;
				else if(!(factors2[i]==one))
					{
					results2.push_back(factors2[i]);
					}
				}
			if(factors1.size()!=results1.size() || factors2.size()!=results2.size())
				{
				if(!sign1 && !sign2)
					{
					sign1=true;
					sign2=true;
					}
				expressionNode temp1(gatherFactors(results1));
				temp1.sign=sign1;
				expressionNode temp2(gatherFactors(results2));
				temp2.sign=sign2;
				//subimos el signo a la division?
				return expressionNode('/',temp1,temp2,sign);
				}
			else
				return *this;
			}

		expressionNode reduceMultiplication() const
			{//supone que se trata del operador '*'
			deque<expressionNode> factors, results;
			expressionNode one(type(true)), exp1,exp2,base1,base2;
			bool sign1(true), sign2(true), sign3(sign);
			getFactors(factors,level);
			deque<expressionNode>::size_type i;

			for(i=0; i<factors.size()-1; ++i)
				{
				if(factors[i]==one || factors[i]==-one)
					continue;
				for(deque<expressionNode>::size_type j=i+1; j<factors.size(); ++j)
					{
					if(factors[j]==one || factors[j]==-one)
						continue;
					if(factors[i].vt==NUMBER && factors[j].vt==NUMBER)
						{
						type result=factors[i].getNumber()*factors[j].getNumber();
						factors[i]=expressionNode(result);
						factors[j]=one;
						continue;
						}

					if(factors[i]==factors[j])
						{
						factors[i]=expressionNode('^',factors[i],type(2));
						//factors[i]=factors[i].reduceExponent() ?
						factors[j]=one;
						continue;
						}
					else if(factors[i]==-factors[j])
						{
						factors[i]=expressionNode('^',(factors[i].sign)? factors[i]: factors[j],type(2));
						//factors[i]=factors[i].reduceExponent() ?
						factors[j]=-one;
						continue;
						}

					if(factors[i].isPower())
						{
						exp1=factors[i].getExponent();
						base1=factors[i].getBase();
						sign1=factors[i].sign;
						}
					else
						{
						exp1=one;
						base1=factors[i];
						sign1=true;
						}
					if(factors[j].isPower())
						{
						exp2=factors[j].getExponent();
						base2=factors[j].getBase();
						sign2=factors[j].sign;
						}
					else
						{
						exp2=one;
						base2=factors[j];
						sign2=true;
						}

					if(base1==base2)
						{
						expressionNode temp3('+',exp1,exp2);
						factors[i]=expressionNode('^',base1,temp3,(sign1==sign2)? true: false);
						//factors[i]=factors[i].reduceExponent() ?
						factors[j]=one;
						continue;
						}
					else if(base1==-base2 && !base1.sign && !factors[i].isPower())
						{
						expressionNode temp3('+',exp1,exp2);
						factors[i]=expressionNode('^',base2,temp3,sign2);
						//factors[i]=factors[i].reduceExponent() ?
						factors[j]=-one;
						continue;
						}
					else if(base1==-base2 && !base2.sign && !factors[j].isPower())
						{
						expressionNode temp3('+',exp1,exp2);
						factors[i]=expressionNode('^',base1,temp3,sign1);
						//factors[i]=factors[i].reduceExponent() ?
						factors[j]=-one;
						continue;
						}

					if(factors[i].isDivision())
						{
						expressionNode temp3('*',factors[j],factors[i].getNumerator());
						expressionNode temp4('/',temp3,factors[i].getDenominator(),factors[i].getSign());
						expressionNode temp5=temp4.reduceDivision();
						if(!(temp5==temp4))
							{
							factors[i]=temp5;
							factors[j]=one;
							}
						}
					else if(factors[j].isDivision())
						{
						expressionNode temp3('*',factors[i],factors[j].getNumerator());
						expressionNode temp4('/',temp3,factors[j].getDenominator(),factors[j].getSign());
						expressionNode temp5=temp4.reduceDivision();
						if(!(temp5==temp4))
							{
							factors[i]=temp5;
							factors[j]=one;
							}
						}
					}
				}
			for(i=0; i<factors.size(); ++i)
				{
				if(factors[i]==-one)
					sign3=!sign3;
				else if(!(factors[i]==one))
					{
					results.push_back(factors[i]);
					}
				}

			if(factors.size()!=results.size())
				{
				expressionNode temp1(gatherFactors(results));
				temp1.sign=sign3;

				return temp1;
				}
			else
				return *this;
			}

		expressionNode reduceExponent() const
			{
			if(subExpression1->isNumber() && subExpression2->isNumber())
				return expressionNode(subExpression1->getNumber()^subExpression2->getNumber(),sign);
			else if(subExpression1->isPower())
				{
				if(subExpression1->subExpression2->isNumber() && subExpression2->isNumber())
					return expressionNode('^',*(subExpression1->subExpression1),subExpression1->subExpression2->getNumber()*subExpression2->getNumber(),(sign==subExpression1->sign)? true: false);
				else
					return expressionNode('^',*(subExpression1->subExpression1),*(subExpression1->subExpression2)*(*(subExpression2)),(sign==subExpression1->sign)? true: false);
				}

			return *this;
			}

		expressionNode reduceExponentInDepth() const
			{
			if(isNumber())
				return getNumber();
			else if(isVariable() || isFunction())
				return *this;
			else if(isPower())
				{
				expressionNode temp1(subExpression1->reduceExponentInDepth());
				expressionNode temp2(subExpression2->reduceExponentInDepth());

				if(temp1->isNumber() && temp2->isNumber())
					return expressionNode(temp1->getNumber()^temp2->getNumber(),sign);
				else if(temp1->isPower())
					{
					if(temp1->subExpression2->isNumber() && temp2->isNumber())
						expressionNode temp('^',*(temp1->subExpression1),temp1->subExpression2->getNumber()*temp2->getNumber(),(sign==temp1->sign)? true: false);
					else
						return expressionNode('^',*(temp1->subExpression1),*(temp1->subExpression2)*(*(temp2)),(sign==temp1->sign)? true: false);
					}
				else
					return expressionNode('^',temp1,temp2,sign);
				}

			return *this;
			}

		bool isNumber() const
			{
			return (vt==NUMBER);
			}

		bool isVariable() const
			{
			return (vt==VARIABLE);
			}

		bool isFunction() const
			{
			return (vt==FUNCTION);
			}

		bool isOperator() const
			{
			return (vt==OPERATOR);
			}

		char getOperator() const
			{
			return Operator;
			}

		bool isSum() const
			{
			return (vt==OPERATOR && Operator=='+');
			}

		bool isSubtraction() const
			{
			return (vt==OPERATOR && Operator=='-');
			}

		bool isDivision() const
			{
			return (vt==OPERATOR && Operator=='/');
			}

		bool isMultiplication() const
			{
			return (vt==OPERATOR && Operator=='*');
			}

		bool isPower() const
			{
			return (vt==OPERATOR && Operator=='^');
			}

		expressionNode simplify() const
			{
			if(vt==NUMBER)
				{
				expressionNode temp(*this);
				return temp.normalize();
				}
				//return this->normalize();
			else if(vt==VARIABLE)
				return *this;
			else if(vt==FUNCTION)
				{
				expressionNode temp(pFunction), temp1;
				temp.sign=sign;
				temp1=subExpression1->simplify();
				temp.subExpression1=new expressionNode(temp1);
				temp.childs=temp1.childs+1;

				return temp.normalize();
				}
			else if(vt==OPERATOR)
				{
				expressionNode temp(subExpression1->simplify()),
				temp1(subExpression2->simplify());

				if(Operator=='+')
					{
					if(temp.vt==NUMBER && temp1.vt==NUMBER)
						{
						expressionNode temp2(temp.getNumber()+temp1.getNumber(),sign);

						return temp2.normalize();
						}
					else
						{
						expressionNode temp2('+',temp,temp1,sign);
						return (temp2.reduceSimilarTerms()).normalize();
						}
					//tal vez factorizar: findFactors()
					}
				else if(Operator=='-')
					{
					//nada porque el '-' no debe ser un nodo, sino una atributo de algun nodo
					//tal vez lanzar aquí una excepcion para avisar de un error, por no usar
					//doExplicitPlusSign()
					}
				else if(Operator=='/')
					{
					expressionNode one(type(true));

					if(temp.vt==NUMBER && temp1.vt==NUMBER)
						{
						expressionNode temp2(temp.getNumber()/temp1.getNumber(),sign);

						return temp2.normalize();
						}
					if(temp1==one)
						{
						if(!sign)
							temp.sign=!temp.sign;

						return temp.normalize();
						}
					if(temp1==-one)
						{
						if(sign)
							temp.sign=!temp.sign;

						return temp.normalize();
						}

					if(temp==temp1)
						{
						expressionNode temp2(type(true),sign);
						
						return temp2.normalize();
						}
					else if(temp==-temp1)
						{
						expressionNode temp2(-(type(true)));
						if(!sign)
							temp2=-temp2;
					
						return temp2.normalize();
						}
					else
						{//reduceDivision()
						expressionNode temp2;
						temp2=expressionNode('/',temp,temp1,sign);
						expressionNode temp4(temp2.reduceDivision());
						if(!(temp2==temp4))
							temp2=temp4.simplify();
						return temp2.normalize();

						/* Para pasar el denominador de un denominador, a la parte de arriba
						de la fracción

						bool changed=false;
						expressionNode *p=&temp, *p1=&temp1, temp2;

						if(p->vt==OPERATOR && p->Operator=='/')
							{
							expressionNode temp3('*',*(p->subExpression2),*p1);
							temp2=expressionNode('/',*(p->subExpression1),temp3.simplify());
							temp2.sign=sign;
							expressionNode temp4(temp2.reduceDivision());
							if(!(temp2==temp4))
								temp2=temp4.simplify();
							changed=true;
							}
						else if(p1->vt==OPERATOR && p1->Operator=='/')
							{
							expressionNode temp3('*',*p,*(p1->subExpression2));
							temp2=expressionNode('/',temp3.simplify(),*(p1->subExpression1));
							temp2.sign=sign;
							expressionNode temp4(temp2.reduceDivision());
							if(!(temp2==temp4))
								temp2=temp4.simplify();
							changed=true;
							}

						if(changed)
							return temp2.normalize();
						else
							{
							temp2=expressionNode('/',temp,temp1);
							temp2.sign=sign;
							expressionNode temp4(temp2.reduceDivision());
							if(!(temp2==temp4))
								temp2=temp4.simplify();
							return temp2.normalize();
							}
						*/
						}
					}
				else if(Operator=='*')
					{
					if(temp.vt==NUMBER && temp1.vt==NUMBER)
						{
						expressionNode temp2(temp.getNumber()*temp1.getNumber(),sign);

						return temp2.normalize();
						}

					if(temp==temp1)
						{
						expressionNode temp2('^',temp,type(2),sign);

						return (temp2.reduceExponent()).normalize();
						}
					else if(temp==-temp1)
						{
						expressionNode temp2('^',(temp.sign)? temp: temp1,type(2),false);

						if(!sign)
							temp2.sign=true;
						
						return temp2.normalize();
						}
					else
						{
						expressionNode temp2;
						temp2=expressionNode('*',temp,temp1,sign);
						expressionNode temp4(temp2.reduceMultiplication());
						if(!(temp2==temp4))
							temp2=temp4.simplify();

						return temp2.normalize();
						}
					}
				else if(Operator=='^')
					{
					if(temp.vt==NUMBER && temp1.vt==NUMBER)
						{
						expressionNode temp2(temp.getNumber()^temp1.getNumber(),sign);

						return temp2.normalize();
						}
					else
						{
						expressionNode temp2;
						temp2=expressionNode('^',temp,temp1,sign);
						expressionNode temp4(temp2.reduceExponent());
						if(!(temp2==temp4))
							temp2=temp4.simplify();

						return temp2.normalize();
						}
					}
				}

			return *this;
			}

		bool searchForVariable() const
			{
			if(vt==VARIABLE)
				return true;
			if(subExpression1->searchForVariable())
				return true;
			if(subExpression2->searchForVariable())
				return true;

			return false;
			}

		int cost() const
			{
			int c=0;
			if(vt==OPERATOR)
				{
				c=amv::cost(Operator);
				c+=subExpression1->cost()+subExpression2->cost();
				}
			else if(vt==FUNCTION)
				{
				c=amv::cost('>');
				c+=subExpression1->cost();
				}

			return c;
			}

		//obtiene los argumentos que están delimitados por el operador ','
		void getArguments(deque<expressionNode *> &d)
			{
			if(vt==OPERATOR && Operator==',')
				{//si hay una coma, es obligatorio que tenga dos hijos, los argumentos
				subExpression1->getArguments(d);
				subExpression2->getArguments(d);
				}
			else
				{
				d.push_back(this);
				}
			}

		expressionNode eval()
			{
			if(vt==NUMBER)
				return *this;
			else if(vt==OPERATOR)
				{
				expressionNode result1=subExpression1->eval(),
				result2=subExpression2->eval();
				if(result1.vt==NUMBER && result2.vt==NUMBER)
					{
					if(Operator=='+')
						{
						expressionNode temp((*(result1.pNumber))+(*(result2.pNumber)));
						return temp;
						}
					else if(Operator=='-')
						{
						expressionNode temp((*(result1.pNumber))-(*(result2.pNumber)));
						return temp;
						}
					else if(Operator=='*')
						{
						expressionNode temp((*(result1.pNumber))*(*(result2.pNumber)));
						return temp;
						}
					else if(Operator=='/')
						{
						expressionNode temp((*(result1.pNumber))/(*(result2.pNumber)));
						return temp;
						}
					else if(Operator=='^')
						{
						expressionNode temp((*(result1.pNumber))^(*(result2.pNumber)));
						return temp;
						}
					}
				else
					{
					return *this;
					}
				}
			else if(vt==FUNCTION)
				{
				if(pFunction->isUnary())
					{
					expressionNode result=subExpression1->eval();
					if(result.vt==NUMBER)
						{
						expressionNode temp((pFunction->getFunction())(*(result.pNumber)));
						return temp;
						}
					else
						{
						return *this;
						}
					}
				else if(pFunction->isBinary())
					{
					deque<expressionNode *> d;
					subExpression1->getArguments(d);
					if(d.size()==2)
						{
						deque<expressionNode> results(d.size());
						for(deque<expressionNode *>::size_type i=0; i<d.size(); ++i)
							results[i]=d[i]->eval();
						if(results[0].isNumber() && results[1].isNumber())
							{
							expressionNode temp((pFunction->getFunctionb())(results[0].getNumber(),results[1].getNumber()));
							return temp;
							}
						else
							{
							return *this;
							}
						}
					else
						{
						//Error, no hay argumentos o hay demasiados
						return *this;
						}
					}
				}
			else if(vt==VARIABLE)
				{
				if(pVariable->isDefined())
					{
					expressionNode temp(pVariable->getValue());

					return temp;
					}

				return *this;
				}

			}

		bool operator==(const expressionNode &eN) const
			{
			if(vt==eN.vt)
				{
				switch(vt)
					{
					case NUMBER:
						if(*pNumber==*(eN.pNumber) && sign==eN.sign)
							return true;
						else
							return false;
					case VARIABLE:
						if(pVariable==eN.pVariable && sign==eN.sign)
							return true;
						else
							return false;
					case FUNCTION:
						if(pFunction==eN.pFunction && sign==eN.sign && (*subExpression1==*(eN.subExpression1)))
							return true;
						else
							return false;
					case OPERATOR:
						if(Operator==eN.Operator && sign==eN.sign && (*subExpression1==*(eN.subExpression1))
							&& (*subExpression2==*(eN.subExpression2)))
							return true;
						else
							return false;
					}

				}

			return false;
			}

		void inorden(ostream &os)
			{
			if(vt==NUMBER)
				{
				if(!sign) os<<'-';
				os<<getNumber()<<'['<<label<<']'<<'{'<<level<<'}'<<":\t";
				}
			else if(vt==VARIABLE)
				{
				if(!sign) os<<'-';
				os<<pVariable->getName()<<'['<<label<<']'<<'{'<<level<<'}'<<":\t";
				}
			else if(vt==FUNCTION)
				{
				if(!sign) os<<'-';
				subExpression1->inorden(os);
				os<<pFunction->getName()<<'['<<label<<']'<<'{'<<level<<'}'<<":\t";
				}
			else if(vt==OPERATOR)
				{
				if(!sign) os<<'-';
				subExpression1->inorden(os);
				os<<Operator<<'['<<label<<']'<<'{'<<level<<'}'<<":\t";
				subExpression2->inorden(os);
				}
			}

		void preorden(ostream &os)
			{
			if(vt==NUMBER)
				{
				if(!sign) os<<'-';
				os<<getNumber()<<'['<<label<<']'<<'{'<<level<<'}'<<":\t";
				}
			else if(vt==VARIABLE)
				{
				if(!sign) os<<'-';
				os<<pVariable->getName()<<'['<<label<<']'<<'{'<<level<<'}'<<":\t";
				}
			else if(vt==FUNCTION)
				{
				if(!sign) os<<'-';
				os<<pFunction->getName()<<'['<<label<<']'<<'{'<<level<<'}'<<":\t";
				subExpression1->preorden(os);
				}
			else if(vt==OPERATOR)
				{
				if(!sign) os<<'-';
				os<<Operator<<'['<<label<<']'<<'{'<<level<<'}'<<":\t";
				subExpression1->preorden(os);
				subExpression2->preorden(os);
				}
			}

		friend ostream &operator<<(ostream &os, const expressionNode &e)
			{
			if(e.vt==NUMBER)
				{
				if(!e.sign)
					os<<(-(*(e.pNumber)));
				else
					os<<(*(e.pNumber));
				}
			else if(e.vt==VARIABLE)
				{
				if(!e.sign)
					os<<'-'<<(e.pVariable->getName());
				else
					os<<(e.pVariable->getName());
				}
			else if(e.vt==OPERATOR)
				{
				if(e.childs>2)
					{
					if(!e.sign)
						{
						os<<"-(";
						if(e.level<e.subExpression1->level)
							os<<'('<<(*(e.subExpression1))<<')';
						else
							os<<(*(e.subExpression1));
						os<<e.Operator;
						if(e.level<e.subExpression2->level)
							os<<'('<<(*(e.subExpression2))<<')';
						else
							os<<(*(e.subExpression2));
						os<<')';
						}
					else
						{
						if(e.level<e.subExpression1->level)
							os<<'('<<(*(e.subExpression1))<<')';
						else
							os<<(*(e.subExpression1));
						os<<e.Operator;
						if(e.level<e.subExpression2->level)
							os<<'('<<(*(e.subExpression2))<<')';
						else
							os<<(*(e.subExpression2));
						}
					}
				else
					{
					if(!e.sign)
						{
						os<<"-(";
						os<<(*(e.subExpression1));
						os<<e.Operator;
						os<<(*(e.subExpression2));
						os<<')';
						}
					else
						{
						os<<(*(e.subExpression1));
						os<<e.Operator;
						os<<(*(e.subExpression2));
						}
					}
				}
			else if(e.vt==FUNCTION)
				{
				if(!e.sign)
					os<<'-';

				os<<(e.pFunction->getName());
				os<<'(';
				os<<(*(e.subExpression1));
				os<<')';
				}

			return os;
			}

	};

public:
	static binaryTree<function<type> > *pTreeFunctions;

private:
	static binaryTree<variable<type> > *pTreeVariables;
	static REEvaluator REEexpression;
	static deque<void *> dPatterns;//void * porque sólo de esta manera lo entiende el compilador VC++ 6.0
	static deque<void *> dIdentities;//no acepta deque<expressionNode *>
	int minCost;//para uso de la función smartSimplify()
		
	expressionNode *pRootNode;

	expression(const expressionNode &eN):
	pRootNode(new expressionNode(eN))
		{
		}
	expression &operator=(const expressionNode &eN)
		{
		delete pRootNode;
		pRootNode=new expressionNode(eN);

		return *this;
		}

	virtual void constructTree(const string &s);
	virtual void extract(istream &is);

	public:
		static bool eval(const char *number);

		expression(const type &n=type()):
		pRootNode(new expressionNode(n))
			{
			}
		expression(const char sourceOperator):
		pRootNode(new expressionNode(sourceOperator))
			{
			}
		expression(const string &s):
		pRootNode(new expressionNode(s))
			{
			}
		expression(const function<type> *pf):
		pRootNode(new expressionNode(pf))
			{
			}
		expression(const string &s, bool b)
			{
			constructTree(s);
			}
		expression(const expression &e):
		pRootNode(e.pRootNode? new expressionNode(*(e.pRootNode)): 0)
			{
			}
		expression(bool b):
		pRootNode(new expressionNode(type(b)))
			{
			}
		~expression()
			{
			delete pRootNode;
			}
		expression &operator=(const expression &op2)
			{
			delete pRootNode;
			pRootNode=new expressionNode(*(op2.pRootNode));

			return *this;
			}
		expression &operator=(bool b)
			{
			delete pRootNode;
			pRootNode=new expressionNode(type(b));

			return *this;
			}
		bool operator==(const expression &op2) const
			{
			return (*pRootNode==*(op2.pRootNode));
			}
		expression eval() const
			{
			return pRootNode->eval();
			}

		virtual expression &operator+=(const expression &op2);
		virtual expression &operator-=(const expression &op2);
		virtual expression &operator*=(const expression &op2);
		virtual expression &operator/=(const expression &op2);
		virtual expression &operator^=(const expression &op2);
		
		virtual expression operator+(const expression &op2) const;
		virtual expression operator-(const expression &op2) const;
		virtual expression operator*(const expression &op2) const;
		virtual expression operator/(const expression &op2) const;
		virtual expression operator^(const expression &op2) const;
		virtual expression operator+() const;
		virtual expression operator-() const;

		expression apply(const function<type> *pf) const;

		typedef type value_type;

		friend ostream &operator<<(ostream &os, const expression<type,ptf,ptv> &e)
			{
			os<<*(e.pRootNode);
			return os;
			}
		friend istream &operator>>(istream &is, expression<type,ptf,ptv> &e)
			{
			e.extract(is);
			return is;
			}

		typedef expression<type,ptf,ptv> (*pfExpression)(const expression<type,ptf,ptv> &);

		static binaryTree<function<expression<type,ptf,ptv> > > getFunctionsTree(const expression &e)
			{
			binaryTree<function<expression > > t;

			expression e1;

			//instanciación explícita de las plantillas
			fact1<expression,type>(e1);
			exp<expression,type>(e1);
			log<expression,type>(e1);
			ln<expression,type>(e1);
			sin<expression,type>(e1);
			sinh<expression,type>(e1);
			asin<expression,type>(e1);
			cos<expression,type>(e1);
			cosh<expression,type>(e1);
			acos<expression,type>(e1);
			tan<expression,type>(e1);
			tanh<expression,type>(e1);
			atan<expression,type>(e1);
			ctg<expression,type>(e1);
			actg<expression,type>(e1);
			sec<expression,type>(e1);
			asec<expression,type>(e1);
			csc<expression,type>(e1);
			acsc<expression,type>(e1);
			root<expression,type>(e1,e1);

//			t.insert(function<expression >("sin",(pfExpression)sin)),
//			t.insert(function<expression >("cos",(pfExpression)cos)),
//			t.insert(function<expression >("tan",(pfExpression)tan));

			t.insert(function<expression >("fact",(pfExpression)fact1)),
			t.insert(function<expression >("exp",(pfExpression)exp)),
			t.insert(function<expression >("log",(pfExpression)log)),
			t.insert(function<expression >("ln",(pfExpression)ln)),
			t.insert(function<expression >("sin",(pfExpression)sin)),
			t.insert(function<expression >("sinh",(pfExpression)sinh)),
			t.insert(function<expression >("asin",(pfExpression)asin)),
			t.insert(function<expression >("cos",(pfExpression)cos)),
			t.insert(function<expression >("cosh",(pfExpression)cosh)),
			t.insert(function<expression >("acos",(pfExpression)acos)),
			t.insert(function<expression >("tan",(pfExpression)tan)),
			t.insert(function<expression >("tanh",(pfExpression)tanh)),
			t.insert(function<expression >("atan",(pfExpression)atan)),
			t.insert(function<expression >("ctg",(pfExpression)ctg)),
			t.insert(function<expression >("actg",(pfExpression)actg)),
			t.insert(function<expression >("sec",(pfExpression)sec)),
			t.insert(function<expression >("asec",(pfExpression)asec)),
			t.insert(function<expression >("csc",(pfExpression)csc)),
			t.insert(function<expression >("acsc",(pfExpression)acsc)),
			t.insert(function<expression >("min",(pfExpression)min,function<expression >::BINARY)),
			t.insert(function<expression >("max",(pfExpression)max,function<expression >::BINARY)),
			t.insert(function<expression >("pow",(pfExpression)pow,function<expression >::BINARY)),
			t.insert(function<expression >("root",(pfExpression)root,function<expression >::BINARY));

			return t;
			}

		void printTerms(ostream &os) const
			{
			deque<expressionNode> d;
			pRootNode->getTerms(d,0);
			deque<expressionNode>::iterator i(d.begin());
			while(i!=d.end())
				os<<*i++<<';';

			}

		void printFactors(ostream &os) const
			{
			deque<expressionNode> d;
			pRootNode->getFactors(d,0);
			deque<expressionNode>::iterator i(d.begin());
			while(i!=d.end())
				os<<*i++<<';';

			}

		static void printPatterns(ostream &os)
			{
			for(deque<void *>::size_type i=0; i<dPatterns.size(); ++i)
				printPattern(os,i);
			}

		static void printPattern(ostream &os, deque<void *>::size_type i)
			{
			os<<(*((expressionNode *)dPatterns[i]))<<" = "<<(*((expressionNode *)dIdentities[i]))<<'\n';
			}

//Simplificación sencilla

		expression simplify() const
			{
			return (pRootNode->simplify());
			}

//normalización, pone en una forma definida las expresiones

		const expression &normalize()
			{
			pRootNode->normalize();

			return *this;
			}

//Calcula el costo de la expresión

		int cost() const
			{
			return pRootNode->cost();
			}

//*********** Patrones **************
	protected:
		class infoPatternNode	{
			public:
			infoPatternNode(): pRoot(0), pattern(0), identity(0), otherFactors(0), otherTerms(0)
				{
				}
			infoPatternNode(const expressionNode *pr, const expressionNode *p, const expressionNode *pi,
							const deque<expressionNode> &ds, const deque<expressionNode> &dn,
							const expressionNode *oF=0, const expressionNode *oT=0):
			pRoot(pr), pattern(p), identity(pi), dSymbols(ds), dNodes(dn), otherFactors(oF? new expressionNode(*oF): oF), otherTerms(oT? new expressionNode(*oT): oT)
				{
				}
			infoPatternNode(const infoPatternNode &i): pRoot(i.pRoot), pattern(i.pattern), identity(i.identity),
			dSymbols(i.dSymbols), dNodes(i.dNodes), otherFactors(i.otherFactors? new expressionNode(*(i.otherFactors)): i.otherFactors),
			otherTerms(i.otherTerms? new expressionNode(*(i.otherTerms)): i.otherTerms)
				{
				}
			const expressionNode *pRoot, *pattern, *identity;
			const expressionNode *otherFactors, *otherTerms;
			deque<expressionNode> dSymbols;
			deque<expressionNode> dNodes;
			~infoPatternNode()
				{
				delete otherFactors;
				delete otherTerms;
				}
		};

	public:

		deque<expressionNode>::size_type findPatterns()
			{
			deque<infoPatternNode> d;
			const expressionNode *p;

			for(int i=0; i<dPatterns.size(); ++i)
				{
				if(p=pRootNode->findEquivalentPattern(*((expressionNode *)dPatterns[i]),d))
					cerr<<(*((expressionNode *)dPatterns[i]))<<" ==> "<<*p<<":\t";
				}

			return d.size();
			}

		deque<expressionNode>::size_type findPatterns1(deque<infoPatternNode> &d)
			{
			const expressionNode *p;

			for(int i=0; i<dPatterns.size(); ++i)
				{
				if(p=pRootNode->findEquivalentPattern(*((expressionNode *)dPatterns[i]),d))
					{
					d[d.size()-1].identity=(const expressionNode *)dIdentities[i];
					//d[d.size()-1].pattern=(expressionNode *)dPatterns[i];
					//std::cerr<<(*((expressionNode *)dPatterns[i]))<<" = "<<(*((expressionNode *)dIdentities[i]))<<" ==> "<<*p<<":\t";

					}
				}

			return d.size();
			}

//Simplifica mediante búsqueda en árboles

		expression<type,ptf,ptv> smartSimplify(int maxDepth)
			{
			expression temp(simplify());
			temp.minCost=temp.cost();
			return (temp.smartSimplify(maxDepth,0));
			}
		
		expression<type,ptf,ptv> smartSimplify(int maxDepth, int currentDepth)
			{//maxDepth es el máximo nivel de profundidad, currentDepth es la actual
			deque<infoPatternNode> d;
			deque<expression> dchilds;
			deque<expression> selectedChilds;

			pRootNode->setLabel();
			findPatterns1(d);
			if(d.size())
				{
				//decidir cuantos patrones aplicar en la sustitucion
				//hay 2^n combinaciones, por ahora sólo sustituye uno en cada hijo
				//también tomaremos en cuenta los patrones que estan traslapados
				int i;
				for(i=0; i<d.size(); ++i)
					{
					expressionNode original=*(pRootNode);
					original.setLabel();//por ahora no se copian las etiquetas en =

					expressionNode eN((const expressionNode *)d[i].identity,d[i].dSymbols,d[i].dNodes);
					if(d[i].otherFactors)
						eN*=*(d[i].otherFactors);
					else if(d[i].otherTerms)
						eN+=*(d[i].otherTerms);
						
					original.substitute(d[i].pRoot->label,eN);
					expression e(original);
					dchilds.push_back(e.simplify());
					}
				sort(dchilds.begin(),dchilds.end(),compare<type,ptf,ptv>);
				for(i=0; i<dchilds.size(); ++i)
					{
					if(dchilds[i].cost()<minCost)
						selectedChilds.push_back(dchilds[i]);
					}

				//analizar los hijos: cost()<minCost y filtrarlos para el siguiente paso
				++currentDepth;
				if(currentDepth==maxDepth)
					{
					//poner los mejores resultados y regresar
					if(selectedChilds.size())
						return selectedChilds[0];
					else
						return *this;
					}
				else
					{
					deque<expression> results;
					for(i=0; i<selectedChilds.size(); ++i)
						{
						results.push_back(selectedChilds[i].smartSimplify(maxDepth,currentDepth));
						}
					if(results.size())
						{
						sort(results.begin(),results.end(),compare<type,ptf,ptv>);
						return results[0];
						}
					return *this;
					}
				}
			else
				return *this;
			}

//Para crear los patrones

		static void createPatterns(const char *name)
			{
			//ignorar comentarios, lo demás, son ecuaciones de la forma
			//expression1=expression2;

			ifstream identities(name);
			if(identities)
				{
				REEvaluator REElineComment="//@*\n";
				REEvaluator REEmultilineComment="/\\*@*\\*/";
				REEvaluator REEexpression1="@+=";
				REEvaluator REEexpression2="@+;";
				REEvaluator REEnoSpace="#*";
				string s,s1;

				while(identities)
					{
					REEnoSpace.skipNoSymbols(identities);
					if(REElineComment.getLexema(identities,s,true))
						{
						}
					else if(REEmultilineComment.getLexema(identities,s,true))
						{
						}
					else if(REEexpression1.getLexema(identities,s,true))
						{
						if(REEexpression2.getLexema(identities,s1,true))
							{
							s.pop_back();
							s1.pop_back();
							expression<type,ptf,ptv> e1(expression<type,ptf,ptv>(s,true));
							expression<type,ptf,ptv> e2(expression<type,ptf,ptv>(s1,true));
							dPatterns.push_back(new expressionNode(e1.pRootNode->normalize()));
							dIdentities.push_back(new expressionNode(e2.pRootNode->normalize()));
							//std::cerr<<"Patrón creado: "<<e1<<" = "<<e2<<'\n';
							}
						else
							{
							std::cerr<<"Hace falta una identidad en los patrones, cierre el programa\n";
							}
						}
					else
						identities.get();
					}
				}
			else
				std::cerr<<"No se pudo abrir el archivo con los patrones\n";

			//se pueden poner ambos lados de la identidad para expandir o contraer la expresión
			//buscando llegar a un mejor estado
			}

//Para destruirlos

		static void destroyPatterns()
			{
			for(deque<void *>::size_type i=0; i<dPatterns.size(); ++i)
				{
				delete (expressionNode *)dPatterns[i];
				delete (expressionNode *)dIdentities[i];
				}
			}
/*
//funciones para agregar patrones para búsqueda en una simplificacion, no esta probadas todavía

		static void addPattern(string &sPattern, string &sIdentity)
			{
			dPatterns.push_back(expression(sPattern,true));
			dIdentities.push_back(expression(sIdentity,true));
			}

		static void addPattern(expression &ePattern, expression &eIdentity)
			{
			dPatterns.push_back(*(ePattern.pRootNode));
			dIdentities.push_back(*(eIdentitie.pRootNode));
			}
*/

//imprimir informacion del árbol sintáctico

		void preorden(ostream &os) const
			{
			pRootNode->setLabel();
			pRootNode->preorden(os);
			}

		void inorden(ostream &os) const
			{
			pRootNode->setLabel();
			pRootNode->inorden(os);
			}

		friend class expressionNode;//para tener acceso a los datos privados de expression desde expressionNode

		friend bool compare(const expression &e1, const expression &e2);
//			{
//			return (e1.cost()<e2.cost());
//			}

		//devuelve el número de permutaciones posibles para sustituir los patrones encontrados
		unsigned int explode()
			{
			deque<infoPatternNode> d;
			findPatterns1(d);
			return (::pow(2,d.size()));
			}
		//aplica la sustitución de los patrones correspondiente a la n-ésima permutación
		expression &apply(unsigned int nth)
			{
			deque<infoPatternNode> d;
			pRootNode->setLabel();
			expressionNode original=*(pRootNode);
			findPatterns1(d);
			if(nth<::pow(2,d.size()))
				{
				for(unsigned int i=0, j=1; i<d.size(); ++i, j<<=1)
					{
					if(nth&j)
						{
						expressionNode eN((const expressionNode *)d[i].identity,d[i].dSymbols,d[i].dNodes);
						if(d[i].otherFactors)
							eN*=*(d[i].otherFactors);
						else if(d[i].otherTerms)
							eN+=*(d[i].otherTerms);
							
						original.substitute(d[i].pRoot->label,eN);
						}
					}
				*this=original;
				*this=simplify();
				}

			return *this;
			}

};

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
bool compare(const expression<type,ptf,ptv> &e1, const expression<type,ptf,ptv> &e2)
{
return (e1.cost()<e2.cost());
}

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
inline bool expression<type,ptf,ptv>::eval(const char *number)
{
return (REEexpression.eval(number));
}

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
deque<void *> expression<type,ptf,ptv>::dPatterns;

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
deque<void *> expression<type,ptf,ptv>::dIdentities;

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
binaryTree<function<type> > *expression<type,ptf,ptv>::pTreeFunctions=ptf;

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
binaryTree<variable<type> > *expression<type,ptf,ptv>::pTreeVariables=ptv;

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
REEvaluator expression<type,ptf,ptv>::REEexpression=("( |[a-z]|[A-Z]|[0-9]|\\+|^|\\-|\\*|/|,|\\(|\\)|\\[|\\]|.)+");

template <class type,  binaryTree<function<type> > *ptf, binaryTree<variable<type> > *ptv>
inline expression<type,ptf,ptv> expression<type,ptf,ptv>::apply(const function<type> *pf) const
{
expression temp(pf);
temp.pRootNode->childs=pRootNode->childs+1;
temp.pRootNode->subExpression1=new expressionNode(*pRootNode);

return temp;
}

template <class X, class s>
X fact1(const X &e)
{
//typedef typename X::value_type subtype;
typedef s subtype;

function<subtype> *pFunction=X::pTreeFunctions->find(function<subtype>("fact",0));
if(pFunction)
	return e.apply(pFunction);

return e;
}

template <class X, class s>
X exp(const X &e)
{
//typedef typename X::value_type subtype;
typedef s subtype;

function<subtype> *pFunction=X::pTreeFunction