字符串算法—正则表达式

1. 前文回顾

　　在字符串算法—字符串搜索中，我们实现了从一堆字符中搜索某个字符串的高效算法。

　　但如果要在一堆字符中找具有某些规律的字符串（要找的字符串是不确定的，但有规律），该如何设计算法？

　　本文将介绍NFA算法来解决此问题。

?

2. 正则表达式

　　首先，有规律的字符串是长什么样的呢？例如：ABBBBBBBBBA。

　　我们需要用一种方式来表达这个规律。于是我们就有了正则表达式。

　　ABBBBBBBBBA可以表达为AB*A。其中B*表示有N个B，N可以为0。

　　然后以下均是正则表达式：

　　

　　

　　[A-E]+表示：(A|B|C|D|E)(A|B|C|D|E)*

　　

　　有了这些表达式后，我们就能让程序读懂字符串的规律，然后就是让它找出含有这规律的字符串在哪了。

　　

3. NFA算法

　　本算法需要有向图基础，如果不了解有向图的，可以先看一下图表算法—有向图。

　　从例子中开始了解此算法：

　　现有正则表达式：?( ( A * B | A C ) D )。

　　我们通过某种构建方法（此方法稍后介绍），把这个正则表达式变成一个有向图：

　　

?

　　我们将逐个逐个符号来读这个表达式。图中的0,1,2,3,...,10,11是阶段，当我们抵达第11阶段，则说明找到符合这表达式的字符串。

　　图中的线有两种颜色，红色的是过渡线，可以不读阶段里面的内容，直接跳到下一个指定阶段；蓝色是正常线，要先读阶段里面的内容，再改变阶段。

　　例如：第4阶段只能去第5阶段；第1阶段可以去第2阶段、第3阶段、第4阶段、第6阶段。

　　现在我们来看一下AAAABD是否符合这个表达式：

　　第一个字符为A，我们从第0阶段开始：

　　

　　0,1阶段都是括弧，故符合。现在1可以去2、3、4和6，且2和6都是A，与第一个字符匹配，故两个阶段都去：

　　

　　第二个字符为A，现在可以去2,4,7(其中去2的路线为2-3-2，去4的路线为2-3-4)，但匹配第二个字符的只有第2阶段，故去第2阶段：

　　

　　第三个字符为A，现在可以去2,4(其中去2的路线为2-3-2，去4的路线为2-3-4)，但匹配第三个字符的只有第2阶段，故去第2阶段：

　　

　　第四个字符为A，现在可以去2,4(其中去2的路线为2-3-2，去4的路线为2-3-4)，但匹配第四个字符的只有第2阶段，故去第2阶段：

　　

　　第五个字符为B，现在可以去2,4(其中去2的路线为2-3-2，去4的路线为2-3-4)，但匹配第五个字符的只有第4阶段，故去第4阶段：

　　

　　第六个字符为D，现在可以去9(其中去9的路线为4-5-8-9,由于5,8都是符号，不能与字符比较，故无视它们)，第9阶段匹配第五个字符，故去第9阶段：

　

　　没有第七个字符，且第9阶段可以直接抵达第11阶段，故这个字符串符合此表达式。

　　如果要从这个字符串中，找出有多少个符合此表达式的字符串，则经过上面的寻找，我们找到了第一个：AAAABD。

　　接下来寻找第二个，从第二个字符开始第0阶段，如果能顺利抵达第11阶段，说明AAABD也符合；否则，AAABD不符合。

　　然后第三个，从第三个字符开始第0阶段，如此类推，直到所有字符都开始过第0阶段为止，然后统计有多少个字符串符合，且记住它们的位置。

　　如此类推，我们可以找出整段字符中符合这个表达式的所有字符串，从而解决一开始提出的问题。

　　接下来就要看如何把这个正则表达式转化为有向图了：

　　首先，如果某阶段里含有的不是符号，而是字符，则可以直接去下一个阶段：

　　

　　然后，如果遇到的是符号 *,则分两种情况：

　　1. *所处的阶段的前一阶段是字符：

　　

　　则加3条方向（不用担心重复加方向，因为代码中如果出现重复的，直接覆盖）。

　　2.?*所处的阶段的前一阶段是右括弧：

　　

　　也是加3条方向：与前一个左括弧加一个互相的方向，我们会用一个数字lp来记住前一个左括弧。

　　回到我们的这个例子，给*阶段添加方向：（符号用的线都是过渡线）

　　

　　如果遇到的是左括弧或者是 | 则要把它们按顺序加到栈中，顺便给左括弧加一个指向下一个阶段的方向：（新建栈A）

　　

?

　　如果遇到的是右括弧，则给它加一个指向下一个阶段的方向，且栈A输出数个元素，直到见到左括弧为止：

　　

?

?

　　然后栈A输出一个元素（先进先出）：第5阶段的 | ，新建一个整数int or=5来记住它，并且给它加一个指向目前所处位置的右括弧处：

　　

?

　　然后栈A输出一个元素：第1阶段的（，给它加一个指向or+1位置的方向：（如果有多个or，则分别指向各个or+1位置）

　　

?

?

　　然后遇见的是第10阶段的），给它加一个指向下一个阶段的方向，且栈A输出数个元素，直到见到左括弧为止：

　　

?

　　然后栈A输出一个元素：第0阶段的（，中途没见到 |,因此不作操作：

　　

?

　　然后去到第11阶段，构建完毕。

代码实现：

　　根据正则表达式构建有向图：

　　

　　图中红色箭头处，它默认了栈下一个吐出来的是左括号，但如果吐出来的是 |,则会出错，这里应该做一个针对连续吐出多个 | 的处理（加个判断）。

　　这段代码只处理了符号，应该添加代码给字符所处的阶段指向下一个阶段。

　　使用这个有向图来寻找字符串：