技海无涯:正则表达式相关的知识和技术(3)——编程技巧:堆栈的本质探讨

编程技巧——堆栈的本质探讨

如果我要说本章的编程技巧就是为了介绍堆栈的使用技巧,你可能会笑掉大牙:哈哈,堆栈,这不是小儿科吗?!!

是的,每个编程的人都知道的堆栈,而且说起堆栈,大家肯定会马上想到“后进先出(LIFO)”,这是教科书关于堆栈本质的解释。

没错,堆栈的本质是LIFO,但绝不是简单的先进后出就完了,结合各种各样的压栈出栈操作,堆栈可以实现很强大的功能。下面就以正则表达式涉及的两个例子来说明堆栈的妙用。

1) 通过堆栈来完成正则表达式->NFA.

在介绍表达式的时候提到过我们书写的正则表达式是中缀表达式,但计算机识别的时候是需要将中缀表达式转换成NFA的。

问题出现了:正则表达式是有优先级的,例如*号优先级最高,然后()里面是当作一个完整的单元来处理的。例如如下正则表达式:

ab*|c(d|a)

按照Thompson算法,正确的处理顺序应该如下:

1)生成aNFA

2)生成b*NFA,将ab*NFA连接起来,假设NFAX

3)生成cNFA

4)遇到括号,生成括号里面的NFA

5)将cNFA和括号的NFA连接起来;假设NFAY

6)将NFA XNFA Y连接起来,得到最终的NFA,假设为Z

人是可以识别出这种先后顺序,但是计算机扫描的时候是从左往右扫描,没有超前扫描的功能,例如计算机扫描到b的时候,并不知道后面马上会有一个*,那计算机该怎么处理呢?

这正是堆栈发挥作用的时候。通过堆栈的压栈和出栈操作,我们可以改变操作顺序,以让计算机来完成类似于人的分析过程

这里还用到一个技巧就是双堆栈,即:运算符一个堆栈,操作数一个堆栈,下面我们看看用堆栈,计算机如何完成正则表达式到NFA的转换。

1)将a压入操作数栈;

2)读到b的时候,由于正则表达式本身没有连接操作符,因此将b压入操作数栈的同时,我们需要同时自己压一个&符号到运算符栈,方便后面处理。

3)读入*,由于*号优先级比&高,所以继续将*压栈;

4)读入|,由于‘|’比*号优先级低,所以这个时候就要把*弹出来,再把b弹出来,生成b*NFA

5)这时运算栈里面只有&,由于‘|’比&优先级也低,所以就要把&弹出来,然后把a弹出来,和第4步已经完成的b*NFA生成ab*NFA

6)此时运算栈里面已经没有运算符了,所以把‘|’压入。

………………………………剩下的就请各位自己分析了)

 

2) 通过堆栈来完成NFA->DFA.

NFA转换到DFA的子集构造算法最核心的就是构造子集闭包,也就是算法中的epsilon_closure函数。

epsilon_closure函数的关键在于找到“经过1个或多个epsilon转换后能够达到的状态集”。我们看一个样例:

技海无涯:正则表达式相关的知识和技术(3)——编程技巧:堆栈的本质探讨

 

如果状态转换关系是上面这种形式,那就很简单,直接递归或者循环都可以搞定,但实际的正则表达式的转换关系不可能是这种一维的形式的,而是一个有向无环图,类似于如下这种复杂的形式:

 

 技海无涯:正则表达式相关的知识和技术(3)——编程技巧:堆栈的本质探讨

这种情况无论是递归还是循环都无法解决,而利用堆栈就可以巧妙的解决这个图的遍历问题。此处使用堆栈的原理为:取出栈顶状态,看这个状态经过1epsilon转换能够到达哪些状态,将这些状态又都压入栈。如下是上面样例的操作步骤:

1  栈初始为1

2  弹出1,发现1经过1epsilon转换能够达到234,因此压入234

3  按照第二步操作(后面都一样,不再赘述),弹出4,压入78

4  弹出88没有可以经过epsilon转换能够到达的状态,因此此处没有压栈操作了(后面也一样,不在赘述)。

5  弹出7;压入9

6  弹出9

………………………………剩下的就请各位自己分析了)

细心的大侠们可能会发现,上面的处理步骤和人的分析过程是一样的,也就是说通过堆栈让计算机模拟了人的思维。

 

综合以上两个例子,我们可以得出堆栈真正的本质:改变计算机的顺序处理,让计算机能够模拟人的处理步骤

所以大家在使用堆栈的时候不要死抱着LIFO,然后先全部压栈再全部出栈,这样的操作在实际应用中除了将字符串倒序外没有任何用处,堆栈真正的妙用是“在处理过程中进行压栈出栈”

========================未完待续==================================

上一篇:技海无涯:正则表达式相关的知识和技术(1)——表达式


下一篇:Python,Jupyter Notebook,IPython快速安装教程