nfa_dfa.txt

求正规表达式到NFA（不确定的有限自动机）

//求正规式到NFA，NFA到DFA及DFA的最小化
#include <iostream>
#include <string>
#include <stdlib.h>
#include <search.h>
#include <stdio.h>
using namespace std;

typedef struct node
{
	int status;							//节点的序号
	char input;							//节点所接受的输入字符
	struct node *next,*brother,*right;	//next指向当前节点经输入字符后到达的下一节点
}NODE;									//brother指向当前节点的分支
										//right指向当前节点的闭包
typedef struct node1
{
	int flag;							//输入或序号
	int status;							//节点的序号
	struct node1 *link;
}NODE1;
typedef struct node2
{
	int index;							//节点的序号
	char *str;							//状态节点集合
	struct node2 *link;
}NODE2;
typedef struct
{
	NODE *base;							//栈底指针
	NODE *top;							//栈顶指针
}STACK;
void print(NODE *,NODE1 *);				//打印NFA
void print1(NODE1 *);					//打印DFA
NODE *NFA_build(char *,int &,NODE **);	//NFA构造主程序
void push(NODE *);						//压栈			
void rpar(char *,int &,NODE **,NODE **);//对右括弧的操作
void function_wrap(NODE **);			//对闭包的操作
void create_node(NODE **,char);			//增加一个新节点
int compare(char,char);					//strchr中的比较函数
int NFA2DFA(NODE1*,NODE1*,char *);		//NFA到DFA的转换函数之主函数
void simple(int,char *,NODE1 *);		//对DFA的最小化
int check_for_repeat(char,char *);		//检查是否有重复
int check_for_end(char *,NODE1);		//检查是否结束
int check_for_equ(int,int,NODE2 *);		//检查是否相等
void func1(int &,int &,char *,NODE1 *);	//求CLOSURE(I)的函数
void func2(int &,int,char,NODE1 *,NODE1 *,NODE2 *);//NFA到DFA的转换函数之实现函数
void func3(char *,char *);				//求正规式中输入字符串
void func4(char *);						//去除重复字符
void func5(NODE1 *);					//去除重复节点
void print2(int,NODE1 *);				//打印最小化后的DFA
int index=0;
FILE *fp1;	
STACK *s;

void main()
{
	fp1=fopen("f:/nfa.txt","w");
	int i=0;							
	char str[80];						
	cout<<"请输入正规式："<<endl;
	cin>>str;
	str[strlen(str)]='\0';
	char *str_out=new char[strlen(str)];
	strset(str_out,'\0');
	func3(str,str_out);
	NODE *head=new NODE;				
	head->status=index++;
	head->input='#';					
	head->brother=head->right=NULL;		
	NODE *tail=new NODE;				
	tail->status=index++;
	tail->input='#';
	tail->next=tail->brother=tail->right=NULL;
	head->next=tail;
	s=new STACK;						
	s->base=new NODE[50];
	s->top=s->base;
	push(head);
	NFA_build(str,i,&head);
	s->top--;
	index--;
	NODE1 arr_NFA[50];
	for(int j=0;j<=index;j++) arr_NFA[j].link=NULL;
	print(head,arr_NFA);
	fclose(fp1);
	fp1=fopen("f:/fa.txt","w");
	arr_NFA[1].status=1;
	NODE1 arr_DFA[50];
	index=NFA2DFA(arr_NFA,arr_DFA,str_out);
	cout<<endl;
	print1(arr_DFA);
	fclose(fp1);
	fp1=fopen("f:/simple.txt","w");
	simple(index,str_out,arr_DFA);
	fclose(fp1);
}

void push(NODE *p)
{
	(*s->top).next=p;
	s->top++;
}

NODE *NFA_build(char str[],int &i,NODE **head)
{
	NODE *p=(*head);
 	while(str[i]!='\0')
	{
		if(str[i]=='(')
		{
			NODE *current_head=new NODE;
			current_head->status=index++;
			current_head->input='#';
			current_head->next=current_head->brother=current_head->right=NULL;
			push(p);
			NODE *current_p=NFA_build(str,++i,&current_head);
			s->top--;
			current_p->next=p->next;
			p->next=current_head;
			p=current_p;
			if(str[i+1]==')') i+=1;
			if(str[i+1]=='*')
			{
				i+=1;
				if(str[i+1]!='\0')
				{	
					p=p->next;
					current_p=new NODE;
					current_p->status=p->status;
					p->status=index++;
					current_p->input='#';
					current_p->next=current_p->brother=current_p->right=NULL;	
					p->next=current_p;
				}
			}
			else
			{
				if(str[i+1]!='\0')
				{
					p=p->next;
					current_p=new NODE;
					current_p->status=p->status;
					p->status=index++;
					current_p->input='#';
					current_p->next=current_p->brother=current_p->right=NULL;
					p->next=current_p;
				}
			}
			i++;
		}
		else if(str[i]==')')
		{
			rpar(str,i,head,&p);
			return p;
		}
		else if(str[i]=='*')
		{
			function_wrap(&p);
			i++;
		}
		else if(str[i]=='|')
		{			
			NODE *pos=(s->top-1)->next;
			NODE *current_head=new NODE;
			current_head->status=(*head)->status;
			current_head->input='#';
			current_head->next=current_head->brother=current_head->right=NULL;
			NODE *current_p=NFA_build(str,++i,&current_head);
			while(pos->next!=NULL)
				pos=pos->next;
			if((str[i]=='\0')||(str[i+2]!='*'))
				current_p->next=pos;
			(*head)->brother=current_head;
		}
		else
		{
			create_node(&p,str[i]);
			i++;
		}
	}
	return p;
}

void rpar(char *str,int &i,NODE **head,NODE **p)
{
	if(str[i+1]=='*')
	{	
		NODE *new_head;
		new_head=new NODE;
		new_head->input='^';
		new_head->status=(*head)->status;
		new_head->right=(*head);
		new_head->next=new_head->brother=NULL;
		(*p)->next=new_head;
		(*p)=(*head)=new_head;
		new_head=(s->top-1)->next;
		if(new_head->status!='#')
		{
			new_head=new NODE;
			new_head->status=index++;
			new_head->right=new_head->brother=NULL;
			new_head->next=(*head);			
			(*head)=new_head;
		}
		new_head->input='^';
	}
}
			
void function_wrap(NODE **p)
{
	NODE *head=new NODE;
	head->input=(*p)->input;
	(*p)->input='^';
	create_node(p,(*p)->input);
	head->status=(*p)->status;
	(*p)->right=head;
	head->next=(*p);
	head->brother=head->right=NULL;
}

void create_node(NODE **p,char ch)
{
	if((*p)->input!='#')
	{
		NODE *new_node=new NODE;
		new_node->status=index++;
		new_node->input=ch;
		new_node->next=(*p)->next;
		(*p)->next=new_node;
		new_node->brother=new_node->right=NULL;
		(*p)=new_node;
	}
	else
		(*p)->input=ch;
}