dn转换.cpp

用图实现的正规式转NFA转DFA

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<ctype.h>
#include<process.h>
#include<bitset>
#include<vector>
using namespace std;

//边结点
typedef struct Node{
	int verIndex;
	char st[100];
	struct Node* nextArc;
}Edge;

//状态节点类型
#define START_NODE 1
#define END_NODE 2
#define NORMAL_NODE 3

//状态结点
typedef struct{
	char ver;
	int type;
	Edge* firstArc;
}Vertex;

//最大的顶点数
#define MAX_VERTEX_NUM 100

//最大的字母数
#define MAX_LETTER_NUM 400

#define MAX_TALBE_SIZE 100

typedef bitset<MAX_VERTEX_NUM> VertexSet;

//图类型
typedef struct{
	Vertex vertexs[MAX_VERTEX_NUM];
	int vertexNum;

	char alphaBeta[MAX_LETTER_NUM];
	int letterNum;
	char st[400]; //存放输入的正则表达式
	
	//产生状态集合表
	VertexSet table[MAX_TALBE_SIZE];
	int row;  //表的行数
}Graph;



//初始化图
void Init(Graph* G){
	for(int i = 0 ; i < MAX_VERTEX_NUM;i++)
		G->vertexs[i].firstArc = NULL;
	G->vertexNum = 0;

}

//返回图中第i个结点字符
char LocateVer(Graph* G,int i){
	if(i <0 || i>=G->vertexNum) return '\0';
	return G->vertexs[i].ver;
}

//图搜索时的访问标志
#define VISITED 1
#define NONVISITED 0
//访问标志数组
int visited[MAX_VERTEX_NUM];

//深度优先输出
void DFS(Graph* G,int startVer){
	visited[startVer] = VISITED;
	Edge* p;
	p = G->vertexs[startVer].firstArc;
	while(p != NULL){
		if(!visited[p->verIndex]){
			printf("%c --->\" %s \" ---->%c\n",
				LocateVer(G,startVer),p->st,LocateVer(G,p->verIndex));
			DFS(G,p->verIndex);
		}
		p = p->nextArc;
	}
}

//深度优先搜索
void DFS_output(Graph* G){
	for(int i = 0 ; i < G->vertexNum;i++)
		visited[i] = NONVISITED;
	for(i = 0 ; i< G->vertexNum;i++)
		if(!visited[i]) DFS(G,i);
}

//按顶点顺序打印图中每一条边
void printGraph(Graph* G){
	printf("\n\n********** 打印图中内容 ************\n");
	for(int i = 0; i < G->vertexNum;i++){
		Edge* p = G->vertexs[i].firstArc;
		while(p != NULL){
			printf("%c --->\" %s \" ---->%c\n",
				LocateVer(G,i),p->st,LocateVer(G,p->verIndex));
			p = p->nextArc;
		}
	}
	printf("\n\n\n");

}

//向图中位置pos处，插入一个名称为c,类型为type的顶点
void InsertVertext(Graph* G,int pos,char c,int type){
	if(pos < 0 || pos > G->vertexNum) {
		printf("****** 插入位置不合法! ***********\n");
		return;
	}
	if(G->vertexNum == MAX_VERTEX_NUM){
		printf("****** 图中节点数已达到最大值，无法插入! *********\n");
		return;
	}

	for(int i = 0 ; i < G->vertexNum;i++){
		Edge* p = G->vertexs[i].firstArc;
		while(p != NULL){
			if(p->verIndex >= pos) p->verIndex ++;
			p = p->nextArc;
		}
	}

	G->vertexNum++;
	for(i = G->vertexNum; i >pos ;i--)
		G->vertexs[i] = G->vertexs[i-1];
	G->vertexs[pos].firstArc = NULL;
	G->vertexs[pos].ver = c;
	G->vertexs[pos].type = type;
}

//输出状态集合set
void outputSet(Graph* G,VertexSet set){
	printf("{");
	for(int i = 0 ; i < G->vertexNum;i++)
		if(set.test(i)) printf(" %c ",LocateVer(G,i));
	printf("}");
}

