实验2：生产流水线的自动规划器

实验二：生产流水线的自动设计器
一、实验内容：
输入一个表示要准备进行设计的生产流水线对应的正则表达式，最终完成整个生成流水线的自动设计。
二、必做实验要求：
（1）正则表达式应该支持单个字符，运算符号有： 连接 选择(|) 闭包(*) 正闭包（+） 可选（?） 括号
（2）要提供一个源程序编辑界面，让用户输入表示生成流水线处理过程的正则表达式（可保存、打开正则表达式文件）
（3）需要提供窗口以便用户可以查看转换得到的NFA（用状态转换表呈现即可）
（4）需要提供窗口以便用户可以查看转换得到的DFA（用状态转换表呈现即可）
（5）需要提供窗口以便用户可以查看转换得到的最小化DFA（用状态转换表呈现即可）
（6）要求应用程序为Windows界面
（7）书写完善的软件文档
三、选做实验要求：
完成绘制转换得到的NFA图,DFA图以及最小化的DFA图
如果选做该内容，实验文档以及使用说明书中就一定要有关于这个内容的设计文档及执行操作说明

1.输入正则表达式

第一关：特殊运算符： ‘&’ ， ‘|’ ， ‘*’ ， ‘+’ ， ‘?’ , ‘[ ]’

扫描一行符号

1.去掉空格
2.方括号要转换形式，从[1-5],变成 （1|2|3|4|5）这样方便进一步转换

因为连接符号在正则表达式中是隐形的，所以为了转换，需要手动加上‘&’表示连接符号。

1. 两个字符之间需要加一个 “&”
   这几种情况要加& ： “a a” 、“a (” 、“* a” 、“* (” 、“) a” 、 “) (”
   比如原字符串：a|bcs[1-3]asds
   加&后 ： a|b&c&s&(1|2|3)&a&s&d&s
   开始遍历
   如果栈内的运算符优先级大于等于当前运算符，则弹出栈内运算符

 //添加连接符'&'int length = raw.length();QString rawadd;for(int i=0;i<length;i++){rawadd.append(raw[i]);if(i < length-1 && ((isAlpha(raw[i]) && isAlpha(raw[i+1])) || (isAlpha(raw[i]) && raw[i+1] == '(') || (raw[i] == '*' && isAlpha(raw[i+1]))|| (raw[i] == '*' && raw[i+1] == '(') || (raw[i] == ')' && isAlpha(raw[i+1])) || (raw[i] == ')' && raw[i+1] == '('))){rawadd.append('&');}}

字符可以直接加入到 总的字符串中，因为在中缀和后缀表达式中，数字的位置都是一样的。遇到5大符号（ ‘&’ ， ‘|’ ， ‘*’ ， ‘+’ ， ‘?’），则需要单独处理，进入栈中，这块还有一些逻辑。

‘[ ]’

方括号太抽象， 这里转换成更具体的范围 （||||） 用圆括号和 || 来表示
QString::toLatin1是相当于 ASCii码不包含中文的遇到中文默认转换为ascii码。
bracket（）函数 ， 即当遇到[ - ]这段的时候，用 （||||）替代，其他原封不动的保存。

QString bracket(QString raw)
{QString p;int i=0;while(i<raw.length()){if(raw[i] == '['){p.append('(');char c1 = raw[++i].toLatin1();p.append(c1);i++;char c3 = raw[++i].toLatin1();for(int j=(c1-'0')+1;j<=(c3-'0');j++){p.append('|');p.append(char(j+'0'));}i++;p.append(')');}else{p.append(raw[i]);}i++;}return p;
}

正则表达式是中缀的，但是为了方便使用后缀表达式

中缀表达式 9+（3-1）x3+10÷2
后缀表达式9 3 1 - 3 x + 10 2 ÷ +
开两个栈结构，一个放数字，一个放符号。
从左到右。9 入数字栈
+号 入符号栈（目前栈空，栈空就进栈）
（ 入符号栈
目前栈里从上到下：（ +
3入数字栈
当前表达式为 9 3

• 入栈
  目前栈里从上到下：-（ +
  正则表达式中总共有以下的符号。

算法思路如下：

QString process, 和一个栈结构 operator
process相当于数字栈， operator 相当于符号栈

NFA

正则表达式转成后缀之后，就可以开始构建图结构。
以邻接表形式存储NFA图
后缀表达式，按照扫描的方式来做：

基本NFA图：
是两个结点一条边。
之后构图就是由这些基本结点连接，形成图。
而连接这些基本的结点的就是 空，一条边。

例子：

源字符串： a|b*[1-3]a*
加了&之后：a|b*&(1|2|3)&a*
变成后缀之后：ab12|3|&a&|
现在用后缀生成NFA状态表和图结构

这里定义一个NFA类，NFA有两个指针，分别指向初态和终态。

struct NFA
{Linknode* start = nullptr;Linknode* end = nullptr;NFA(Linknode* s, Linknode* e){start = s;end = e;}
};