/*

Operadores:

'|' alternancia
'<' concatenación
'*' cerradura de Kleene
'+' cerradura positiva
'-' intervalos
'[' y ']' intervalos
'(' y ')' niveles de precedencia
'?' lo que le precede o nada

Metacaracteres:

'@' cualquier carácter
'#' cualquier carácter que al aplicarle isspace(c), de falso como resultado

De tal manera que si queremos que el evaluador reconozca uno de metacaracteres
u operadores como símbolos, debemos utilizar el carácter de escape '\'. Por ejemplo,
para reconocer la palabra '#include', debemos poner los siguiente:

REEvaluator REEinclude="\\#include";

	se utilizó '\\' porque es la manera de poner '\' en una cadena en C++
*/
#ifndef __REEvaluator_AMV
	#define __REEvaluator_AMV

#include <iostream>
#include <strstream>
#include <cctype>
#include <limits>
#include "streambufw.h"
#include "stack.h"
#include "stringAMV.h"
#include "deque.h"
#include "algorithm.h"
#include "amvdefs.h"

namespace amv	{

class REEvaluator	{

	class token	{
		public:
			enum token_type	{ EMPTY, SYMBOL, OPERATOR };
			token_type vt;
			bool nospace;
			bool interval;
			bool anysymbol;
			char symbol,c1,c2;
			token():
			vt(EMPTY), nospace(false), interval(false), anysymbol(false)
				{
				}
			token(char c, token_type t=SYMBOL, bool ns=false, bool i=false, bool a=false):
			vt(t), symbol(c), nospace(ns), interval(i), anysymbol(a)
				{
				}
			token(char char1, char char2):
			vt(SYMBOL), nospace(false), interval(true), anysymbol(false),
			c1(char1), c2(char2)
				{
				}

			void toAnysymbol()
				{
				vt=SYMBOL;
				anysymbol=true;
				nospace=false;
				interval=false;
				}

			void toNospace()
				{
				vt=SYMBOL;
				anysymbol=false;
				nospace=true;
				interval=false;
				}

			void toInterval(char char1, char char2)
				{
				vt=SYMBOL;
				anysymbol=false;
				nospace=false;
				interval=true;
				c1=char1;
				c2=char2;
				}

			void toEmpty()
				{
				vt=EMPTY;
				}

			void toSymbol(char c)
				{
				vt=SYMBOL;
				symbol=c;
				nospace=false;
				interval=false;
				anysymbol=false;
				}

			void toOperator(char c)
				{
				vt=OPERATOR;
				symbol=c;
				}

			bool isEmpty() const
				{
				return vt==EMPTY;
				}
			bool isSymbol() const
				{
				return vt==SYMBOL;
				}
			bool isOperator() const
				{
				return vt==OPERATOR;
				}

			bool isInInterval(char c)
				{
				if(c1<=c && c<=c2)
					return true;
				return false;
				}

		};

	class state;

	class connection	{
		public:
			state *nextState;
			token transition;
			connection():
			nextState(0), transition()
				{
				}
	};

	class state	{
		int visited;
		public:
			int stateNumber, connectionsNumber;
			connection *pConnections;
			state()
				{
				stateNumber=0;
				pConnections=0;
				connectionsNumber=0;
				visited=0;
				}
			~state()
				{
				if(pConnections)
					{
					if(connectionsNumber==1)
						delete pConnections;
					else
						delete [] pConnections;
					}
				}
			void deleteVisit();
			void lockE(stack<state *> &stackStates);
			void saveStates(stack<state *> &stackStates);
	};


	class AFN	{
		public:
			state *beg, *end;
			AFN() { beg=end=0; }
	};

	vector<token> regularExpression, RPNregularExpression;
	int stateNum;
	AFN *pafn;
	stack<AFN *> stackAFNs;
	stack<state *> stackStates;
	vector<bool> definedSymbols;
	bool isOperator(char c);
	void REtoRPN();
	void removeSquareBrackets();
	void removeQuestionSign();
	void removePositiveLock();
	void insertOperator();
	int precedence(char operador);
	void createAFN();
	AFN *createSymbolAFN(token t);
	AFN *alternateAFNs(AFN *afn1, AFN *afn2);
	AFN *Kleene(AFN *afn1);
	AFN *uniteAFNs(AFN *afn1, AFN *afn2);
	void lockET();
	void move(char symbol);
	void deleteStates();
	public:
		class syntax_error	{
			public:
				syntax_error(const char *message="Error de sintaxis")
				{
				}
		};
		REEvaluator(char *regExp);
		~REEvaluator();
		bool eval(const char *str);
		bool eval(const string &s);
		template<class II>
		bool eval(II begin, II end)
			{
			bool accepted=false;
			pafn->beg->lockE(stackStates);
			pafn->beg->deleteVisit();
			while(begin!=end)
				{
				move(*begin);
				if(stackStates.empty())
					return false;
				lockET();
				++begin;
				}
			while(stackStates.size())
				{
				if(stackStates.top()==pafn->end)
					accepted=true;
				stackStates.pop();
				}
			return accepted;
			}

