文档介绍：正则表达式转NFA
    最近一直在忙着写大作业,考试复****复****算法的时候写了一些随笔,现在忙起来都落下了博客,这里有一个VC++写的大作业,主要是正则表达式转NFA并显示。内容如下。
数据结构描述
介绍一下NFA在表示的结构设计,由于NFA本身是一种有向图,所以这里的存储结构设计和邻接表相似,图中的每个节点后面是一些与其连接的节点的值,。
 

a)         Graph由若干个GraphLine组成,其中start和end标识了NFA的初始状态和终止状态的下标;
b)         GraphLine的由一个节点和以该节点为起点所指向的节点组成,而所指向的节点利用EdgeLink表示,其中有指向边上的转移字符和指向的节点组成;
c)         GraphNode表示图的基本组成节点,其中节点有唯一的ID和位置;
正则表达式转换NFA算法
基础的正则表达式,
 

 

    符号栈,即运算的符号,其存储的为wchar_t类型,为连接,左括号,选择3种运算符。
    NFA栈,即保存的NFA,这里因为整个计算过程都是更新一个Graph结构,所以这里的NFA栈保留的其实是当前NFA的开始和结束信息,即start和end。
具体的主要算法执行流程:
    遍历输入的正则表达式,这里正则表达式的保存在CString变量中,可以通过下标访问
    首先初始化一张保存NFA的Graph结构,算法过程中的节点的数量不会超过正则表达式长度的2倍,所以这里直接开辟一个大小为正则表达式长度为2倍的Graph结构
    遇到非运算符,及正则表达式里面的转移符号的时候,这里就需要构造一个基本的NFA, 一个初始状态,一个终止状态,然后由初始状态至终止状态有一条为该转移符号的边,此时仍然需要检查正则表达式的下一个符号,如果不是运算符或者为左括号,此时应该运算栈中添加一个连接运算符,然后将构造的基本NFA添加入NFA栈中,方便以后将基本的NFA进行其他选择,重复,连接运算
    遇到非运算符时,需要分一下四种运算符的情况
    如果是运算符“)”,即右括号,此符号属于运算级最高的符号了,所以它要在符号栈中弹出所有符号运算,直到遇到“)”匹配,运算过程中根据符号栈中弹出的符号计算
    如果是运算符“(”,即左括号,此符号只是用来和右括号结合的,所以直接将该运算符压入符号栈中即可
    如果是运算符“*”,即重复符号,这个在正则表达式中运算级最高,直接进行计算,计算方法就是从NFA栈中弹出一张图,然后得到两个未分配的新节点,添加4条上面图表示的那样的边,然后重新设定NFA的start和end之后将新的NFA压入NFA栈中即可,运算后检查其后跟随的元素,如果是转移符号或者左括号,则必须要向符号栈中添加连接符号
    如果是运算符“+”,即选择符号,由于此符号的优先级没有连接符号高,所以此时应该弹出符号栈中优先级高于它的符号,但是“(”不参与弹出,所以这里只是弹出连接符号和自身“+”符号运算,然后将该符号压入符号栈等候计算
    正则表达式遍历完毕之后,需要弹出所有的符号栈进行计算,最后NFA栈中的唯一NFA就是所求的NFA
接下来就是具体的运算的算法,这里点与点的连接通过更新Graph中相应的点的邻接链表即可
    连接运算,此时需要弹出NFA栈中的两个NFA,然后将其中一个的end连接至另一个的start,然后更新新的NFA的start和end,压入NFA栈中。
    选择运算,此时需要弹出NFA栈中的两个NFA,然后Graph重新分配两个节点,作为新的NFA的start和end,然后新的start分别连接弹出的两个NFA的start,弹出的两个NFA的end分别连接新的end即构成新的NFA,压入NFA栈中。
    闭包运算,此时需要弹出NFA栈中的一个NFA,然后Graph重新分配两个节点,作为新的NFA的start和end,然后新的start连接弹出NFA的start,弹出NFA的end连接新的end,然后添加一条新的start到新的end的一条空边和一条旧的end到旧的start的一条空边,将新的NFA压入NFA栈中。

 

NFA的显示

 
 
具体的显示方法是从Graph的start节点开始调用绘制函数,该绘制函数的功能是首先检查该节点是否绘制,如果未绘制则进行绘制,如果已经绘制则不进行绘制