//用深度优先搜索返回 ver 的ε闭包
VertexSet CloserDFS(Graph* G,int ver){
	VertexSet result;
	Edge* p = G->vertexs[ver].firstArc;
	visited[ver] = VISITED;
	result.set(ver);
	while(p != NULL){
		if(strcmp(p->st,"ε") == 0){			
			if(!visited[p->verIndex]) 
				result |= CloserDFS(G,p->verIndex);
		}
		p = p->nextArc;
	}
	return result;
}

//返回顶点ver的ε闭包
VertexSet Closer(Graph* G,int ver){
	for(int i = 0 ; i < G->vertexNum;i++)
		visited[i] = NONVISITED;
    return CloserDFS(G,ver);	 
}

//
VertexSet SetThrough(Graph* G,const VertexSet& s,char ch){
	VertexSet result;
	for(int i = 0 ; i < G->vertexNum;i++){
		if(s.test(i)) {
			Edge* p = G->vertexs[i].firstArc;
			while(p != NULL){
				if(p->st[0] == ch)
					result.set(p->verIndex);
				p = p->nextArc;
			}
		}
	}
	return result;
}

//集合b关于字符ch的Ich闭包
VertexSet Move(Graph* G,VertexSet& b,char ch){
	VertexSet  result;

	//存放G中每个状态的?闭包
	vector<VertexSet> v(G->vertexNum,result);
	for(int i = 0 ; i < G->vertexNum;i++)
		v[i] = Closer(G,i);
	
	result = SetThrough(G,b,ch);
	VertexSet tmpSet;
	for( i = 0 ; i < G->vertexNum;i++)
		if(result.test(i)) tmpSet |= v[i];
	result |= tmpSet;

	return result;
}

void outputStatesTable(Graph* G){
	for(int i = 0; i < G->row ; i++){
		for(int j = 0 ; j < G->letterNum + 1;j++){
			int index = i * (G->letterNum + 1) + j;
			outputSet(G,G->table[index]);
			printf("\t");
		}
		printf("\n");
	}
}
					   



//
void BuildSituTable(Graph* G){
	int col = G->letterNum + 1;
	int row = 0;
	int k = 0;
	G->table[0] = Closer(G,0);
	while(1){
		//处理一行
		G->table[row*col] = G->table[k];
		for(int i = 1; i < col;i++)
			G->table[row*col + i] = Move(G,G->table[k],G->alphaBeta[i-1]);
		row++;

		//判断是否要结束
		int next = k;
		bool find = false;
		for(int j = k + 1; j < row*col && !find; j++){
			for(int m = 0; m < row ; m++)
				if(G->table[m*col] == G->table[j]) break;
			if(m == row) find = true;
		}
		if(!find) break;
		k = j - 1;
	}
	G->row = row;
}

//去掉字符串中的空格
void Trim(char st[]){
	for(int i = 0 ; st[i];)
		if(isspace(st[i])){
			for(int j = i;st[j];j++)
				st[j] = st[j+1];
		}
		else i++;
}

//***去掉字符串最外层多余的括号
void DeleteBrackets(char st[]){
	int a = 0;
	int b = strlen(st) - 1;
	int k = 0;

	while(st[0] == '('){
		int k = 1;
		for(int i = 1 ; st[i] && k != 0; i++){
			if(st[i] == '(') k++;
			if(st[i] == ')') k--;
		}
		if(st[i-1] != ')' || st[i] != '\0') break;
		st[i - 1] = '\0';
		strcpy(st,st+1);
	}
}

//判断顶点下标是否合法
bool isLegal(Graph* G,int ver){
	return ver>=0 && ver< G->vertexNum;
}

//在图中添加一条 ver-->toVer的边
void AddEdge(Graph* G,int ver,int toVer,char st[]){
	if(!isLegal(G,ver) || !isLegal(G,toVer)){
		printf("***** (%d-->%d) 顶点下标越界! **********\n",ver,toVer);
		return;
	}


	Edge* p = (Edge*)malloc(sizeof(Edge));
	strcpy(p->st,st);
	p->verIndex = toVer;
	p->nextArc = G->vertexs[ver].firstArc;
	G->vertexs[ver].firstArc = p;
}

