re.cpp

输入一个正则表达式

#include <iostream>
#include "RE.h"

//////////////////////////////////////////////////////////////////////////
//	class Scanner
//
void Scanner::get()
{
	int c;

	do
	{
		c = re[off ++];
	}while(c == ' ' || c == '\t');
	
	if(('a' <= c && c <= 'z') || ('0' <= c && c <= '9'))	// charset
	{
		token = CHARS;
		value = rawMap[c - '0'];
	}
	else if(c == 'E' || c == 'O' || c == '+' || c == '-' || 
			c == '~' || c == '(' || c == ')' || c == '*')
	{
		token = SYMBOL;
		value = c;
	}
	else if(c == 0)
	{
		token = ENDSTRING;
	}
	else 
	{
		token = SCAN_ERR;
		value = c;
	}
}
// count how many chacters are used, and build the map
void Scanner::analyze()
{
	int c, i = 0, counter;
	
	// Map character into rawMap
	while( (c = re[i++]) != NULL)
	{
		if((('a' <= c && c <= 'z') || ('0' <= c && c <= '9')) && rawMap[c - '0'] == 0)
		{
			rawMap[c - '0'] = 1;
			mapSize++;
		}
	}
	if(map != NULL)	delete []map;
	map = new int[mapSize];

	// Build map, map[num] can map num to character
	counter = 0;
	for(i = 0;i < MAP_SIZE;i ++)
	{
		if(rawMap[i])
		{
			map[counter] = i + '0';
			rawMap[i] = counter ++;
		}
		else
		{
			rawMap[i] = -1;
		}
	}
}
//////////////////////////////////////////////////////////////////////////
// class RegularExp
//
void RegularExp::parse(void)
{
	scanner.get();
	nfa = unionSet();
	if(scanner.token != scanner.ENDSTRING)
	{
		error("Error end of the Expression");
	}
	nfa->makeDeadState();
}
NFA *RegularExp::unionSet()
{
	NFA *n1, *n2;

	n1 = intersectionSet();
	while(scanner.token == scanner.SYMBOL && scanner.value == '+')
	{
		scanner.get();
		n2 = intersectionSet();
		n1->unionSet(n2);
		delete n2;
	}	
	return n1;
}
NFA *RegularExp::intersectionSet()
{
	NFA *n1, *n2;

	n1 = join();
	while(scanner.token == scanner.SYMBOL && scanner.value == '-')
	{
		scanner.get();
		n2 = join();
		n1->intersectionSet(n2);
		delete n2;
	}	
	return n1;
}
NFA *RegularExp::join()
{
	NFA *n1, *n2;

	n1 = complementSet();
	while(	(scanner.token == scanner.SYMBOL && scanner.value == '(') ||
			(scanner.token == scanner.SYMBOL && scanner.value == '~') ||
			(scanner.token == scanner.SYMBOL && scanner.value == 'E') ||
			(scanner.token == scanner.CHARS) )
	{
		n2 = complementSet();
		n1->join(n2);
		delete n2;
	}	
	return n1;
}
NFA *RegularExp::complementSet()
{
	NFA *n1;
	int counter = 0;

	while(scanner.token == scanner.SYMBOL && scanner.value == '~')
	{
		scanner.get();
		++counter;
	}
	n1 = closure();
	if(counter % 2 == 1)
	{
		n1->complementSet();	
	}
	return n1;
}
NFA *RegularExp::closure()
{
	NFA *n1;
	int once = 0;

	n1 = element();
	while(scanner.token == scanner.SYMBOL && scanner.value == '*')
	{
		scanner.get();
		once = 1;
	}
	if(once)
	{
		n1->closure();
	}
	return n1;
}
NFA *RegularExp::element()
{
	NFA *n1;
	if(scanner.token == scanner.SYMBOL && scanner.value == '(')
	{
		scanner.get();
		n1 = unionSet();
		if(scanner.token == scanner.SYMBOL && scanner.value == ')')
		{
			scanner.get();
		}
		else
		{
			error("() must match");
		}
	}
	else if(scanner.token == scanner.SYMBOL && scanner.value == 'E')
	{
		n1 = new NFA(scanner.mapSize);
		n1->emptyStr();
		scanner.get();
	}
	else if(scanner.token == scanner.SYMBOL && scanner.value == 'O')
	{
		n1 = new NFA(scanner.mapSize);
		n1->emptySet();
		scanner.get();
	}
	else if(scanner.token == scanner.CHARS)
	{
		n1 = new NFA(scanner.mapSize);
		n1->alphabet(scanner.value);
		scanner.get();
	}
	else
	{
		error("Unknow string");
	}
	return n1;
}
// Deal with the errors occurd in parsing
int	RegularExp::error(const char *msg)
{
	cerr << msg << endl;
	return 0;
}