		bool eval(const char c);
		bool isSymbol(const char c);
		friend istream &operator>>(istream &is, REEvaluator &e);
		bool hasAcceptedState() const;
		bool searchLexema(istream &is, string &s, deque<char> &newStr, bool delimiter, unsigned int pos, bool stdinput=false);
		bool getLexema(istream &is,string &s, bool smallest=false);
		bool getLexemaWithEscape(istream &is,string &s, char escape);
		bool getLexema(istream &is,string &s, char delimiter, bool smallest=false);
		bool getLexema(istream &is,string &s, char delimiter, char escape, bool smallest=false);
		template<class it>
		bool getLexema(it &begin, it end, string &s)
			{
			static deque<char> newStr;
			char c=0;
			bool accepted=false;

			newStr.clear();
			pafn->beg->lockE(stackStates);
			pafn->beg->deleteVisit();

			while(begin!=end)
				{
				c=*begin;
				if(definedSymbols[static_cast<unsigned char>(c)])
					{
					newStr.push_back(c);
					move(c);
					lockET();
					}
				else
					{
					break;
					}
				++begin;
				}

			while(stackStates.size())
				{
				if(stackStates.top()==pafn->end)
					accepted=true;
				stackStates.pop();
				}

			if(accepted)
				{
				s.resize(newStr.size());
				deque<char>::const_iterator itSource(newStr.begin());
				string::iterator itTarget(s.begin());

				while(itSource!=newStr.end())
					{
					*itTarget=*itSource;
					++itTarget;
					++itSource;
					}
				}

			return accepted;
			}
		istream &skipNoSymbols(istream &is);
		template<class it>
		it &skipNoSymbols(it &begin, it end)
			{
			char c=0;

			while(begin!=end)
				{
				c=*begin;
				if(definedSymbols[static_cast<unsigned char>(c)])
					{
					break;
					}
				++begin;
				}

			return begin;
			}
		static bool (*isspace)(char);
		static void setIsspace(bool (*pf)(char));

friend class state;

};

bool myIsspace(char c)
{
if(c==0x20 || (0x08<c && c<0x0e))//c está entre 0x09 y 0x0d o es 0x020
	return true;

return false;
}

typedef bool (*pfbc)(char);
pfbc REEvaluator::isspace=myIsspace;

void REEvaluator::setIsspace(pfbc pf)
{
isspace=pf;
}

void REEvaluator::state::deleteVisit()
{
visited=0;
if(pConnections)
	{
	switch(connectionsNumber)
		{
		case 1:
			if(pConnections->nextState->visited)
				pConnections->nextState->deleteVisit();
			break;
		case 2:
			if(pConnections[0].nextState->visited)
				pConnections[0].nextState->deleteVisit();
			if(pConnections[1].nextState->visited)
				pConnections[1].nextState->deleteVisit();
			break;
		}
	}

}

void REEvaluator::state::lockE(stack<state *> &stackStates)
{
visited=1;
stackStates.push(this);
if(pConnections)
	{
	switch(connectionsNumber)
		{
		case 1:
			if((pConnections->transition.isEmpty()) && !pConnections->nextState->visited)
				pConnections->nextState->lockE(stackStates);
			break;
		case 2:
			if((pConnections[0].transition.isEmpty()) && !pConnections[0].nextState->visited)
				pConnections[0].nextState->lockE(stackStates);
			if((pConnections[1].transition.isEmpty()) && !pConnections[1].nextState->visited)
				pConnections[1].nextState->lockE(stackStates);
			break;
		}
	}
}

void REEvaluator::state::saveStates(stack<state *> &stackStates)
{
visited=1;
stackStates.push(this);
if(pConnections)
	{
	switch(connectionsNumber)
		{
		case 1:
			if(!pConnections->nextState->visited)
				pConnections->nextState->saveStates(stackStates);
			break;
		case 2:
			if(!pConnections[0].nextState->visited)
				pConnections[0].nextState->saveStates(stackStates);
			if(!pConnections[1].nextState->visited)
				pConnections[1].nextState->saveStates(stackStates);
			break;
		}
	}
}

bool REEvaluator::isOperator(char c)
{
if(c=='*' || c=='+' || c=='(' || c==')'
	|| c=='[' || c==']' || c=='?' || c=='|' || c=='<' || c=='-')
	return true;

return false;
}

void REEvaluator::REtoRPN()
{
stack<token> stackOperators;
RPNregularExpression.resize(regularExpression.size());
vector<token>::const_iterator itRE(regularExpression.begin());
vector<token>::iterator itRPN(RPNregularExpression.begin());
token temp;

int operatorPrecedence=0;

while(itRE!=regularExpression.end())
	{
	if(itRE->isOperator() && itRE->symbol=='(')
		{
		stackOperators.push(*itRE);
		}
	else if(itRE->isOperator() && itRE->symbol==')')
		{
		temp=stackOperators.top();
		stackOperators.pop();
		while(!(temp.isOperator() && temp.symbol=='('))//temp.symbol!='('
			{
			*itRPN=temp;
			++itRPN;
			temp=stackOperators.top();
			stackOperators.pop();
			}
		}
	else if(itRE->isOperator() && (itRE->symbol=='*' || itRE->symbol=='|' ||
	itRE->symbol=='+' || itRE->symbol=='<'))
		{
		int notEmptyStack=stackOperators.size();
		operatorPrecedence=precedence(itRE->symbol);
		if(notEmptyStack)
			{
			temp=stackOperators.top();
			}
		while(notEmptyStack && temp.symbol!='(' && (operatorPrecedence<=precedence(temp.symbol)))
			{
			*itRPN=temp;
			++itRPN;
			stackOperators.pop();
			notEmptyStack=stackOperators.size();
			if(notEmptyStack)
				temp=stackOperators.top();
			}
		stackOperators.push(*itRE);
		}
	else
		{
		*itRPN=*itRE;
		++itRPN;
		}
	++itRE;
	}
while(stackOperators.size())
	{
	*itRPN=stackOperators.top();
	++itRPN;
	stackOperators.pop();
	}
RPNregularExpression.resize(itRPN-RPNregularExpression.begin());
}

void REEvaluator::removeSquareBrackets()
{
vector<token>::const_iterator itRE(regularExpression.begin());
vector<token> newStr;
token temp;
temp.vt=token::OPERATOR;

while(itRE!=regularExpression.end())
	{
	if(itRE->isOperator() && itRE->symbol=='[')
		{
		temp.toOperator('(');
		newStr.push_back(temp);
		++itRE;
		newStr.push_back(*itRE);
		++itRE;
		while(!(itRE->isOperator() && itRE->symbol==']'))
			{
			if((itRE-1)->isSymbol() && itRE->isSymbol())
				{
				temp.toOperator('|');
				newStr.push_back(temp);
				newStr.push_back(*itRE);
				}
			else if((itRE-1)->isOperator() && (itRE-1)->symbol=='-')
				{
				temp.toInterval((itRE-2)->symbol,itRE->symbol);
				newStr.back()=temp;
				char c;//checar el siguiente ciclo en la funcion comentada del mismo nombre y en esta
				//por definedSymbols del primer elemento
				for(c=(itRE-2)->symbol+1; c<=itRE->symbol; ++c)
					{
					definedSymbols[static_cast<unsigned char>(c)]=true;
					}
				}
			++itRE;
			}
		temp.toOperator(')');
		newStr.push_back(temp);
		}
	else
		newStr.push_back(*itRE);
	++itRE;
	}

regularExpression=newStr;
vector<token>::iterator it(regularExpression.begin());
for(it=regularExpression.begin(); it!=regularExpression.end(); ++it)
	{
	if(it->isOperator() && it->symbol=='-')
		{
		it->toSymbol('-');
		}
	}
}

void REEvaluator::removeQuestionSign()
{
vector<token>::const_iterator itRE(regularExpression.begin());
vector<token> newRE;
token d;
int signsNumber=0;
vector<token>::size_type i=0;
while(itRE!=regularExpression.end())
	{
	if(itRE->isOperator() && itRE->symbol=='?')
		signsNumber++;
	++itRE;
	}
itRE=regularExpression.begin();
if(signsNumber)
	{
	newRE.resize(regularExpression.size()+(3*signsNumber));
	while(itRE!=regularExpression.end())
		{
		if(itRE->isOperator() && itRE->symbol=='?')
			{
			d=newRE[i-1];
			
			if(d.isSymbol())
				{
				newRE[i-1].toOperator('(');
				newRE[i++]=d;
				newRE[i++].toOperator('|');
				newRE[i++].toEmpty();
				newRE[i++].toOperator(')');
				}
			else if(d.isOperator() && d.symbol==')')
				{
				vector<token>::size_type j,numParenthesis=1,k,numChars;
				vector<token> subString;
				for(j=i-1; numParenthesis; j--)
					{
					if(newRE[j-1].isOperator() && newRE[j-1].symbol==')')
						numParenthesis++;
					else if(newRE[j-1].isOperator() && newRE[j-1].symbol=='(')
						numParenthesis--;
					}
				numChars=i-j;
				subString.resize(numChars);
				for(k=0; k<numChars; k++)
					{
					subString[k]=newRE[j++];
					}
				for(k=0, j=(i-numChars+1); k<numChars; k++, j++)
					{
					newRE[j]=subString[k];
					}
				newRE[j++].toOperator('|');
				newRE[j++].toEmpty();
				newRE[j++].toOperator(')');
				i+=4;
				}
			}
		else
			{
			newRE[i++]=*itRE;
			}
		++itRE;
		}
	regularExpression=newRE;
	}
}

void REEvaluator::removePositiveLock()
{
vector<token>::const_iterator itRE(regularExpression.begin());
vector<token> newRE;
char d;
int signsNumber=0;
vector<token>::size_type increment=0, i=0;
while(itRE!=regularExpression.end())
	{
	if(itRE->isOperator() && itRE->symbol=='+')
		{
		signsNumber++;
		if(!((itRE-1)->isOperator()))
			{
			increment+=4;
			}
		else if((itRE-1)->isOperator() && (itRE-1)->symbol==')')
			{
			int numParenthesis=1;
			vector<token>::const_iterator temp=(itRE-1);
			while(temp!=(regularExpression.begin()) && numParenthesis)
				{
				temp--;
				if(temp->isOperator() && temp->symbol==')')
					numParenthesis++;
				else if(temp->isOperator() && temp->symbol=='(')
					numParenthesis--;
				}
			increment+=(itRE-temp)+3;
			}
		}
	++itRE;
	}
itRE=regularExpression.begin();
if(signsNumber)
	{
	newRE.resize(regularExpression.size()+increment);
	while(itRE!=regularExpression.end())
		{
		if(itRE->isOperator() && itRE->symbol=='+')
			{
			token t=newRE[i-1];
			d=newRE[i-1].symbol;
			if(!(newRE[i-1].isOperator()))
				{
				newRE[i-1].toOperator('(');
				newRE[i++]=t;
				newRE[i++].toOperator('<');
				newRE[i++]=t;
				newRE[i++].toOperator('*');
				newRE[i++].toOperator(')');
				}
			else if(newRE[i-1].isOperator() && newRE[i-1].symbol==')')
				{
				vector<token>::size_type j,numParenthesis=1,k,numChars;
				vector<token> subString;
				for(j=i-1; numParenthesis; j--)
					{
					if(newRE[j-1].isOperator() && newRE[j-1].symbol==')')
						numParenthesis++;
					else if(newRE[j-1].isOperator() && newRE[j-1].symbol=='(')
						numParenthesis--;
					}
				numChars=i-j;
				subString.resize(numChars);
				for(k=0; k<numChars; k++)
					{
					subString[k]=newRE[j++];
					}
				for(k=0, j=(i-numChars+1); k<numChars; k++, j++)
					{
					newRE[j]=subString[k];
					}
				newRE[j++].toOperator('<');
				for(k=0; k<numChars; k++)
					{
					newRE[j++]=subString[k];
					}
				newRE[j++].toOperator('*');
				newRE[j++].toOperator(')');
				i+=numChars+4;
				}
			}
		else
			{
			newRE[i++]=*itRE;
			}
		++itRE;
		}
	regularExpression=newRE;
	}
}

/* Esta funci¢n inserta en la ER, el operador que manejaremos para la
concatenaci¢n: '<', pues nos facilitará el tratamiento de la cadena
*/
void REEvaluator::insertOperator()
{
vector<token>::const_iterator itRE(regularExpression.begin());
vector<token> newRE(regularExpression.size()*2);
vector<token>::size_type i=0, insertionsNumber=0;

while(itRE!=regularExpression.end())
	{
	newRE[i++]=*itRE;
	if((itRE+1)==regularExpression.end())
		break;

	if((itRE->isSymbol() && (itRE+1)->isSymbol()) ||
		(itRE->isSymbol() && (itRE+1)->isOperator() && (itRE+1)->symbol=='(') ||
		((itRE+1)->isSymbol() && itRE->isOperator() && (itRE->symbol==')' || itRE->symbol=='*')) ||
		(itRE->isOperator() && (itRE->symbol==')' || itRE->symbol=='*') && (itRE+1)->isOperator() && (itRE+1)->symbol=='('))
		{
		newRE[i].toOperator('<');
		++i;
		++insertionsNumber;
		}

	++itRE;
	}

if(insertionsNumber)
	{
	regularExpression.resize(i);
	copy(newRE.begin(),newRE.begin()+i,regularExpression.begin());
	}

}

int REEvaluator::precedence(char Operator)
{
switch(Operator)
	{
	case '(':	return 4;
	case '*':	return 3;
	case '<':	return 2;
	}
return 1; 
}

void REEvaluator::createAFN()
{
vector<token>::const_iterator itRPN(RPNregularExpression.begin());
while(itRPN!=RPNregularExpression.end())
	{
	if(itRPN->vt==token::OPERATOR)
		switch(itRPN->symbol)
			{
			case '*':
				{
				AFN *topAFN=stackAFNs.top();
				stackAFNs.pop();
				stackAFNs.push(Kleene(topAFN));
				break;
				}
			case '<':
				{
				AFN *aux1, *op1;
				aux1=stackAFNs.top();
				stackAFNs.pop();
				op1=stackAFNs.top();
				stackAFNs.pop();
				stackAFNs.push(uniteAFNs(op1,aux1));
				break;
				}
			case '|':
				{
				AFN *op1, *op2;
				op1=stackAFNs.top();
				stackAFNs.pop();
				op2=stackAFNs.top();
				stackAFNs.pop();
				stackAFNs.push(alternateAFNs(op1,op2));
				break;
				}
			}
	else
		{
		stackAFNs.push(createSymbolAFN(*itRPN));
		}
		
	++itRPN;
	}
pafn=stackAFNs.top();
stackAFNs.pop();
}

REEvaluator::AFN *REEvaluator::createSymbolAFN(token t)
{
AFN *newAFN=new AFN;
state *newState;
stateNum++;
newState=new state;
newState->stateNumber=stateNum;
newState->connectionsNumber=1;
newState->pConnections=new connection;
newState->pConnections->transition=t;
newState->pConnections->nextState=new state;
stateNum++;
newState->pConnections->nextState->stateNumber=stateNum;

newAFN->beg=newState;
newAFN->end=newState->pConnections->nextState;
return newAFN;
}

REEvaluator::AFN *REEvaluator::alternateAFNs(AFN *afn1, AFN *afn2)
{
AFN *newAFN=new AFN;
state *firstState, *lastState;
stateNum++;
firstState=new state;
firstState->stateNumber=stateNum;
firstState->pConnections=new connection [2];
firstState->connectionsNumber=2;
firstState->pConnections[0].transition.vt=token::EMPTY;
firstState->pConnections[0].nextState=afn1->beg;
firstState->pConnections[1].transition.vt=token::EMPTY;
firstState->pConnections[1].nextState=afn2->beg;
stateNum++;
lastState=new state;
lastState->stateNumber=stateNum;
afn1->end->pConnections=new connection;
afn1->end->pConnections->transition.vt=token::EMPTY;
afn1->end->connectionsNumber=1;
afn2->end->pConnections=new connection;
afn2->end->pConnections->transition.vt=token::EMPTY;
afn2->end->connectionsNumber=1;
afn1->end->pConnections->nextState=lastState;
afn2->end->pConnections->nextState=lastState;
newAFN->beg=firstState;
newAFN->end=lastState;

delete afn1;
delete afn2;
return newAFN;
}

REEvaluator::AFN *REEvaluator::Kleene(AFN *afn1)
{
AFN *newAFN=new AFN;
state *firstState, *lastState;
firstState=new state;
stateNum++;
firstState->stateNumber=stateNum;
firstState->pConnections=new connection[2];
firstState->connectionsNumber=2;
firstState->pConnections[0].transition.vt=token::EMPTY;
firstState->pConnections[0].nextState=afn1->beg;
lastState=new state;
stateNum++;
lastState->stateNumber=stateNum;
firstState->pConnections[1].transition.vt=token::EMPTY;
firstState->pConnections[1].nextState=lastState;

afn1->end->pConnections=new connection[2];
afn1->end->connectionsNumber=2;
afn1->end->pConnections[0].transition.vt=token::EMPTY;
afn1->end->pConnections[0].nextState=afn1->beg;
afn1->end->pConnections[1].transition.vt=token::EMPTY;
afn1->end->pConnections[1].nextState=lastState;

newAFN->beg=firstState;
newAFN->end=lastState;

delete afn1;
return newAFN;
}

REEvaluator::AFN *REEvaluator::uniteAFNs(AFN *afn1, AFN *afn2)
{
AFN *newAFN=new AFN;
afn1->end->connectionsNumber=afn2->beg->connectionsNumber;
if(afn1->end->connectionsNumber==1)
	{
	afn1->end->pConnections=new connection;
	afn1->end->pConnections->transition=afn2->beg->pConnections->transition;
	afn1->end->pConnections->nextState=afn2->beg->pConnections->nextState;
	}
else
	{
	afn1->end->pConnections=new connection [afn1->end->connectionsNumber];
	afn1->end->pConnections[0].transition=afn2->beg->pConnections[0].transition;
	afn1->end->pConnections[0].nextState=afn2->beg->pConnections[0].nextState;
	afn1->end->pConnections[1].transition=afn2->beg->pConnections[1].transition;
	afn1->end->pConnections[1].nextState=afn2->beg->pConnections[1].nextState;
	}

newAFN->beg=afn1->beg;
newAFN->end=afn2->end;

delete afn2->beg;
delete afn1;
delete afn2;
return newAFN;
}

//establece el conjunto de estados a los que se puede llegar con transiciones vacías
//desde los estados actuales
void REEvaluator::lockET()
{
stack<state *> stackStates1, stackStates2;
state *pState;
while(stackStates.size())
	{
	stackStates1.push(stackStates.top());
	stackStates.pop();
	}
while(stackStates1.size())
	{
	pState=stackStates1.top();
	stackStates1.pop();
	pState->lockE(stackStates);
	pState->deleteVisit();
	while(stackStates.size())
		{
		stackStates2.push(stackStates.top());
		stackStates.pop();
		}
	}
while(stackStates2.size())
	{
	stackStates.push(stackStates2.top());
	stackStates2.pop();
	}
}

//establece los estados a los que se puede llegar con el símbolo 'symbol' desde el conjunto
//de estados actuales
void REEvaluator::move(char symbol)
{
stack<state *> tempStackStates;
state *pState;
while(stackStates.size())
	{
	pState=stackStates.top();
	stackStates.pop();
	if(pState->pConnections)
		{
		switch(pState->connectionsNumber)
			{
			case 1:
				if(pState->pConnections->transition.isSymbol())
					{
					if(pState->pConnections->transition.nospace)
						{
						if(!isspace(symbol))
							tempStackStates.push(pState->pConnections->nextState);
						}
					else if(pState->pConnections->transition.interval)
						{
						if(pState->pConnections->transition.isInInterval(symbol))
							tempStackStates.push(pState->pConnections->nextState);
						}
					else if(pState->pConnections->transition.anysymbol)
						{
						tempStackStates.push(pState->pConnections->nextState);
						}
					else if(pState->pConnections->transition.symbol==symbol)
						tempStackStates.push(pState->pConnections->nextState);
					}
				break;
			case 2:
				if(pState->pConnections[0].transition.isSymbol())
					{
					if(pState->pConnections[0].transition.nospace)
						{
						if(!isspace(symbol))
							tempStackStates.push(pState->pConnections[0].nextState);
						}
					else if(pState->pConnections[0].transition.interval)
						{
						if(pState->pConnections[0].transition.isInInterval(symbol))
							tempStackStates.push(pState->pConnections[0].nextState);
						}
					else if(pState->pConnections[0].transition.anysymbol)
						{
						tempStackStates.push(pState->pConnections[0].nextState);
						}
					else if(pState->pConnections[0].transition.symbol==symbol)
						tempStackStates.push(pState->pConnections[0].nextState);
					}
				if(pState->pConnections[1].transition.isSymbol())
					{
					if(pState->pConnections[1].transition.nospace)
						{
						if(!isspace(symbol))
							tempStackStates.push(pState->pConnections[1].nextState);
						}
					else if(pState->pConnections[1].transition.interval)
						{
						if(pState->pConnections[1].transition.isInInterval(symbol))
							tempStackStates.push(pState->pConnections[1].nextState);
						}
					else if(pState->pConnections[1].transition.anysymbol)
						{
						tempStackStates.push(pState->pConnections[1].nextState);
						}
					else if(pState->pConnections[1].transition.symbol==symbol)
						tempStackStates.push(pState->pConnections[1].nextState);
					}
				break;
			}
		}
	}
while(tempStackStates.size())
	{
	stackStates.push(tempStackStates.top());
	tempStackStates.pop();
	}
}

void REEvaluator::deleteStates()
{
pafn->beg->saveStates(stackStates);
while(stackStates.size())
	{
	delete (stackStates.top());
	stackStates.pop();
	}

}

REEvaluator::REEvaluator(char *regExp):
definedSymbols(std::numeric_limits<unsigned char>::max()+1)
{
char *pBegin=regExp, *pEnd=regExp+strlen(regExp), c;
token temp;
bool nospace=false, anysymbol=false;

while(pBegin!=pEnd)
	{
	c=*pBegin;
	if(c=='\\')
		{
		++pBegin;
		if(pBegin!=pEnd)
			{
			temp.toSymbol(*pBegin);
			regularExpression.push_back(temp);
			definedSymbols[static_cast<unsigned char>(*pBegin)]=true;
			}
		else
			throw syntax_error();
		}
	else
		{
		if(isOperator(c))
			{
			temp.toOperator(c);
			regularExpression.push_back(temp);
			}
		else
			{
			if(c=='#')
				{
				temp.toNospace();
				nospace=true;
				regularExpression.push_back(temp);
				}
			else if(c=='@')
				{
				temp.toAnysymbol();
				anysymbol=true;
				regularExpression.push_back(temp);
				}
			else
				{
				temp.toSymbol(c);
				regularExpression.push_back(temp);
				definedSymbols[static_cast<unsigned char>(c)]=true;
				}
			}
		}
	++pBegin;
	temp=token();
	}

if(anysymbol)
	{
	for(unsigned int i=0; i<(std::numeric_limits<unsigned char>::max()+1); ++i)
		{
		definedSymbols[static_cast<unsigned char>(i)]=true;
		}
	}
else if(nospace)
	{
	for(unsigned int i=0; i<(std::numeric_limits<unsigned char>::max()+1); ++i)
		{
		if(!isspace(i))
			definedSymbols[static_cast<unsigned char>(i)]=true;
		}
	}

stateNum=0;
pafn=new AFN;
removeSquareBrackets();
removeQuestionSign();
removePositiveLock();
insertOperator();
REtoRPN();
createAFN();
}

REEvaluator::~REEvaluator()
{
if(pafn)
	{
	deleteStates();
	delete pafn;
	}
}

//esta función es riesgosa porque no funciona bien cuando se busca el símbolo \0,
//pues este es el terminador de cadena, y no sirve pasarle la longitud de la cadena
//porque al hacer strlen(str), si hay un \0 en la cadena, la longitud es incorrecta
//se podrá usar sólo cuando entre los símbolos válidos no esté el \0
bool REEvaluator::eval(const char *str)
{
bool accepted=false;
pafn->beg->lockE(stackStates);
pafn->beg->deleteVisit();
while(*str)
	{
	move(*str);
	if(stackStates.empty())
		return false;
	lockET();
	++str;
	}
while(stackStates.size())
	{
	if(stackStates.top()==pafn->end)
		accepted=true;
	stackStates.pop();
	}
return accepted;
}

bool REEvaluator::eval(const string &s)
{
string::const_iterator it=s.begin();
bool accepted=false;
pafn->beg->lockE(stackStates);
pafn->beg->deleteVisit();
while(it!=s.end())
	{
	move(*it);
	if(stackStates.empty())
		return false;
	lockET();
	++it;
	}
while(stackStates.size())
	{
	if(stackStates.top()==pafn->end)
		accepted=true;
	stackStates.pop();
	}
return accepted;
}

bool REEvaluator::eval(const char c)
{
bool accepted=false;
pafn->beg->lockE(stackStates);
pafn->beg->deleteVisit();
move(c);
if(stackStates.empty())
	return false;
lockET();

while(stackStates.size())
	{
	if(stackStates.top()==pafn->end)
		accepted=true;
	stackStates.pop();
	}
return accepted;
}

bool REEvaluator::isSymbol(const char c)
{
return (definedSymbols[static_cast<unsigned char>(c)]);
}

bool REEvaluator::hasAcceptedState() const
{
stack<state *> temp;
temp=stackStates;
bool accepted=false;
while(temp.size())
	{
	if(temp.top()==pafn->end)
		accepted=true;
	temp.pop();
	}

return accepted;
}

bool REEvaluator::searchLexema(istream &is, string &s, deque<char> &newStr, bool delimiter, unsigned int pos, bool stdinput)
{
deque<char>::size_type n=newStr.size();

if(n)
	{
	char *s1=new char[n+1];
	copy(newStr.begin(),newStr.end(),s1);
	s1[n]=0;
	while(n)
		{
		if(eval(s1,s1+n))
			break;
		else
			{
			--n;
			s1[n]=0;
			}
		}

	if(n)
		{
		s.resize(n);
		copy(s1,s1+n,s.begin());
		if(stdinput)
			is.ignore(delimiter? n+1: n);
		else
			{
			is.seekg(pos,ios_base::beg);
			is.ignore(delimiter? n+1: n);
			}
		delete [] s1;
		return true;
		}
	else
		{
		if(!stdinput)
			is.seekg(pos,ios_base::beg);
		delete [] s1;
		return false;
		}

	}
else
	{
	if(!stdinput)
		is.seekg(pos,ios_base::beg);
	return false;
	}
}

bool REEvaluator::getLexema(istream &is,string &s, bool smallest)
{
static deque<char> newStr;
char c=0;
newStr.clear();

if(smallest)
	{
	unsigned int pos=is.tellg();
	bool accepted=false;
	pafn->beg->lockE(stackStates);
	pafn->beg->deleteVisit();
	while(is.get(c))
		{
		move(c);
		if(stackStates.empty())
			{
			is.seekg(pos,ios_base::beg);
			return false;
			}
		newStr.push_back(c);
		lockET();
		if(hasAcceptedState())
			{
			s.resize(newStr.size());
			copy(newStr.begin(),newStr.end(),s.begin());
			while(stackStates.size())
				{
				stackStates.pop();
				}
			return true;
			}
		if(is.peek()==EOF)
			break;
		}
	while(stackStates.size())
			{
			stackStates.pop();
			}
	is.seekg(pos,ios_base::beg);
	return false;
	}
else
	{//creo que es más veloz una tabla de estados y símbolos con referencia al estado al que nos
	//lleva, que el esquema de apuntadores, aunque ocuparía más memoria
	long pos=-1;
	bool stdinput=false;
	if((&is==(istream *)&std::cin) || (&is==(istream *)&std::wcin))
		stdinput=true;

	if(stdinput)
		{
		streambufw sb(is.rdbuf());
		char *p=sb.begin();

		while(p!=sb.end())
			{
			c=*p;
			if(definedSymbols[static_cast<unsigned char>(c)])
				newStr.push_back(c);
			else
				break;
			++p;
			}
		}
	else
		{
		pos=is.tellg();

		while(is.get(c))
			{
			if(definedSymbols[static_cast<unsigned char>(c)])
				newStr.push_back(c);//tal vez lockET(),...,if(stackStates.empty()) break; ir hacia atras buscando un estado de aceptación
			else
				break;
			if(is.peek()==EOF)
				break;
			}
		}
	
	return searchLexema(is,s,newStr,false,pos,stdinput);
	}
}

bool REEvaluator::getLexemaWithEscape(istream &is,string &s, char escape)
{
static deque<char> newStr;
char c=0;
newStr.clear();
bool lastc=false;
char lc;

unsigned int pos=is.tellg();
bool accepted=false;
pafn->beg->lockE(stackStates);
pafn->beg->deleteVisit();
while(is.get(c))
	{
	move(c);
	if(stackStates.empty())
		{
		is.seekg(pos,ios_base::beg);
		return false;
		}
	newStr.push_back(c);
	lockET();
	if(!(lastc && lc==escape))
		{
		if(hasAcceptedState())
			{
			s.resize(newStr.size());
			copy(newStr.begin(),newStr.end(),s.begin());
			while(stackStates.size())
				{
				stackStates.pop();
				}
			return true;
			}
		}
	lastc=true;
	lc=c;
	if(is.peek()==EOF)
		break;
	}
while(stackStates.size())
	{
	stackStates.pop();
	}
is.seekg(pos,ios_base::beg);
return false;
}

bool REEvaluator::getLexema(istream &is,string &s, char delimiter, bool smallest)
{
static deque<char> newStr;
char c=0;
newStr.clear();
unsigned int pos=is.tellg();

while(is.get(c))
	{
	if(c==delimiter)
		break;
	if(definedSymbols[static_cast<unsigned char>(c)])
		newStr.push_back(c);
	else
		break;

	if(is.peek()==EOF)
		break;
	}

return searchLexema(is,s,newStr,true,pos);
}

bool REEvaluator::getLexema(istream &is,string &s, char delimiter, char escape, bool smallest)
{
static deque<char> newStr;
char c=0;
newStr.clear();
unsigned int pos=is.tellg();
bool lastc=false;
char lc;

while(is.get(c))
	{
	if(c==delimiter)
		{
		if(lastc)
			{
			if(lc==escape)
				{
				if(definedSymbols[static_cast<unsigned char>(c)])
					{
					newStr.push_back(c);
					lastc=true;
					lc=c;
					if(is.peek()==EOF)
						break;
					else
						continue;
					}
				else
					break;
				}
			}

		break;
		}
	if(definedSymbols[static_cast<unsigned char>(c)])
		{
		newStr.push_back(c);
		lastc=true;
		lc=c;
		}
	else
		break;

	if(is.peek()==EOF)
		break;
	}

return searchLexema(is,s,newStr,true,pos);
}

istream &REEvaluator::skipNoSymbols(istream &is)
{
char c=0;

while(is.get(c))
	{
	if(definedSymbols[static_cast<unsigned char>(c)])
		{
		is.putback(c);
		break;
		}
	if(is.peek()==EOF)
		{
		is.clear(ios_base::eofbit);
		break;
		}
	}

return is;
}

}

#endif