//在图中删除一条边
void DeleteEdge(Graph* G,int pos,Edge* p){
	if(!isLegal(G,pos)) {
		printf("***** (%d) 顶点下标越界! **********\n",pos);
		return;
	}
	
	if(G->vertexs[pos].firstArc == NULL) return;
	if(G->vertexs[pos].firstArc == p){
		G->vertexs[pos].firstArc = p->nextArc;
	}
	else{
		for(Edge* q = G->vertexs[pos].firstArc;q->nextArc != NULL && q->nextArc != p;q = q->nextArc);
		if(q->nextArc != NULL) q->nextArc = p->nextArc;
		else {
			printf("**** 没有找到要删除的边! *****\n");
			return;
		}
	}
	free(p);
}

//分解字符串
char DivideStr(char st[],char firstSt[],char secondSt[]){
	int FI = 0;
	int k = 0;

	DeleteBrackets(st);
	if(isalnum(st[k])){
		while(isalnum(st[k])){
			firstSt[FI++] = st[k++];
		}
	}
	else if(st[0] == '('){
		int n = 1;
		firstSt[FI++] = '(';
		for(k = 1;n != 0; k++){
			if(st[k] == '(') n++;
			else if(st[k] == ')') n--;
			firstSt[FI++] = st[k];
		}
	}
	else{
		printf("******  %s 非法开头字符 %c ***********\n",st,st[k]);
		return '!';
	}

	if(st[k] == '\0'){
		firstSt[0] = st[0];
		firstSt[1] = '\0';
		strcpy(secondSt,st+1);
		return '+';
	}

	if(st[k] == '*' ){
		k++;		
		if(st[k] == '\0'){
			firstSt[FI] = '\0';
			if(firstSt[FI - 1] == ')'){
				firstSt[--FI] = '\0';
				strcpy(firstSt,firstSt+1);
			}
			secondSt[0] = '\0';
			return '*';
		}
		firstSt[FI++] = '*';
	}

	if(st[k] == '|'){
		strcpy(secondSt,st+k+1);
		firstSt[FI] = '\0';
		if(firstSt[FI - 1] == ')'){
			firstSt[--FI] = '\0';
			strcpy(firstSt,firstSt+1);
		}
		return '|';
	}

	if(isalnum(st[k]) || st[k] == '('){
		strcpy(secondSt,st+k);
		firstSt[FI] = '\0';
		if(firstSt[FI - 1] == ')'){
			firstSt[--FI] = '\0';
			strcpy(firstSt,firstSt+1);
		}
		return '+';
	}

	printf("******  %s 非法操作符 %c ***********\n",st,st[k]);
	return '!';
}


//判断是否为最简
bool isSimplest(char st[]){
	return st[1] == '\0' || strcmp(st,"ε") == 0 ;
}

//将正则式变为DFA
void ToDFA(Graph* G){
	for(int i = 0 ; i < G->vertexNum;i++){
		Edge* p = G->vertexs[i].firstArc;
		while(p != NULL){
			if(isSimplest(p->st)) p = p->nextArc;
			else{
				char firstSt[100] , secondSt[100];
				char oper ;
				oper = DivideStr(p->st,firstSt,secondSt);
				if(oper == '*'){
					int newNode = G->vertexNum - 1;
					InsertVertext(G,newNode,'0' + newNode , NORMAL_NODE);
					AddEdge(G,newNode,p->verIndex,"ε");
					AddEdge(G,newNode,newNode,firstSt);
					AddEdge(G,i,newNode,"ε");
					Edge* q = p;
					p = p->nextArc;
					DeleteEdge(G,i,q);
				}
				else if(oper == '|'){
					strcpy(p->st,firstSt);
					AddEdge(G,i,p->verIndex,secondSt);
				}
				else if(oper == '+'){
					int newNode = G->vertexNum - 1;
					InsertVertext(G,newNode,'0' + newNode , NORMAL_NODE);
					AddEdge(G,newNode,p->verIndex,secondSt);
					strcpy(p->st,firstSt);
					p->verIndex = newNode;
				}
				p = G->vertexs[i].firstArc;
			}
		}
	}
}


