林瀚编译原理projectA
sicily题目链接http://soj.me/show_problem.php?pid=1000&cid=866
Description
两个正则表达式等价，是指两个表达式描述完全相同的语言，即正则表达式expr1和expr2等价，当且仅当L(expr1)=L(expr2).
编写判断两个正则表达式是否等价的程序.
Input
有多组输入数据. 每组数据有两个正则表达式expr1和expr2，每个正则表达式占一行. expr1和expr2仅含有字符a, b, c, d, e, |, (, ), *, +, ?，其中a, b, c, d代表相应的字符（也即我们考虑的语言定义在字母表 ={a, b, c, d}上），而e代表空串є，其它符号的意义和“龙书”一致. expr1和expr2的长度不超过80，且均保证是合法表达式.输入以一个'#'号结束.
Output
对于每组数据，如果expr1和expr2等价，则输出"YES”；否则，输出"NO”.
算法的基本思路
正则表达式->NFA->DFA->最小DFA，如果两个正则表达式求出的最小DFA完全相同的话，则说明是等价的；如果不相同，则不等价。
具体如下ε
1. 正则表达式转化成NFA，使用Thompson构造法，由于Thompson构造法无法对+和？进行构造，而根据+和？的定义，可以把它们转化为等价的连接和*。此外，为了更好的分辨单个的字母和连接的多个字母，在应该人为的添加连接符，便于识别。所以，在构造NFA之前，要对正则表达式进行预处理，具体处理如下：
a) 类似a+，处理成aa*
b) 类似a？，处理成（a|e）
c) 类似ab，处理成a.b
2. 正则表达式转成NFA的过程，主要用两个栈来模拟，st存放操作符，sNFA则保存每次用Thompson构造NFA后一个整体的开始状态和最后一个状态。对预处理后的正则表达式扫描，遇到字母则构造NFA，并压入sNFA；遇到操作符，则和st栈顶的操作符比较优先级，优先级大于栈顶操作符则压入st，小于则根据栈顶操作符弹出sNFA中相应个数的元素。整个过程结束后，sNFA中一定还剩一个元素，这个元素中存有这个正则表达式转换成NFA后的开始状态和结束状态。
函数reToNFA()，其中会用到的重要函数makeSingle(char input, NFA n)，makeAND(NFA left,NFA right)，makeOR(NFA left, NFA right)，makeMUTI(NFA op)
3. 从NFA构造DFA用的是子集构造法。首先从NFA的开始状态开始，对其求闭包集，即通过e可以到达的状态号的集合。然后对集合输入对正则中的每个字母，求其到达的状态号的闭包集合。直到不再产生新的集合，则完成了DFA的构造，而DFA集合中有NFA的开始状态的，也是DFA的开始状态集合；而包含NFA的结束状态的DFA集合都是DFA的接收状态，其余的都是非接收状态。
函数NFAToDFA()，其中会用到的重要函数
move(vector<int>input,char in, vector<Edge> edge) //状态转移函数,返回in条件下input的转移集
findNullClosure(vector<int>input, vector<Edge> edge) //返回所能通过空到达的状态集
4. 由DFA构造最小DFA，算法用的是IInew的构造
函数minimizeDFA();用到的重要函数
equalCombine();//合并相同项
futiRemove();//删除无用项
5. 判断最小DFA是否相同，如果两个最小DFA的边不一样，则正则表达式不等价；若相同，则可通过判断最小DFA的开始状态，接受状态，甚至非接受状态；如果这些都相同，说明正则表达式等价；否则不等价。
函数 isEqual（string r1， string r2）