#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <conio.h>
#include <string>

using namespace std; 


/////////////////////////////////////////////////

#define NULL 0
#define LStack LinkedStack

/////////////////////////////////////////////////

// 鏈式棧類的前視定義
template <class T>
class LinkedStack;

/////////////////////////////////////////////////

// 定義鏈式棧結點類
template <class T>
class StackNode
{
	friend class LinkedStack<T>;
	private:
		T data;
        StackNode<T> *next;
		StackNode(T item = 0, StackNode<T> *p = NULL)
		{
			data = item;
			next = p;
		}
};

/////////////////////////////////////////////////

// 定義鏈式棧類
template <class T>
class LinkedStack
{
	private:
		StackNode<T> *top;
	public:
		LinkedStack();
		~LinkedStack();
		bool IsEmpty(void) const;
		int Length(void) const;
		void Push(const T &item);
		T Pop(void);
		T GetTop(void);
		void Clear(void);
};
// 構造函數
template <class T>
LinkedStack<T>::LinkedStack()
{
	top = NULL;
}
// 析構函數
template <class T>
LinkedStack<T>::~LinkedStack()
{
	Clear();
}
// 判斷棧是否為空
template <class T>
bool LinkedStack<T>::IsEmpty(void) const
{
	return (! top);
}
// 獲取隊列的長度
template <class T>
int LinkedStack<T>::Length(void) const
{
	StackNode<T> *temp = new StackNode<T>();
	temp = top;
	int length = 0;
	while (temp)
	{
		temp = temp->next;
		length++;
	}
	return length;
}
// 壓入數據(入棧)
template <class T>
void LinkedStack<T>::Push(const T &item)
{
	top = new StackNode<T>(item, top);
}
// 抽出數據(出棧)
template <class T>
T LinkedStack<T>::Pop(void)
{
	if (! IsEmpty())
	{
	    StackNode<T> *temp = top;
		top = top->next;
		T value = temp->data;
		delete temp;
		return value;
	}
	else
	{
		cout << "Stack Already Empty!" << endl;
		getch();
		exit(1);
	}
}
// 獲取棧頭數據
template <class T>
T LinkedStack<T>::GetTop(void)
{
	if (! IsEmpty())
	{
		return top->data;
	}
	else
	{
		cout << "Stack Already Empty!" << endl;
		getch();
		exit(1);
	}
}
// 設置棧為空棧
template <class T>
void LinkedStack<T>::Clear(void)
{
	StackNode<T> *temp = new StackNode<T>();
	while (top)
	{
		temp = top;
		top = top->next;
		delete temp;
	}
}

/////////////////////////////////////////////////

// 定義鄰接表的邊表類
class Edge
{
	public:
		int number;
		int position;
		char weight;
		Edge *link;
		Edge();
		Edge(int num, int pos, char ch);
};
Edge::Edge()
{
	number = -1;
	position = -1;
	link = NULL;
}
Edge::Edge(int num, int pos, char ch)
{
	number = num;
	position = pos;
	weight = ch;
    link = NULL;
}

/////////////////////////////////////////////////

// 定義鄰接表的頂點類
class Vertex
{
	public:
		int number;
		Vertex *next;
		Edge *out;
		Vertex();
		Vertex(int num);
};
Vertex::Vertex()
{
	number = -1;
	next = NULL;
	out = NULL;
}
Vertex::Vertex(int num)
{
	number = num;
	next = NULL;
	out = NULL;
}

/////////////////////////////////////////////////

