正则表达式的等价判定

前端之家收集整理的这篇文章主要介绍了正则表达式的等价判定前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

编译原理的两个课程设计之一,关于两个正则表达式是否等价的问题。题目描述及提交地址: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,d代表相应的字符(也即我们考虑的语言定义在字母表 ={a,d}上),而e代表空串є,其它符号的意义和“龙书”一致. expr1和expr2的长度不超过80,且均保证是合法表达式. 输入以一个'#'号结束.

Output

对于每组数据,如果expr1和expr2等价,则输出“YES”;否则,输出“NO”.


对于这个项目,复习相关知识用了一天半,敲代码用了一天,调试用了半天,前后大概三天可以完成。作业提交截止后,撰写此文供日后自己复习和回顾,供他人参考和点评。

需要注意的是,本人参考的书籍为《编译原理》(即“龙书”)第二版中文翻译版,代码有前后三个版本:alpha(有调试和跟踪信息),beta(能通过SOJ但没注释),gamma(有注释和过程输出),若想看初始代码请查看alpha版本,若想只求AC请查看beta版本,若想了解算法请查看gamma版本。本文使用的代码为gamma版本,而作为解释说明的版本,代码并不能够直接在Sicily上AC通过,也就是不会严格符合文章开始时所描述的大概内容

书籍下载:http://download.csdn.net/detail/ederick/5043025

代码下载:http://download.csdn.net/detail/ederick/5043904

另外参考:http://mcs.sysu.edu.cn/user/chenzz/Article_1591

最后感谢王建同学和李晓潮同学的帮助,帮我解答了一些疑问以及提供了一些典型例子,避免了很多麻烦,多谢!

一些技巧和细节会在下文中说明,测试样例也会放出,请留意找寻。


下面开始程序流程的介绍:

要求是判断两个正则表达式是否等价,总的步骤可以划分为四部分:

1.正则表达式转换成NFA;
2.NFA转换成DFA;
3.DFA最小化;
4.判断两个最小化DFA是否等价。

各个部分大概的流程如下所示:

A. 正则表达式转换成NFA:

这一部分的代码实现基本上遵循龙书上第3.7.4章节中的算法3.23(P100),即McMaughton-Yamada-Thompson算法。子NFA的构造方法如书上所说,这里不再熬述。

需要说明的是,个人修改过其中的的一个部分,即把归约规则中的r = st,并没有按书上所说把N(s)的接受状态和N(t)的开始状态合并,而是在两者之间通过ε转换来连接。另外,对于书上没有描述的?和+也自行构造了NFA的模版。还有的是,本人也没有对正则表达式先进行后缀表示的转换,而是直接对其进行分析并构造NFA。在这里,r = st会当作r = s & t来处理。

基本思路是,创建两个栈分别用于存储操作符和子NFA,然后从头到尾开始遍历正则表达式。对于当前处理的字符,作以下判断和处理:

Ø 如果是字母,并且如果前一字符是abcde)*+?中的一个,进行如下操作:a.如果栈顶操作符是&,执行catNFA();否则跳过此步骤b.压入操作符&构造当前字母的NFA并压栈;

Ø 如果是操作符|,当栈非空并且栈顶不是&时,不断把栈顶的|或者&操作弹出来,并执行相应的orNFA()或者catNFA();最后压入|操作符;

Ø 如果是操作符?、*、+,则直接执行相应的queNFA()、starNFA()、plusNFA();

