570      技術社區[雲棲]

技海無涯：正則表達式相關的知識和技術(1)——表達式

正則表達式，看似簡單，實則博大精深。簡簡單單幾個字符：|、*、（、）……卻能夠演繹出無窮無盡的變化。初看正則表達式，其實就是一串子字符串，但隱藏在這字符串背後的各種各樣的知識、技能、技巧，卻一點也不簡單。

以前在學習《編譯原理（龍書）》的時候，也是一目十行的將其跳過，這次偶爾需要用到正則表達式，然後自己就上網搜了搜，結果發現水不是一般的深，耗費了3個晚上的時間搜索、查閱，才稍微理清了這些相關知識的關係和脈絡，於是稍作整理歸納，既為了加深自己的理解，也為了共享給各位。

在正式開始之前，先將相關東東列出來，看看你能夠知道幾個？

NFA、逆波蘭表達式、雙棧、自動機、子集算法、中綴表達式、Thompson算法。

技海無涯：正則表達式相關的知識和技術

看到下麵這一堆東東，你是不是覺得頭皮發麻，思維混亂呢？

NFA、逆波蘭表達式、雙棧、自動機、子集算法、中綴表達式、Thompson算法……

按照這種散亂無章的順序來理解和記憶，當然是感覺很混亂了。 其實事情沒有那麼複雜，要想理解起來容易，記憶也牢固，我們要抓住一條思維的線路，然後將這一堆的東東沿著思維的線路進行分門別類，下麵就是我總結出來的正則表達式的思路：

表達式->轉換算法->編程技巧->自動機。

首先正則表達式是一個表達式，但這個表達式最終是要讓計算機理解和應用，這個理解和應用就是自動機。從表達式到自動機需要經過轉換算法，在實現轉換算法的時候有一些編程技巧，這樣就把正則表達式從表達式到自動機串起來了。

下麵我們一一介紹，這裏隻介紹簡單的概念和知識點以及關聯關係，詳細的研究還需要各位自己上網查了。

表達式

表達式有幾個相關的概念：前綴表達式、中綴表達式、後綴表達式、波蘭表達式、逆波蘭表達式。

概念介紹

前綴、中綴、後綴表達式很好理解，就是操作符在操作數前麵、中間、後麵，對應的英文分別是prefix notation, infix notation, postfix notation，英文好的大俠可以到google上直接搜索英文，有很多詳細的介紹（如果要看詳細的介紹和分析，一定要看英文），這裏就不詳細介紹了。

l         前綴表達式prefix notation：操作符在操作數前麵，例如3+4轉化成前綴表達式就是+34；

l         中綴表達式infix notation：操作符在操作數中間，例如3+4轉化成中綴表達式就是3+4；

l         後綴表達式postfix notation：操作符在操作數後麵，例如3+4轉化成後綴表達式就是34+；

表達式對比

三種表達式各自的特點和作用是什麼呢？其實說白了就是誰理解更容易的問題：

前綴表達式：不好意思，我還沒有弄懂前綴表達式的作用，據說是在Lisp語言中用到，有可能是Lisp這種語言更好理解前綴表達式。

中綴表達式：人更好理解，從小到大四則運算我們都是這麼用的，大家寫正則表達式也是這麼寫的；

後綴表達式：計算機更好理解，沒有括號，沒有優先級，按照順序計算即可。

正則表達式的書寫、四則運算的書寫，都是按照中綴表達式來寫的，但實際在計算機處理的時候，是需要轉換成後綴表達式來進行處理（當然也可以不完全轉換成後綴表達式後再進行計算，可以邊分析邊計算，後麵在講編程技巧的時候會詳細分析）。

波蘭、逆波蘭

介紹到這裏，似乎表達式的格式都涵蓋了，總不可能來個“上綴”或者“下綴”表達式吧？既然這樣的話，相信你一定會有這樣的疑問：

1）什麼叫波蘭表達式？什麼叫逆波蘭表達式？

2）和波蘭有什麼關係麼？

其實答案很簡單，波蘭表達式就是前綴表達式，逆波蘭表達式就是後綴表達式。至於為什麼和波蘭扯上關係，其實也很簡單，就是因為波蘭表達式是波蘭的邏輯學家Jan Łukasiewicz發明的，就像大家熟悉的Microsoft的“匈牙利命名法”，其實就是一個匈牙利工程師提出來的一樣。

至於為什麼沒有“中波蘭”表達式，這個還沒有研究，也許哪位大俠申請一下，從此可以多一個“中國表達式”：）

參考資料

https://en.wikipedia.org/wiki/Reverse_Polish_notation

https://en.wikipedia.org/wiki/Prefix_notation

========================未完待續==================================

最後更新：2017-04-02 00:06:48

  上一篇： [轉貼]計算機編程名言精選

  下一篇： [原創]利用MASM宏顯示環境變量