dn转换.cpp

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

			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';
}


//输出图G的字符型的状态转换矩阵
void outputCharTable(Graph* G){
	int col = G->letterNum + 1;

	printf("  I\t");
	for(int j = 0 ; j < col - 1;j++){
		printf("I%c\t",G->alphaBeta[j]);
	}
	printf("\n");

	for(int i = 0; i < G->row ; i++){
		if(G->isEnd[i]) printf("%c*\t",G->charTable[i*col]);
		else  printf("%c\t",G->charTable[i*col]);
		for(int j = 1 ; j < col;j++){
			int index = i * col + j;
			printf("%c\t",G->charTable[index]);
		}
		printf("\n");
	}
}

typedef vector<char> VecLetterSet;

//输出字符集合
void outputCharSet(VecLetterSet v){
	printf("{");
	for(int i = 0 ; i < v.size();i++)
		printf("%c ",v[i]);
	printf("}");
}


//获得点c的下标
int GetIndex(char c){
	if(c == 'X') return 0;
	return c - 'A' + 1;
}

//获得图G中结点C通过letterIndex到达的结点
char GetLinkedSitu(Graph* G,char c,int letterIndex){
	int index = GetIndex(c);
	int col = G->letterNum + 1;
	return G->charTable[col * index + letterIndex + 1];
}

//判断c是否属于集合v
bool IsVerMember(char c , const VecLetterSet& v){
	for(int i = 0 ; i < v.size();i++)
		if(v[i] == c) return true;
	return false;
}

//用深度优先划分一个集合
void DivideSet(Graph* G,vector<VecLetterSet>& v,int setIndex,int letterIndex){

	//通过每个字母弧的划分完成,则返回
	if(letterIndex == G->letterNum ) return;

	int k = v.size();
	for(int i = 0 ; i < v[setIndex].size(); i++){
		int n = v.size();
		for(int j = k ; j < n ; j++){
			char c1 = GetLinkedSitu(G,v[j][0],letterIndex);
			char c2 = GetLinkedSitu(G,v[setIndex][i],letterIndex);
			for(int l = 0 ; l < n;l++)
				if(IsVerMember(c1,v[l]) && IsVerMember(c2,v[l]))
					break;
			if(l < n){
				v[j].push_back(v[setIndex][i]);
				break;
			}
		}
		if(j==n){
			VecLetterSet tmp;
			tmp.push_back(v[setIndex][i]);
			v.push_back(tmp);
		}
	}
	
	//从总的集合容器中删除处理过的集合
	vector<VecLetterSet>::iterator iter = v.begin();
	for(i = 0; i < setIndex ; i++)
		iter++;
	v.erase(iter);

	//本层的其他集合进行按下一个字母拆分
	for(i = k-1; i < v.size(); i++)
		DivideSet(G,v,k-1,letterIndex+1);
}

//集合容器排序
void MySort(vector<VecLetterSet>& v){
	for(int pass = 1 ; pass < v.size();pass++)
		for(int i = 0 ; i < v.size() - pass; ++i)
			if(v[i+1][0] < v[i][0]) v[i].swap(v[i+1]);
	
	VecLetterSet tmp = v[v.size() - 1];

	v.insert(v.begin(),tmp);
	v.pop_back();
}


//对图中集合划分为一个个等价集合
vector<VecLetterSet> GetDividedSets(Graph* G){
	vector<VecLetterSet> result;
	VecLetterSet startSet;
	VecLetterSet endSet;

	int endIndex = G->vertexNum - 1;
	int col = G->letterNum + 1;

	//首先将所有状态划分为 终态与非终态
	for(int i = 0 ; i < G->row;i++)
		if(G->table[i*col].test(endIndex))
			endSet.push_back(G->charTable[i*col]);
		else
			startSet.push_back(G->charTable[i*col]);

	result.push_back(startSet);
	result.push_back(endSet);		


	//循环划分状态集合
	while(1){
		int n = result.size();
		for(int i = 0 ; i < n ;i++)
			DivideSet(G,result,0,0);
		//子集个数不再增加则退出
		if(result.size() == n) break;
	}

	MySort(result);
	return result;
}

//将所有字符替换为其所在的集合中第一个元素
void Substitute(Graph* G,char charTable[],const vector<VecLetterSet>& v){
	char trans[MAX_TALBE_SIZE];
	int col = G->letterNum + 1;
	char endChar = charTable[(G->row - 1) * col];

	//得到映射数组
	for(int i = 0 ; i < v.size();i++){
		G->isEnd[i] = false;
		for(int j = 0 ; j < v[i].size();j++){
			trans[GetIndex(v[i][j])] = v[i][0];
			if(v[i][j] == endChar) G->isEnd[i] = true;
		}
	}

	for(i = 0 ; i < G->row;i++){
		for(int j = 1; j < col;j++){
			char ch = charTable[i*col+j];
			if(ch == '\0') continue;
			charTable[i*col+j] = trans[GetIndex(ch)];
		}
	}

}

//按照划分的等价状态集合生成图的状态转换矩阵
void Transform(Graph* G,const vector<VecLetterSet>& v){
	char charTable[MAX_TALBE_SIZE];
	int col = G->letterNum +1;
	int n = col * G->row;

	//备份一下原来的状态转换矩阵
	for(int i = 0 ; i < n;i++)
		charTable[i] = G->charTable[i];
	
	Substitute(G,charTable,v);
	
	//转换为新的状态转换矩阵
	G->row = v.size();
	for(i = 0 ; i < v.size();i++){
		G->charTable[col*i] = v[i][0];
		int k = GetIndex(v[i][0]);
		for(int j = 1 ; j < col ; j++)
			G->charTable[col*i + j] = charTable[col*k + j];
	}
}


//化简图G,使之成为最简的DFA形式
void SimplestDFA(Graph* G){
	vector<VecLetterSet> v;
	v = GetDividedSets(G);

	//输出状态集合
	printf("\n******* 其中可合并的状态集为 *******\n");
	for(int i = 0 ; i < v.size();i++){
		outputCharSet(v[i]);
		printf("--> %c\n",v[i][0]);
	}

	Transform(G,v);
	printf("*********** 化简后的DFA状态转换矩阵 **********\n");
	outputCharTable(G);
}


//建立图的DFA的状态转换矩阵
void BuildCharTable(Graph* G){
	int col = G->letterNum + 1;

	//给各个状态结点赋值
	G->charTable[0] = 'X';	
	for(int i = 1 ; i < G->row;i++)
		G->charTable[i*col] = 'A' + i -1;

	int endIndex = G->vertexNum - 1;

	for(i = 0 ; i < G->row;i++){
		for(int j = 1; j < col;j++){
			if(G->table[i*col + j].count() == 0) G->charTable[i*col+j] = '\0';
			else{
				for(int k = 0; k < G->row; k++)
					if(G->table[i*col+j] == G->table[k*col])
						G->charTable[i*col+j] = G->charTable[k*col];
			}
		}
		
		if(G->table[i*col].test(endIndex))
			G->isEnd[i] = true;
		else
			G->isEnd[i] = false;
	}
}


//建立最初的图
void CreateGraph(Graph* G){
	char st[100];
	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,'Y',END_NODE);

	AddEdge(G,0,1,st);

	ToDFA(G);
	printGraph(G);
	BuildSituTable(G);
	BuildCharTable(G);

	printf("*********** 未化简的DFA状态转换矩阵 **********\n");
	outputCharTable(G);
	SimplestDFA(G);

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

	while(1){
		Init(&G);
		CreateGraph(&G);
	}

	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