// 用鄰接表定義的圖類
class AdjacentTable
{
	private:
		Vertex *startVertex;
		int numOfVertices;
		int numOfEdges;
	public:
		AdjacentTable();
		~AdjacentTable();
		int GetValueByPos(int pos) const;
		int GetPosByValue(int value) const;
		char GetWeightByPos(int v1, int v2) const;
		char GetWeightByValue(int value1, int value2) const;
		void SetValue(int value, int pos);
		void InsertVertex(int value);
		void InsertEdgeByPos(int v1, int v2, char weight);
		void InsertEdgeByValue(int value1, int value2, char weight);
		void RemoveAllEdges(void);
		void Clear(void);
		int* Closure(int *T);
		int* Move(int *T, char ch);
		void OutputNFA(void);
};
// 構造函數
AdjacentTable::AdjacentTable()
{
	numOfVertices = 1;
	numOfEdges = 0;
	startVertex = new Vertex();
}
// 析構函數
AdjacentTable::~AdjacentTable()
{
	Vertex *p;
	Edge *q;
	p = startVertex;
	for (int i=0; i<numOfVertices; i++)
	{
		q = p->out;
		while (q)
		{
			p->out = q->link;
			delete q;
			q = p->out;
		}
		p = p->next;
	}
}
// 按頂點位置獲取頂點的值
int AdjacentTable::GetValueByPos(int pos) const
{
	if ((pos >= 0) && (pos < numOfVertices))
	{
    	Vertex *p = startVertex;
    	for (int i=0; i<pos; i++)
		{
	    	p = p->next;
		}
		return p->number;
	}
	return -1;
}
// 按頂點值獲取頂點的位置
int AdjacentTable::GetPosByValue(int value) const
{
	Vertex *p = startVertex;
    for (int i=0; i<numOfVertices; i++)
	{
		if (p->number == value)
		{
			return i;
		}
	    p = p->next;
	}
	return -1;
}
// 按頂點位置獲取邊的權
char AdjacentTable::GetWeightByPos(int v1, int v2) const
{
	if ((v1 >= 0) && (v2 >= 0) && (v1 < numOfVertices) && (v2 < numOfVertices))
	{
		Vertex *p = startVertex;
		for (int i=0; i<v1; i++)
		{
	    	p = p->next;
		}
		Edge *q = p->out;
		while (q)
		{
			if (q->position == v2)
			{
				return (q->weight);
			}
			else
			{
				q = q->link;
			}
		}
	}
	return '#';
}
// 按頂點值獲取邊的權
char AdjacentTable::GetWeightByValue(int value1, int value2) const
{
	return GetWeightByPos(GetPosByValue(value1), GetPosByValue(value2));
}
// 設置頂點的值
void AdjacentTable::SetValue(int value, int pos)
{
	if ((pos < 0) || (pos >= numOfVertices))
	{
		cout << "Illegal setting: The vertex doesn't exist!" << endl;
		getch();
		exit(1);
	}
	Vertex *p = startVertex;
	for (int i=0; i<pos; i++)
	{
		p = p->next;
	}
	p->number = value;
}
// 插入頂點
void AdjacentTable::InsertVertex(int value)
{
	int pos = GetPosByValue(value);
	if ((pos >= 0) && (pos < numOfVertices))
	{
		cout << "Illegal insertion: The same vertex has existed!" << endl;
		getch();
		exit(1);
	}
	Vertex *p = startVertex;
	while (p->next)
	{
		p = p->next;
	}
	Vertex *newVertex = new Vertex(value);
	p->next = newVertex;
	numOfVertices++;
}
// 按頂點位置插入邊表
void AdjacentTable::InsertEdgeByPos(int v1, int v2, char weight)
{
	if ((v1 < 0) || (v1 >= numOfVertices) || (v2 < 0) || (v2 >= numOfVertices))
	{
		cout << "Illegal insertion: The vertex doesn't exist!" << endl;
		getch();
		exit(1);
	}
	Vertex *p = startVertex;
	for (int i=0; i<v1; i++)
	{
		p = p->next;
	}
	Edge *q = p->out;
	Edge *newEdge = new Edge(GetValueByPos(v2), v2, weight);
	if (! q)
	{
		p->out = newEdge;
		numOfEdges++;
		return;
	}
	while ((q->position != v2) && (q->link))
	{
		q = q->link;
	}
	if (q->position == v2)
	{
		cout << "Illegal insertion: The Edge has existed!" << endl;
		getch();
		exit(1);
	}
	if (! q->link)
	{
		q->link = newEdge;
		numOfEdges++;
	}
}
// 按頂點值插入邊表
void AdjacentTable::InsertEdgeByValue(int value1, int value2, char weight)
{
	int v1 = GetPosByValue(value1), v2 = GetPosByValue(value2);
	InsertEdgeByPos(v1, v2, weight);
}
// 刪除所有的邊表
void AdjacentTable::RemoveAllEdges(void)
{
	Vertex *p = startVertex;
	for (int i=0; i<numOfVertices; i++)
	{
		Edge *q = p->out;
		while (q)
		{
			p->out = q->link;
			delete q;
			q = p->out;
		}
		p = p->next;
	}
	numOfEdges = 0;
}
// 清空鄰接表
void AdjacentTable::Clear(void)
{
	RemoveAllEdges();
	Vertex *p = startVertex->next;
	while (p)
	{
		startVertex->next = p->next;
		delete p;
		p = startVertex->next;
	}
	numOfVertices = 1;
}
// 閉包函數
int* AdjacentTable::Closure(int *T)
{
	int i = 0, j, k = 0, l, len = 0;
	int *temp = new int[128];
	Vertex *p;
	Edge *q;
	while (T[len] != -1)
	{
		len++;
	}
	while (T[i] != -1)
	{
    	for (l=0; l<k; l++)
		{
			if (T[i] == temp[l])
			{
		    	break;
			}
		}
	    if (l == k)
		{
			temp[k] = T[i];
			k++;
		}
		int pos = GetPosByValue(T[i]);
		p = startVertex;
		for (j=0; j<pos; j++)
		{
			p = p->next;
		}
		q = p->out;
		while (q)
		{
			if (q->weight == '~')
			{
				for (l=0; l<k; l++)
				{
			    	if (q->number == temp[l])
					{
			    		break;
					}
				}
		    	if (l == k)
				{
			    	temp[k] = q->number;
		    		k++;
					T[len++] = q->number;
					T[len] = -1;
				}
			}
			q = q->link;
		}
		i++;
	}
	temp[k] = -1;
	return temp;
}
// 移動函數
int* AdjacentTable::Move(int *T, char ch)
{
	int i = 0, j, k = 0, l;
	int *temp = new int[128];
	Vertex *p;
	Edge *q;
	while (T[i] != -1)
	{
		int pos = GetPosByValue(T[i]);
		p = startVertex;
		for (j=0; j<pos; j++)
		{
			p = p->next;
		}
		q = p->out;
		while (q)
		{
			if (q->weight == ch)
			{
				for (l=0; l<k; l++)
				{
			    	if (q->number == temp[l])
					{
			    		break;
					}
				}
		    	if (l == k)
				{
			    	temp[k] = q->number;
		    		k++;
				}
			}
			q = q->link;
		}
		i++;
	}
	temp[k] = -1;
	return temp;
}
// 輸出鄰接表
void AdjacentTable::OutputNFA(void)
{
	Vertex *p = startVertex;
	Edge *q = new Edge();
	cout << "狀態   邊(權值)" << endl;
	for (int i=0; i<numOfVertices; i++)
	{
		cout << p->number;
		if (p->number < 10)	 cout << "      ";
		else if (p->number < 100)  cout << "     ";
		else if (p->number < 1000)	cout << "    ";
		else  cout << "   ";
		q = p->out;
		if (q)
		{
			while (q)
			{
				cout << q->number << "(" << q->weight << ") ";
				q = q->link;
			}
		}
		else 
		{
			cout << "END";
		}
		cout << endl;
		p = p->next;
	}
}

/////////////////////////////////////////////////

// 定義轉移矩陣類
class TransitionTable
{
public:
	TransitionTable(int rowNum, int colNum);
	~TransitionTable();
	void SetValue(int i, int j, int value);
	int GetValue(int i, int j);
	int Transit(int current, char input, char *edge);
	void Clear(void);
private:
	int **matrix;
	int rowNumber;
	int colNumber;
};
// 構造函數
TransitionTable::TransitionTable(int rowNum, int colNum)
{
	rowNumber = rowNum;
	colNumber = colNum;
	matrix = (int**)(new int*[rowNumber]);
	for (int i=0; i<rowNumber; i++)
	{
		matrix[i] = new int[colNumber];
	}
}
// 析構函數
TransitionTable::~TransitionTable()
{
	Clear();
}
// 設置元素的值
void TransitionTable::SetValue(int i, int j, int value)
{
	matrix[i][j] = value;
}
// 獲取元素的值
int TransitionTable::GetValue(int i, int j)
{
	return matrix[i][j];
}
// 狀態轉移函數
int TransitionTable::Transit(int current, char input, char *edge)
{
	for (int i=0; edge[i]!= '\0'; i++)
	{
		if (input == edge[i])