表達式解析-字尾表達式

引言

         前一段時間,因為需要在産品内部的腳本解析程式中引入表達式解析功能,研究了一下表達式解析的常用方法.

         表達式解析是程式設計語言中最基本的功能之一,我們日常使用的一般為中綴表達式,然而中綴表達式的解析比較複雜,在計算機中的解析一般是将中綴表達式轉化為字尾表達式（又叫逆波蘭表達式）,然後進行解析.

概念

         中綴表達式:通用的算術以及邏輯公式表示方式,其表達式中操作符位于操作數中間.中綴表達式不易被計算機解析,但其符合人們的日常使用.

         字尾表達式:不包含括号，操作符位于兩個操作數後面，所有的計算依據操作符的出現順序，嚴格按照從左到右的順序進行，不考慮操作符的優先級别.

解析

         表達式的解析過程一般分為以下幾步.

1.       掃描表達式,獲得表達式中的每一個獨立的詞素(Token).

2.       轉化掃描後的中綴表達式為字尾表達式.

3.       計算字尾表達式.

         中綴表達式計算一般采用”算符優先法”, 其必須嚴格按照以下規則進行計算:

1.       先計算括号.

2.       先計算優先級高的操作符

3.       從左到右進行計算.

為實作解析,需要兩個棧,一個用于儲存操作符,一個用于儲存操作數以及結果,當讀到操作符時并不能立即作計算,需要與操作符棧頂元素進行優先級比較,根據結果然後采用不同的處理方式, 而且算法較字尾表達式不管是時間複雜度或者是空間複雜度都要高.

字尾表達式由于其自身的優點,表達式的解析是按照操作符的出現順序進行的,比較簡單,掃描一遍即可完成解析.但需要将中綴表達式轉化為字尾表達式.

表達式轉化

         對于簡單的中綴表達式可以很容易的獲得字尾表達式,但對于複雜的中綴表達式,可以通過二叉樹來表示表達式,然後對其進行前序,中序或者後序周遊即可獲得想要的表達式.這種方式很友善表達式轉化.在此介紹一種簡單的轉化算法.

可以通過棧來處理,基本思路如下:

1.       從左到右讀取中綴表達式,依次一個操作項.

2.       如果是操作數直接進入輸出隊列.

3.       讀到左括号時總是将它壓入棧中.

4.       讀到右括号, 将最近棧頂的第一個左括号上面的操作符全部依次彈出, 送至輸出隊列後, 再丢棄左括号.

5.       當讀到操作符時,将棧中所有優先級高于或等于目前操作符的操作符彈出，送到輸出隊列中.

6.       中綴表達式全部讀完後，若棧中仍然有運算符，将其送到輸出隊列中./

舉例

         中綴表達式:   3 * (1 + 4)

         字尾表達式:   1 4 + 3 *