Ø 如果是(,并且如果前一字符是abcde)*+?中的一个,进行如下操作:a.如果栈顶操作符是&,执行catNFA();否则跳过此步骤b.压入操作符&最后将(压栈;

Ø 如果是),当栈顶不是(时,不断把栈顶的|或者&操作弹出来,并执行相应的orNFA()或者catNFA();最后把栈顶的(弹出。

说明一下,queNFA()、starNFA()、plusNFA()需要一个子NFA,而orNFA()、catNFA()需要两个子NFA。对于以上操作,是基于操作符的优先级顺序:(>*= + = ? >& >|>)的进行的。

这一部分的代码如下:

  1. /*********************正则转NFA**********************************************/
  2. unsigned N,M; //分别表示NFA和DFA的状态数
  3. string s; //正则表达式
  4. string sub( "abcde)*+?" ); //正则表达式中需要构造子NFA的字符
  5. stack<char> sign; //存储操作符
  6. stack< pair<int,int> > nfa; //存储子NFA
  7. vector<int> NFA[ 160 ][ 5 ]; //NFA的状态转移表
  8.  
  9. /*对于是字母(a、b、c、d、e)的NFA构造方法*/
  10. void alpNFA( int i ) {
  11. pair<int,int> r;
  12. r.first = N++;
  13. r.second = N++;
  14. NFA[ r.first ][ i ].push_back( r.second );
  15. nfa.push( r );
  16. }
  17.  
  18. /*对于是|的NFA构造方法*/
  19. void orNFA() {
  20. sign.pop();
  21. pair<int,int> r;
  22. r.first = N++;
  23. r.second = N++;
  24. pair<int,int> s = nfa.top();
  25. nfa.pop();
  26. pair<int,int> t = nfa.top();
  27. nfa.pop();
  28. NFA[ r.first ][ 4 ].push_back( s.first );
  29. NFA[ r.first ][ 4 ].push_back( t.first );
  30. NFA[ s.second ][ 4 ].push_back( r.second );
  31. NFA[ t.second ][ 4 ].push_back( r.second );
  32. nfa.push( r );
  33. }
  34.  
  35. /*对于是?的NFA构造方法*/
  36. void queNFA() {
  37. pair<int,int> s = nfa.top();
  38. nfa.pop();
  39. NFA[ r.first ][ 4 ].push_back( s.first );
  40. NFA[ r.first ][ 4 ].push_back( r.second );
  41. NFA[ s.second ][ 4 ].push_back( r.second );
  42. nfa.push( r );
  43. }
  44.  
  45. /*对于是&的NFA构造方法*/
  46. void catNFA() {
  47. sign.pop();
  48. pair<int,int> t = nfa.top();
  49. nfa.pop();
  50. pair<int,int> r( s.first,t.second );
  51. NFA[ s.second ][ 4 ].push_back( t.first );
  52. nfa.push( r );
  53. }
  54.  
  55. /*对于是*的NFA构造方法*/
  56. void starNFA() {
  57. pair<int,int> s = nfa.top();
  58. nfa.pop();
  59. NFA[ r.first ][ 4 ].push_back( s.first );
  60. NFA[ r.first ][ 4 ].push_back( r.second );
  61. NFA[ s.second ][ 4 ].push_back( s.first );
  62. NFA[ s.second ][ 4 ].push_back( r.second );
  63. nfa.push( r );
  64. }
  65.  
  66. /*对于是+的NFA构造方法*/
  67. void plusNFA() {
  68. pair<int,int> s = nfa.top();
  69. nfa.pop();
  70. NFA[ r.first ][ 4 ].push_back( s.first );
  71. NFA[ s.second ][ 4 ].push_back( s.first );
  72. NFA[ s.second ][ 4 ].push_back( r.second );
  73. nfa.push( r );
  74. }
  75.  
  76. /*初始化NFA相关状态*/
  77. void resetNFA() {
  78. N = 0;
  79. for ( int i = 0; i < 160; i++ ) {
  80. for ( int j = 0; j < 5; j++ )
  81. NFA[ i ][ j ].clear();
  82. }
  83. while ( !sign.empty() )
  84. sign.pop();
  85. while ( !nfa.empty() )
  86. nfa.pop();
  87. }
  88.  
  89. /*正则表达式转NFA*/
  90. void RE2NFA() {
  91. resetNFA();
  92. /*遍历字符串,对相关字符进行对应操作*/
  93. for ( unsigned i = 0; i < s.size(); i++ ) {
  94. if ( isalpha( s[ i ] ) ) {
  95. /*判断是否需要加上操作符&*/
  96. if ( i != 0 && sub.find( s[ i - 1 ] ) != string::npos ) {
  97. if ( !sign.empty() && sign.top() == '&' )
  98. catNFA();
  99. sign.push( '&' );
  100. }
  101. alpNFA( s[ i ] - 'a' );
  102. }
  103. else if ( s[ i ] == '|' ) {
  104. while ( !sign.empty() && sign.top() != '(' ) {
  105. if ( sign.top() == '|' )
  106. orNFA();
  107. else if ( sign.top() == '&' )
  108. catNFA();
  109. }
  110. sign.push( '|' );
  111. }
  112. else if ( s[ i ] == '?' )
  113. queNFA();
  114. else if ( s[ i ] == '*' )
  115. starNFA();
  116. else if ( s[ i ] == '+' )
  117. plusNFA();
  118. else if ( s[ i ] == '(' ) {
  119. /*判断是否需要加上操作符&*/
  120. if ( i != 0 && sub.find( s[ i - 1 ] ) != string::npos ) {
  121. if ( !sign.empty() && sign.top() == '&' )
  122. catNFA();
  123. sign.push( '&' );
  124. }
  125. sign.push( '(' );
  126. }
  127. else if ( s[ i ] == ')' ) {
  128. while ( sign.top() != '(' ) {
  129. if ( sign.top() == '|' )
  130. orNFA();
  131. else if ( sign.top() == '&' )
  132. catNFA();
  133. }
  134. sign.pop();
  135. }
  136. }
  137.  
  138. /*清空操作符栈,获取最终NFA*/
  139. while ( !sign.empty() ) {
  140. if ( sign.top() == '|' )
  141. orNFA();
  142. else if ( sign.top() == '&' )
  143. catNFA();
  144. }
  145. }
  146.  
  147. /*输出NFA的各项数据*/
  148. void showNFA() {
  149. cout << "**********第一步:NFA各项数据如下***************\n";
  150. pair<int,int> r = nfa.top();
  151. cout << "状态数:" << N << "\t";
  152. cout << "开始状态:" << r.first << "\t" << "接受状态:" << r.second << endl;
  153. cout << "\ta\tb\tc\td\tε\n";
  154. for ( unsigned i = 0; i < N; i++ ) {
  155. cout << i << ":\t";
  156. for ( unsigned j = 0; j < 5; j++ ) {
  157. sort( NFA[ i ][ j ].begin(),NFA[ i ][ j ].end() );
  158. cout << "{";
  159. for ( unsigned k = 0; k < NFA[ i ][ j ].size(); k++ ) {
  160. cout << NFA[ i ][ j ][ k ];
  161. if ( k + 1 != NFA[ i ][ j ].size() )
  162. cout << ",";
  163. }
  164. cout << "}\t";
  165. }
  166. cout << endl;
  167. }
  168. }

这里面有几个技巧和细节,罗列如下:

1.返回值采用pair<int,int>的形式是为了便于获取NFA的开始状态和接受状态;
2.NFA的数组开到160,是因为每个符号最多构造2个状态,80个字符就是160个状态;
3.?和+操作符的NFA构造可以等价于a?=(a|e),a+=aa*就可以很方便地得到了;
4.sub字符串的存在是为了便于判断是否需要添加&进操作符栈。

B. NFA转换成DFA

基本上如同龙书算法3.20(P97)的描述一样,通过子集构造算法,我们可以从一个NFA中构造出相应的DFA。这一部分按照书上的内容可以按部就班完成,如下:


其中的函数意义如下:


较为重要的计算e-closure(T)的方法如下:


D的开始状态是e-closure(S@H_403_198@0),接受状态是所有至少包含了N的一个接受状态的状态集合。

这一部分的代码如下:

  1. /*********************NFA转DFA************************************************/
  2. map< vector<int>,int > trans; //NFA的状态和DFA的状态对应关系
  3. vector<int> acc; //DFA中的接受状态
  4. int DFA[ 1600 ][ 5 ]; //DFA的状态转换表
  5.  
  6. /*计算e-closure(T)*/
  7. vector<int> eClosure( vector<int> T ) {
  8. stack<int> s;
  9. vector<int>::iterator it;
  10. int t;
  11. for ( it = T.begin(); it != T.end(); it++ )
  12. s.push( *it );
  13. while ( !s.empty() ) {
  14. t = s.top();
  15. s.pop();
  16. for ( it = NFA[ t ][ 4 ].begin(); it != NFA[ t ][ 4 ].end(); it++ ) {
  17. if ( find( T.begin(),T.end(),*it ) == T.end() ) {
  18. T.push_back( *it );
  19. s.push( *it );
  20. }
  21. }
  22. }
  23. sort( T.begin(),T.end() );
  24. return T;
  25. }
  26.  
  27. /*计算move(T,a)*/
  28. vector<int> move( vector<int> T,int a ) {
  29. vector<int>::iterator it1,it2;
  30. vector<int> U;
  31. for ( it1 = T.begin(); it1 != T.end(); it1++ ) {
  32. for ( it2 = NFA[ *it1 ][ a ].begin(); it2 != NFA[ *it1 ][ a ].end(); it2++ ) {
  33. if ( find( U.begin(),U.end(),*it2 ) == U.end() )
  34. U.push_back( *it2 );
  35. }
  36. }
  37. return U;
  38. }
  39.  
  40. /*初始化DFA数据*/
  41. void resetDFA() {
  42. M = 0;
  43. trans.clear();
  44. acc.clear();
  45. }
  46.  
  47. /*把NFA转换成DFA*/
  48. void NFA2DFA() {
  49. resetDFA();
  50. pair<int,int> r = nfa.top();
  51. vector<int> T,U;
  52. T.push_back( r.first );
  53. U = eClosure( T );
  54.  
  55. vector< vector<int> > Dstates;
  56. stack< vector<int> > s;
  57. Dstates.push_back( U );
  58. s.push( U );
  59. trans[ U ] = M++;
  60. if ( find( U.begin(),r.second ) != U.end() )
  61. acc.push_back( M - 1 );
  62. while ( !s.empty() ) {
  63. T = s.top();
  64. s.pop();
  65. for ( int a = 0; a < 4; a++ ) {
  66. U = eClosure( move( T,a ) );
  67. if ( find( Dstates.begin(),Dstates.end(),U ) == Dstates.end() ) {
  68. Dstates.push_back( U );
  69. s.push( U );
  70. trans[ U ] = M++;
  71. if ( find( U.begin(),r.second ) != U.end() )
  72. acc.push_back( M - 1 );
  73. }
  74. DFA[ trans[ T ] ][ a ] = trans[ U ];
  75. }
  76. }
  77. }
  78.  
  79. /*输出DFA的各项数据*/
  80. void showDFA() {
  81. cout << "**********第二步:DFA各项数据如下***************\n";
  82. cout << "状态数:" << M << "\t";
  83. cout << "开始状态:" << 0 << "\t" << "接受状态:";
  84. for ( unsigned i = 0; i < acc.size(); i++ )
  85. cout << acc[ i ] << " ";
  86. cout << endl;
  87. cout << "\ta\tb\tc\td\n";
  88. for ( unsigned i = 0; i < M; i++ ) {
  89. cout << i << ":\t";
  90. for ( int j = 0; j < 4; j++ )
  91. cout << DFA[ i ][ j ] << "\t";
  92. cout << endl;
  93. }
  94. }

技巧和细节说明如下:

1.DFA的状态上限设为1600没什么特别的原因,只是开大点以防内存溢出而已;
2.
选用vector是因为状态数不确定,所以开数组不方便;而又不需要list快速插入删功能,综合权衡之下采取vector来存储数据;
3.
可以留意到计算闭包后对vector进行了排序,这是为了后面计算得出来的vector能够有序,确保map中键值的比较正确,以及方便输出DFA状态转移表;
4.
采用map是为了NFADFA中的状态得以对应,其中mapvector有很好的包容性,所以操作符[]使用起来相当方便;

C. DFA最小化

算法原则是基于龙书上算法3.39(P115),关键的分组部分如下:

代码如下:

  1. /*********************DFA最小化***********************************************/
  2. int groups[ 1600 ][ 5 ]; //输入符号状态转移到的分组
  3. bool included[ 1600 ]; //状态的分组去向是否已确定
  4. vector< vector<int> > PI,nPI; //原分组和新分组
  5. int L; //最小化DFA的状态数
  6. int MAP[ 1600 ]; //DFA和最小化DFA的状态对应关系
  7. int MIN[ 1600 ][ 5 ]; //最小化DFA的状态转移表
  8. int start; //最小化DFA的开始状态
  9. vector<int> fin; //最小化DFA的接受状态
  10.  
  11. /*对状态划入分组*/
  12. void grouping( int n ) {
  13. unsigned i,j,k;
  14. int t;
  15. vector<int> v;
  16.  
  17. for ( i = 0; i < PI[ n ].size(); i++ ) {
  18. for ( j = 0; j < 4; j++ ) {
  19. t = DFA[ PI[ n ][ i ] ][ j ];
  20. for ( k = 0; k < PI.size(); k++ ) {
  21. if ( find( PI[ k ].begin(),PI[ k ].end(),t ) != PI[ k ].end() ) {
  22. groups[ PI[ n ][ i ] ][ j ] = k;
  23. break;
  24. }
  25. }
  26. }
  27. }
  28.  
  29. for ( i = 0; i < PI[ n ].size(); i++ ) {
  30. if ( !included[ PI[ n ][ i ] ] ) {
  31. v.clear();
  32. v.push_back( PI[ n ][ i ] );
  33. included[ PI[ n ][ i ] ] = true;
  34. for ( j = i + 1; j < PI[ n ].size(); j++ ) {
  35. if ( !included[ PI[ n ][ j ] ] ) {
  36. for ( k = 0; k < 4; k++ ) {
  37. if ( groups[ PI[ n ][ i ] ][ k ] != groups[ PI[ n ][ j ] ][ k ] )
  38. break;
  39. }
  40. /*判断两个状态是否划入了同一个分组*/
  41. if ( k == 4 ) {
  42. v.push_back( PI[ n ][ j ] );
  43. included[ PI[ n ][ j ] ] = true;
  44. }
  45. }
  46. }
  47. nPI.push_back( v );
  48. }
  49. }
  50. }
  51.  
  52. /*初始化最小化DFA的各项数据*/
  53. void resetMIN() {
  54. unsigned i,j;
  55. vector<int> v1,v2;
  56. for ( i = 0; i < M; i++ ) {
  57. if ( find( acc.begin(),acc.end(),i ) == acc.end() )
  58. v1.push_back( i );
  59. else
  60. v2.push_back( i );
  61. }
  62. PI.clear();
  63. nPI.clear();
  64. nPI.push_back( v1 );
  65. nPI.push_back( v2 );
  66. }
  67.  
  68. /*DFA转化成最小化DFA*/
  69. void DFA2MIN() {
  70. resetMIN();
  71. unsigned i,j;
  72. /*细分分组*/
  73. memset( groups,sizeof( groups ) );
  74. while ( PI.size() != nPI.size() ) {
  75. PI = nPI;
  76. nPI.clear();
  77. memset( included,false,sizeof( included ) );
  78. for ( i = 0; i < PI.size(); i++ )
  79. grouping( i );
  80. }
  81.  
  82. /*确定状态对应关系*/
  83. L = 0;
  84. for ( i = 0; i < PI.size(); i++ ) {
  85. for ( j = 0; j < PI[ i ].size(); j++ ) {
  86. MAP[ PI[ i ][ j ] ] = L;
  87. if ( PI[ i ][ j ] == 0 )
  88. start = L;
  89. }
  90. L++;
  91. }
  92.  
  93. /*获取接受状态*/
  94. fin.clear();
  95. for ( i = 0; i < acc.size(); i++ ) {
  96. if ( find( fin.begin(),fin.end(),MAP[ acc[ i ] ] ) == fin.end() )
  97. fin.push_back( MAP[ acc[ i ] ] );
  98. }
  99. sort( fin.begin(),fin.end() );
  100.  
  101. /*构造状态转移表*/
  102. memset( included,sizeof( included ) );
  103. for ( i = 0; i < M; i++ ) {
  104. if ( !included[ MAP[ i ] ] ) {
  105. included[ MAP[ i ] ] = true;
  106. for ( j = 0; j < 4; j++ )
  107. MIN[ MAP[ i ] ][ j ] = MAP[ DFA[ i ][ j ] ];
  108. }
  109. }
  110. }
  111.  
  112. /*输出最小化DFA*/
  113. void showMIN( int nMIN[ 2000 ][ 5 ],int nstart,vector<int> nfin,int nL ) {
  114. cout << "**********第三步:MIN各项数据如下***************\n";
  115. cout << "状态数:" << nL << "\t";
  116. cout << "开始状态:" << nstart << "\t" << "接受状态:";
  117. for ( vector<int>::iterator it = nfin.begin(); it != nfin.end(); it++ )
  118. cout << *it << " ";
  119. cout << endl;
  120. cout << "\ta\tb\tc\td\n";
  121. for ( int i = 0; i < nL; i++ ) {
  122. cout << i << ":\t";
  123. for ( int j = 0; j < 4; j++ )
  124. cout << nMIN[ i ][ j ] << "\t";
  125. cout << endl;
  126. }
  127. }

D. 判断两个最小化DFA是否等价

基本思路是通过对两个最小化DFA进行同步DFS遍历,而遍历的原则是:

对于两者访问的下一个节点:

1.都未被访问,则访问,进入深一层的遍历;
2.都已访问,改变字符输入寻求下一个未被访问的节点。

需要注意的是,当两者在遍历的过程中,碰到以下情况时:

1.其中一个到达了接受状态而另一个还处于非接受状态;
2.两者即将访问的下一个节点的深度不一样(都没被访问的话视作深度相同);

可以认为两个最小化DFA不是等价的。如果两者成功同步访问完所有的节点,即遍历过程中没有碰到以上的两种情况,就可以认为两个最小化DFA是等价的。

代码如下:

  1. /*********************正则转最小DFA及比较*************************************/
  2. int P,Q; //两个最小化DFA的状态数
  3. int MIN1[ 1600 ][ 5 ],MIN2[ 1600 ][ 5 ]; //两个最小化DFA的状态转移表
  4. int start1,start2; //两个最小化DFA的开始状态
  5. vector<int> fin1,fin2; //两个最小化DFA的结束状态
  6. int deep; //同步遍历时的深度
  7. int vis1[ 1600 ],vis2[ 1600 ]; //两个最小化DFA在同步遍历时各个状态的深度
  8.  
  9. /*正则表达式转最小化DFA*/
  10. void RE2MIN( int nMIN[ 1600 ][ 5 ],int &nstart,vector<int> &nfin,int &nL ) {
  11. RE2NFA();
  12. showNFA();
  13. NFA2DFA();
  14. showDFA();
  15. DFA2MIN();
  16. memcpy( nMIN,MIN,sizeof( MIN ) );
  17. nstart = start;
  18. nfin = fin;
  19. nL = L;
  20. }
  21.  
  22. /*同步遍历*/
  23. bool traversal( int n1,int n2 ) {
  24. int i,m1,m2;
  25. vis1[ n1 ] = vis2[ n2 ] = ++deep;
  26. for ( i = 0; i < 4; i++ ) {
  27. m1 = MIN1[ n1 ][ i ];
  28. m2 = MIN2[ n2 ][ i ];
  29. if ( find( fin1.begin(),fin1.end(),m1 ) == fin1.end() && find( fin2.begin(),fin2.end(),m2 ) != fin2.end() )
  30. break;
  31. if ( find( fin1.begin(),m1 ) != fin1.end() && find( fin2.begin(),m2 ) == fin2.end() )
  32. break;
  33. if ( vis1[ m1 ] != vis2[ m2 ] )
  34. break;
  35. if ( vis1[ m1 ] == 0 && !traversal( m1,m2 ) )
  36. break;
  37. }
  38. --deep;
  39. return i == 4;
  40. }
  41.  
  42. /*判断两个正则表达式是否等价*/
  43. bool equal() {
  44. if ( P != Q )
  45. return false;
  46. memset( vis1,sizeof( vis1 ) );
  47. memset( vis2,sizeof( vis2 ) );
  48. deep = 0;
  49. return traversal( start1,start2 );
  50. }


最后的主函数如下,大功告成:

  1. /*********************主函数部分*********************************************/
  2. int main()
  3. {
  4. while ( true ) {
  5. cout << "请输入第一个正则表达式:";
  6. cin >> s;
  7. if ( s == "#" )
  8. break;
  9. RE2MIN( MIN1,start1,fin1,P );
  10. showMIN( MIN1,P );
  11.  
  12. cout << "\n请输入第二个正则表达式:";
  13. cin >> s;
  14. RE2MIN( MIN2,start2,fin2,Q );
  15. showMIN( MIN2,Q );
  16.  
  17. cout << "\n两个正则表达式的等价结果:";
  18. cout << ( equal() ? "YES": "NO" ) << endl << endl << endl;
  19. }
  20.  
  21. return 0;
  22.  
  23. }

随便输入一个正则表达式,效果如下:

至此,所有工作完成。由于时间比较赶,代码当中应该存在不少错漏,效率上可能也不如人意,仍然有待改进。


附:测试样例和答案

a?

a|e YES

b*|a+

a+|b* YES

aa*|bb*

b+|a+ YES

e+++++*?*?*?++

eeee YES

(a|b)(a|b)

aa|ab|bb NO

(a|b)*

((e|a)b*)* YES

a+(aa)+

(aa)+a NO

a+(aa)+

(aa)+a+ YES

d*c+d?c*

d*c*d?c* NO

(a|b)|(c|d)

(c|d)|(a|b) YES

(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)

(a|b)*b(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b) NO

(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)

(a|b)*a(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b)(a|b) YES

b*a*b?a*

b*((a|ab)*|(a|ba)*) NO

猜你在找的正则表达式相关文章