//生成图中的字母表
void MadeAlphaBeta(Graph* G){
	G->letterNum = 0;
	for(int i = 0 ;G->st[i];i++){
		char ch = G->st[i];
		if(isalpha(ch)){
			for(int j = 0 ; j < G->letterNum;j++)
				if(ch == G->alphaBeta[j]) break;
			if(j < G->letterNum) continue;
			G->alphaBeta[G->letterNum ++] = ch;
		}
	}
	G->alphaBeta[G->letterNum] = '\0';

//	printf("图中字母表为:%s\n",G->alphaBeta);
}


//建立最初的图
void CreateGraph(Graph* G){
	char st[100];
    flushall();
	printf("请输入正则表达式:");
	gets(st);
	Trim(st);
	if(strcmp(st,"exit") == 0) exit(0);
	printf("\n%s\n",st);
	strcpy(G->st,st);
	MadeAlphaBeta(G);

	InsertVertext(G,0,'X',START_NODE);
	InsertVertext(G,1,'1',NORMAL_NODE);
	InsertVertext(G,2,'2',NORMAL_NODE);
	InsertVertext(G,3,'Y',END_NODE);

	//插入第一条边
	Edge* p = (Edge*)malloc(sizeof(Edge));
	strcpy(p->st ,"ε");
	p->nextArc = NULL;
	p->verIndex = 1;  
	G->vertexs[0].firstArc = p;


	//第二条边
	p = (Edge*)malloc(sizeof(Edge));
	strcpy(p->st ,st);
	p->nextArc = NULL;
	p->verIndex = 2;  
	G->vertexs[1].firstArc = p;

	//第三条边
	p = (Edge*)malloc(sizeof(Edge));
	strcpy(p->st ,"ε");
	p->nextArc = NULL;
	p->verIndex = 3;  
	G->vertexs[2].firstArc = p;
	

//	DFS_output(G);
	ToDFA(G);
	printGraph(G);
	BuildSituTable(G);

//	DFS_output(G);

}
#if 1
int main(){
	Graph G;

	while(1){
		Init(&G);
		CreateGraph(&G);
		outputStatesTable(&G);
		while(1){
			printf("请输入一个顶点:");
			int ver;
			scanf("%d",&ver);
			if(ver == -1) break;
			VertexSet result;
			result = Closer(&G,ver);
			printf("%c 的ε 闭包是:\n",LocateVer(&G,ver));
			outputSet(&G,result);
			printf("\n");

			result.reset();
			result.set(ver);
			result = SetThrough(&G,result,'a');
			printf("%c 经过a到达的状态集是:\n",LocateVer(&G,ver));
			outputSet(&G,result);
			printf("\n");

			result.reset();
			result.set(ver);
			result = SetThrough(&G,result,'b');
			printf("%c 经过b到达的状态集是:\n",LocateVer(&G,ver));
			outputSet(&G,result);
			printf("\n\n");

			result = Closer(&G,0);
			result = Move(&G,result,'a');
			printf("%c 经过a到达的状态集是:\n",LocateVer(&G,ver));
			outputSet(&G,result);
			printf("\n\n");

			result = Closer(&G,0);
			result = Move(&G,result,'b');
			printf("%c 经过b到达的状态集是:\n",LocateVer(&G,ver));
			outputSet(&G,result);
			printf("\n\n");
		}
	}

	return 0;
}
#else
int main(){
	char st[100] = "ε";
	printf("strlen(st) = %d\nst = (%d,%d)\n",strlen(st),st[0],st[1]);
	printf("dd = (%d,%d)\n",'b','b');

	while(1){
		char firstSt[100] , secondSt[100];
		char st[100];
		char oper ;
		printf("请输入正则表达式:");
		gets(st);
		if(strcmp(st,"exit")== 0) break;

		Trim(st);
		oper = DivideStr(st,firstSt,secondSt);
		printf("%s\n%c\n%s\n",firstSt,oper,secondSt);
	}
	return 0;
}
#endif