732
技海無涯：正則表達式相關的知識和技術(3)——編程技巧:堆棧的本質探討
編程技巧——堆棧的本質探討
如果我要說本章的編程技巧就是為了介紹堆棧的使用技巧，你可能會笑掉大牙：哈哈，堆棧，這不是小兒科嗎？！！
是的，每個編程的人都知道的堆棧，而且說起堆棧，大家肯定會馬上想到“後進先出（LIFO）”，這是教科書關於堆棧本質的解釋。
沒錯，堆棧的本質是LIFO，但絕不是簡單的先進後出就完了，結合各種各樣的壓棧出棧操作，堆棧可以實現很強大的功能。下麵就以正則表達式涉及的兩個例子來說明堆棧的妙用。
1) 通過堆棧來完成正則表達式->NFA.
在介紹表達式的時候提到過我們書寫的正則表達式是中綴表達式，但計算機識別的時候是需要將中綴表達式轉換成NFA的。
問題出現了：正則表達式是有優先級的，例如*號優先級最高，然後（）裏麵是當作一個完整的單元來處理的。例如如下正則表達式：
ab*|c(d|a)
按照Thompson算法，正確的處理順序應該如下：
（1）生成a的NFA
（2）生成b*的NFA，將a和b*的NFA連接起來，假設NFA為X；
（3）生成c的NFA
（4）遇到括號，生成括號裏麵的NFA；
（5）將c的NFA和括號的NFA連接起來；假設NFA為Y；
（6）將NFA X和NFA 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轉換後能夠達到的狀態集”。我們看一個樣例：
如果狀態轉換關係是上麵這種形式，那就很簡單，直接遞歸或者循環都可以搞定，但實際的正則表達式的轉換關係不可能是這種一維的形式的，而是一個有向無環圖，類似於如下這種複雜的形式：
這種情況無論是遞歸還是循環都無法解決，而利用堆棧就可以巧妙的解決這個圖的遍曆問題。此處使用堆棧的原理為：取出棧頂狀態，看這個狀態經過1個epsilon轉換能夠到達哪些狀態，將這些狀態又都壓入棧。如下是上麵樣例的操作步驟：
1、 棧初始為1，
2、 彈出1，發現1經過1個epsilon轉換能夠達到2、3、4，因此壓入2、3、4；
3、 按照第二步操作（後麵都一樣，不再贅述），彈出4，壓入7、8；
4、 彈出8；8沒有可以經過epsilon轉換能夠到達的狀態，因此此處沒有壓棧操作了（後麵也一樣，不在贅述）。
5、 彈出7；壓入9；
6、 彈出9；
（………………………………剩下的就請各位自己分析了）
細心的大俠們可能會發現，上麵的處理步驟和人的分析過程是一樣的，也就是說通過堆棧讓計算機模擬了人的思維。
綜合以上兩個例子，我們可以得出堆棧真正的本質：改變計算機的順序處理，讓計算機能夠模擬人的處理步驟。
所以大家在使用堆棧的時候不要死抱著LIFO，然後先全部壓棧再全部出棧，這樣的操作在實際應用中除了將字符串倒序外沒有任何用處，堆棧真正的妙用是“在處理過程中進行壓棧出棧”！
========================未完待續==================================
最後更新：2017-04-02 00:06:48