实验三：算符优先算法一、实验目的：1使用算符优先算法将输入的正则表达式转化位 NFA2 加强对算法优先算法的理解，加强将正则表达式转化为NFA方法的理解；3强化对系统软件综合工程实现能力的训练。二、实验内容：用C语言或者其他的高级语言开发完成将输入的正则表达式转化为NFA勺程序。三、实验要求：1. 编写一个程序，能将输入的正则表达式转化为 NFA源程序并调试通过。2. 通过测试程序的验收；3. 提交实验报告，报告必须包含以下内容：(1) 程序功能描述；(2) 程序数据结构描述；(3) 函数或模块描述：函数功能、流程图，函数参数含义、返回值描述；(4) 函数之间的调用关系描述和程序总体执行流程图；(5) 实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时 间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？(6) 手写实验报告使用学校要求的实验稿纸，打印实验报告使用B5纸打印。四、评判标准：1输出正确的实验结果；2. 代码清晰，格式良好；3. 提交报告，报告阐述清楚。五、程序工作说明：(1)程序接受文本文件中输入的正则表达式，生成该正则表达式对应的NFA在屏幕上显示出这个NFA 统计并输出该NFA中的节点个数和边的个数；(3) 输入的正则表达式中包含的运算符包括：连接运算符”.”，闭包运算符“”,逻辑或运算符“”，左括号(，“右括号“”。运算符的运算优先级从高到低位 (*.|)(4) 输入的正则表达式中的字符限于大写英文字母，小写英文字母，数字09;NFA使用图的邻接链表或者邻接矩阵存储；(6)程序的调试者和执行者保证输入的正则表达式正确，程序不检查正则表达式的正确性。六、结构体和算法流程如果NFA用图的邻接链表存储，邻接链表中存储边信息的结构体：struct Arrowint nEndStatelD;/箭弧终点的节点状态 IDchar chLetter; /箭弧上标注的字符struct Arrow * pNextArrow;/与当前边有相同开始接点的下条箭弧；邻接链表中存储节点信息的结构体:struct Stateint nStatelD;/顶点编号，在整个 NFA中定点编号是唯一的struct Arrow *pFirstArrow; /当前顶点的连接的第一条箭弧的指针；NFA中的状态在图中用图的节点表示，NFA的所有状态保存在邻接链表的节点结点结构体数组中，结构体定义：struct NFAstruct State StateListMAX; /表示头结点的数组（就是NFA的状态）int stateCount; /有效的状态个数int arrowCount; /箭弧的个数;每个输入符号都要生成一个NFA （就是一对开始结束节点和中间连着的箭弧），输入符号生成的NFA要进栈，输入符号对应的NFA的栈结构体：struct stateStackstruct State * pStateListMAX; /栈空间int top; /栈顶，栈顶元素在数组中的下标;正则表达式的运算符栈struct operatorStackchar chOperatorListMAX;/ 栈空间int top; /栈顶，栈顶元素在数组中的下标;算符优先算法初始化状态栈；初始化运算符栈；I#压进入运算符栈；在正则表达式末尾添加 #运算符；产生一个初始0号节点读取正则表达式的首符；while（正则表达式没有结束）if（当前字符是正则表达式的字符）产生一对新开始和结束节点；在开始节点和结束节点之间拉一条标注为当前字符的箭弧; 将开始节点和结束节点压入状态栈；读取下一个字符；elseif（当前操作符运算优先级别比栈顶运算符优先级别高）当前操作符压入符号栈；读取下一个字符；else if （当前操作符运算优先级别比栈顶运算符优先级别低）运算符栈的栈顶运算符出栈；if （出栈运算符是连接符）从状态栈中弹出一对开始结束节点A ；从状态栈中弹出一对开始结束节点B ；从B的结束节点拉一条e指示的箭弧到A的开始节点；B的开始节点和A的结束节点作为一对开始结束节点入状态栈;从状态栈中弹出一对开始结束节点 A ； 从状态栈中弹出一对开始结束节点 B ； 生成一对新的开始结束节点 C ；从C的开始节点拉一条e指示的箭弧到A的开始节点; 从C的开始节点拉一条e指示的箭弧到B的开始节点; 从A的结束节点拉一条e指示的箭弧到C的结束节点; 从B的结束节点拉一条e指示的箭弧到C的结束节点; C的开始节点和结束节点作为一对节点入状态栈；else if （出栈运算符是闭包运算符）从状态栈中弹出一对开始结束节点 A ;生成一对新的开始结束节点 C;从C的开始节点拉一条e指示的箭弧到A的开始节点； 从A的结束节点拉一条e指示的箭弧到C的结束节点； 从A的结束节点拉一条e指示的箭弧到A的开始节点 从C的开始节点拉一条e指示的箭弧到C的结束节点 C的开始节点和结束节点作为一对开始结束节点入状态栈;else if（当前操作符运算优先级别比栈顶运算符优先级别相等if （栈顶运算符是左括号，当前运算符是右括号）从状态栈中弹出一对开始结束节点A ;从0号节点拉一条e指示的箭弧到A的开始节点;操作说明：产生一对新开始和结束节点：就是在结构体 struct NFA的结构体成员stateCount的值增加2,表示结构体中的成员StateList数组中的有效元素增加2个，数组的成员是结构体 struct State，该结构体有2个数据成员：nStatelD （表示节点ID）和pFirstArrow （表示这个 节点上出发的箭弧链表）；设置新增的2个数组成员的 StateListstateCount-1和StateListstateCount-2的nStateID的值为 唯一的状态ID，第一条箭弧的指针 pFirstArrow赋值为空；在开始节点和结束节点之间拉一条标注为当前字符的箭弧：|在结构体NFA的成员StateList数组中查找到开始节点（找到开始节点对应的下标），该数组元素是个struct State类型的结构体，结构体 struct State中有个指针成员pFirstArrow，该指针成员指示的链表是所有从这个顶点出发的箭弧，在 这个链表中增加一个链表元素（可以用头插法或者尾插法插入），表示新增加的边。该新增的链表元素是个结构体structArrow，设置该结构体中的箭弧终点的节点状态nEndStateID的值为结束节点的ID，箭弧上标注的字符chLetter的值为当前字符，箭弧的下一个指针pNextArrow的值根据头使用插入还是尾插法进行不同的设置；C的开始节点和结束节点作为一对开始结束节点入状态栈：C实际是结构体 NFA中的成员StateList数组中的2个数组成员，结构体的struct stateStack的中代表栈空间的成员pStateList是指针数组，数组的成员中存放 struct State类型的地址，只要把C中2个节点在结构体 NFA中的成员StateList 数组中的地址赋值给 stateStack的中代表栈空间的成员pStateList的数组成员。七、举例边数皿r-?- 71-?- 9J-?-!正则表达式: 节点个数“E1 I-a- 212 -?- 313 t-b- 414 -? 115 -?-6 -T-M.2 J7 L-b- 818 -?- ?911 -?- 51121314