// REManage.h: interface for the REManage class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_REMANAGE_H__5B8C1C6A_7551_4DF0_B01E_1D40C5481F88__INCLUDED_)
#define AFX_REMANAGE_H__5B8C1C6A_7551_4DF0_B01E_1D40C5481F88__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <fstream>
using namespace std;

const int OP=0;		//操作符
const int OP_D=1;	//操作數(shù)

typedef class _EDGE
{
public:
	int start;
	char input;
	int end;
	friend bool operator == (const _EDGE& a,const _EDGE& b)
	{
		return (a.start==b.start)&&(a.input==b.input)&&(a.end==b.end);
	}
}EDGE;		//自動(dòng)機(jī)的邊

typedef struct _NFA
{
	int start;
	int end;
}NFA;		//

class REManage  
{
public:
	REManage();
	REManage(string re);
	virtual ~REManage();
	
	//處理新的輸入
	void Process();

	//測(cè)試輸入字符串，判斷能否由生成的DFA識(shí)別
	bool TestString(string str);
	
	//設(shè)置正規(guī)式
	void setRE(string re);

	//設(shè)置NFA
	void setNFA(vector<EDGE> edge,vector<int> start,vector<int> end);

	//設(shè)置DFA
	void setDFA(vector<EDGE> edge,int start,vector<int> end);

	
private:
	//清空所有容器變量
	void clear();

	//輸出處理結(jié)果
	void OutputResult();

	/********************分析RE函數(shù)**********************/
	/*正規(guī)式到NFA的轉(zhuǎn)換*/
	void ProcessREToNFA();

	int state;		//計(jì)數(shù)狀態(tài)
	int type(char re);		//判斷輸入字符的類型: OP,OP_D
	/********************End*****************************/

	/********************RE到NFA轉(zhuǎn)換有關(guān)函數(shù)*************************/
	/*對(duì)單個(gè)輸入字符構(gòu)造相應(yīng)的NFA*/
	void MakeNFA_S(char input,NFA* n,vector<EDGE>& edge);

	/*構(gòu)造某個(gè)NFA的閉包*/
	void MakeNFA_CL(NFA* result,NFA* op,vector<EDGE>& edge);

	/*構(gòu)造兩個(gè)NFA的或運(yùn)算*/
	void MakeNFA_OR(NFA* result,NFA* left,NFA* right,vector<EDGE>& edge);

	/*構(gòu)造兩個(gè)NFA的與運(yùn)算*/
	void MakeNFA_AND(NFA* result,NFA* left,NFA* right,vector<EDGE>& edge);
	/******************************End*******************************/

	/********************************NFA到DFA轉(zhuǎn)換有關(guān)函數(shù)*************************/
	/*NFA到DFA的轉(zhuǎn)換*/
	void ProcessNFAToDFA();

	/*找到集合input的@閉包，結(jié)果保存在集合output中*/
	void Find_NULL_Closure(vector<int> input, vector<int>&output,vector<EDGE> edge);

	/*計(jì)算集合input在輸入為in時(shí)的所能達(dá)到的狀態(tài)集合result*/
	void Move(vector<int> input,char in,vector<int>&result,vector<EDGE> edge);
	/***************************************End***********************************/

	/********************************DFA最小化有關(guān)函數(shù)*************************/
	/*最小化DFA*/
	void MinimizeDFA();

	/*在DFA中當(dāng)初態(tài)為start，輸入為input時(shí)，返回終態(tài)*/
	int MovdDFA(int start,char input);

	/*找到輸入終態(tài)end所在的集合*/
	int FindGather(int end,vector<vector<int> > gather);

	/*消除DFA中的無(wú)用狀態(tài)*/
	void RemoveFutility();

	/*合并DFA中的等價(jià)狀態(tài)*/
	void CombineEquality();
	/*************************************End**********************************/
	
	ofstream out;
	
	//正規(guī)式對(duì)應(yīng)的變量
	string re;				//輸入的正規(guī)式
	vector<char> REInput;		//正規(guī)式的輸入符
	bool isREUpdate;		//正規(guī)式是否已更新
	
	//NFA對(duì)應(yīng)的變量
	vector<char> NFAInput;	//NFA的輸入符
	vector<int>	startNFA;	//NFA的起始狀態(tài)集
	vector<int>	endNFA;		//NFA的終態(tài)集
	vector<EDGE> NFA_EDGE;		//構(gòu)造出的NFA的所有邊的集合
	bool isNFAUpdate;		//NFA是否已更新
	
	//DFA對(duì)應(yīng)的變量
	vector<char> DFAInput;	//DFA的輸入符
	int startDFA;			//DFA的起始狀態(tài)
	vector<int> endDFA;		//DFA的終態(tài)集
	vector<int> nonEndDFA;	//DFA的非終態(tài)集	
	vector<EDGE> DFA_EDGE;	//由NFA所構(gòu)造成的DFA的邊的集合
	vector<vector<int> > DFAStateGather;		//DFA中各個(gè)狀態(tài)對(duì)應(yīng)于NFA中的狀態(tài)集
	bool isDFAUpdate;		//DFA是否已更新

	//DFA最小化后對(duì)應(yīng)的變量
	vector<char> miniDFAInput;	//最小化后DFA的輸入符
	int miniStartDFA;			//最小化后DFA的起始狀態(tài)
	vector<int> miniEndDFA;		//最小化后DFA的終態(tài)集
	vector<int> miniNonEndDFA;	//最小化后DFA的非終態(tài)集
	vector<EDGE> MiniDFA_EDGE;	//最小化后DFA中的邊的集合
	vector<vector<int> > miniStateGather;	//最小化后DFA中各個(gè)狀態(tài)對(duì)應(yīng)于初始DFA中的狀態(tài)集
};

#endif // !defined(AFX_REMANAGE_H__5B8C1C6A_7551_4DF0_B01E_1D40C5481F88__INCLUDED_)