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

//邊結(jié)點(diǎn)
typedef struct Node{
	int verIndex;
	char st[100];
	struct Node* nextArc;
}Edge;

//狀態(tài)節(jié)點(diǎn)類(lèi)型
#define START_NODE 1
#define END_NODE 2
#define NORMAL_NODE 3

//狀態(tài)結(jié)點(diǎn)
typedef struct{
	char ver;
	int type;
	Edge* firstArc;
}Vertex;

//最大的頂點(diǎn)數(shù)
#define MAX_VERTEX_NUM 100

//最大的字母數(shù)
#define MAX_LETTER_NUM 400

#define MAX_TALBE_SIZE 100

typedef bitset<MAX_VERTEX_NUM> VertexSet;

//圖類(lèi)型
typedef struct{
	Vertex vertexs[MAX_VERTEX_NUM];
	int vertexNum;

	char alphaBeta[MAX_LETTER_NUM];
	int letterNum;
	char st[400]; //存放輸入的正則表達(dá)式
	
	//產(chǎn)生狀態(tài)集合表
	VertexSet table[MAX_TALBE_SIZE];
	int row;  //表的行數(shù)
	char charTable[MAX_TALBE_SIZE];
	bool isEnd[MAX_TALBE_SIZE]; //記錄表中每行首結(jié)點(diǎn)是否為終結(jié)點(diǎn)
}Graph;

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

}

//返回圖中第i個(gè)結(jié)點(diǎn)字符
char LocateVer(Graph* G,int i){
	if(i <0 || i>=G->vertexNum) return '\0';
	return G->vertexs[i].ver;
}

//圖搜索時(shí)的訪問(wèn)標(biāo)志
#define VISITED 1
#define NONVISITED 0
//訪問(wèn)標(biāo)志數(shù)組
int visited[MAX_VERTEX_NUM];

//深度優(yōu)先輸出
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;
	}
}

//深度優(yōu)先搜索
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);
}

//按頂點(diǎn)順序打印圖中每一條邊
void printGraph(Graph* G){
	printf("\n\n1. 轉(zhuǎn)換成NFA如下 \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處，插入一個(gè)名稱(chēng)為c,類(lèi)型為type的頂點(diǎn)
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("****** 圖中節(jié)點(diǎn)數(shù)已達(dá)到最大值，無(wú)法插入! *********\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;
}

//輸出狀態(tài)集合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("}");
}

//用深度優(yōu)先搜索返回 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;
}

//返回頂點(diǎn)ver的ε閉包
VertexSet Closer(Graph* G,int ver){
	for(int i = 0 ; i < G->vertexNum;i++)
		visited[i] = NONVISITED;
    return CloserDFS(G,ver);	 
}

//返回圖G中頂點(diǎn)集合s通過(guò)一次ch弧所能到達(dá)的頂點(diǎn)集
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關(guān)于字符ch的Ich閉包
VertexSet Move(Graph* G,VertexSet& b,char ch){
	VertexSet  result;

	//存放G中每個(gè)狀態(tài)的?閉包
	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;
}

//輸出圖G的狀態(tài)表
void outputStatesTable(Graph* G){
	int col = G->letterNum + 1;
	for(int i = 0; i < G->row ; i++){
		for(int j = 0 ; j < col;j++){
			int index = i * col + j;
			outputSet(G,G->table[index]);
			printf("\t");
		}
		printf("\n");
	}
}

//建圖的DFA狀態(tài)表
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++;

		//判斷是否要結(jié)束
		int next = k;
		bool find = false;
		for(int j = k + 1; j < row*col && !find; j++){
			if(G->table[j].count() == 0) continue;
			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++;
}

//去掉字符串最外層多余的括號(hào)
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);
	}
}

//判斷頂點(diǎn)下標(biāo)是否合法
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) 頂點(diǎn)下標(biāo)越界! **********\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) 頂點(diǎn)下標(biāo)越界! **********\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("**** 沒(méi)有找到要?jiǎng)h除的邊! *****\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] == '('){				//n用來(lái)表示括號(hào)是否匹配
		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 非法開(kāi)頭字符 %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 '*';