regexptonfa.cpp

编译原理中的表达失转换为NFA

////////////////////////////////
//		20021610517
//		2004-9-30
//		Peng Fude
////////////////////////////////

#include<iostream.h>
#include<stdio.h>
#include<string.h>
#include<conio.h>
#include<stdlib.h>

//定义结点类
template <class Elem> class link
{
	public:
		link* next;
		Elem element;
		int sign;
		link(const Elem& elementValue,link* nextValue = NULL)
		{
			element = elementValue;
			next = nextValue;
			sign = -1;
		}
		link(link* nextValue = NUll)
		{
			next = nextValue;
			sign = -1;
		}
};
//定义堆栈类
template <class Elem> class stack
{
	private:
		link<Elem> *top;
		int size;
	public:
		stack(int sz = DefaultSize)
		{
			top = NULL;
			size = 0;
		}
		~stack(){	clear();	}
		void clear()
		{
			while(top!=NULL)
			{
				link<Elem>* temp = top;
				top = top->next;
				size = 0;
				delete temp;
			}
		}
		//入栈函数
		bool push(const Elem& item)
		{
			top = new link<Elem>(item,top);
			size++;
			return true;
		}
		//出栈函数
		Elem pop()
		{
			Elem item;
			if (size == 0)
				return false;
			item = top->element;
			link<Elem>* temp = top->next;
			delete top;
			top = temp;
			size--;
			return item;
		}
		//获取栈顶元素的值
		Elem GetTop() const
		{
			Elem item;
			if(size == 0)
				return false;
			item = top->element;
			return item;
		}
		//获取堆栈的深度
		int length() const 	{	return size;	}
		//判断栈是否为空
		bool IsEmpty() const 	{	return top == NULL;	}
		//设置标志位
		void SetSign(int s)		{	top->sign = s;	}
		//获取标志位
		int GetSign() const		{	return top->sign;  }
};

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

// 定义邻接表的边表类
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;
		int GetVertexNumber(){return numOfVertices;}
		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);
		void Output(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))
	{
		cerr << "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))
	{
		cerr << "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))
	{
		cerr << "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)
	{
		cerr << "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;
}
// 输出邻接表
void AdjacentTable::Output(void)
{
	Vertex *p = startVertex;
	Edge *ed = new Edge();	
	for (int i=0; i<numOfVertices; i++)
	{
		cout<<"  "<< p->number;
		if (p->number <10)
			cout<<"    │  ";
		else
			cout<<"   │  ";
		ed = p->out;
		if (ed)
		{
			if (ed->weight=='0')
			{
				cout<<ed->number;
				if(ed->number<10)
					cout<<" ";
				cout<<"    │   --     │   --";
			}
			else if (ed->weight=='1')
			{
				cout<<"--    │   ";
				cout<<ed->number;
				if(ed->number<10)
					cout<<" ";
				cout<<"     │   --";
			}
			else if (ed->weight=='e')
			{
				cout<<"--    │   --     │   ";
				while (ed)
				{
					cout<<ed->number<<" ";
					ed = ed->link;
				}
			}
			else
				cout<<"--     │  --     │   --";			
		}
		else 
		{
			cout << "end   │   --     │   --";
		}
		cout<<endl;
		p = p->next;
	}
}
//实现有正则表达式转化成NFA的类
class RegularExpToNFA
{
public:
	RegularExpToNFA();
	void GetExpression();
//	void Compute();
	void Run();
	void ExpToPostFix();
//	void FormNFA(char op);
	int Precedence(char symbol);
    int ThompsonMethod();
	void OutputNFA(int end);
private:
	char exp[50];
	char post[50];
	int state[50];
	int endState[20];
	int startState;
	int StateCount;
	int EdgeCount;
	struct move
	{
		int moveFrom;
		int moveTo;
		char moveSymbol;
	};
	move moveEdge[40];
	stack<int> *ss;
	stack<char> *st;
	AdjacentTable *table;
};
//类的成员函数的实现
RegularExpToNFA::RegularExpToNFA()
{
	for (int i=0;i<50;i++)
	{
		state[i] = i;
	}
	startState = 0;
	StateCount = 0;
	EdgeCount = 0;
	table = new AdjacentTable();
	stack<char> *st = new stack<char>(0);
	stack<int> *ss = new stack<int>(0);