四則表達式實作原理_F_hawk189_新浪部落格

首先是将中綴表達式轉化為字尾表達式：

在計算機中計算一個字尾表達式的值要比計算一個中綴表達式的值簡單的多

實作轉換的基本步驟如下：

1.初始化一個運算符棧。

2.從算數表達式輸入的字元串中依次從左向右每次讀取一個字元。

3.如果目前字元是操作數，則直接填寫到字尾表達式。

4.如果目前字元是（左括号，将其壓入運算符棧（第一步定義）。

5.如果目前字元為運算符，則分兩種情況：

運算符棧為空，将其壓入運算符棧。

此運算符的優先級大于棧頂元素的時候），則将此運算符壓入運算符棧；否則，彈出棧頂運算符到字尾表達式，反複彈出，直到該運算符優先級大于棧頂元素或者棧為空時，然後将目前運算符壓棧。回到步驟2繼續讀取.

6.如果目前字元是）右括号，反複将棧頂元素彈出到字尾表達式，直到棧頂元素是左括号（為止，并将左括号從棧中彈出丢棄。

7.如果讀取還未完成，回到步驟2.

8.如果讀取完成，則将棧中剩餘的運算符依次彈出到字尾表達式。

舉個例子：

a+b*c-(d+e)

1.讀取到操作數 a，将其放入最終字尾表達式，此時表達式為：a ， 棧為空

2.讀取到運算符 +，此時棧為空，+ 入棧，此時表達式為：a ， 棧為：+

3.讀取到操作數 b， 将其放入最終字尾表達式，此時表達式為：ab ， 棧為： +

4.讀取到運算符 *， 棧不為空，* 優先級大于棧頂元素 + ，* 入棧，此時表達式為：ab ， 棧為： +*

5.讀取到操作數 c， 将其放入最終字尾表達式，此時表達式為：abc ， 棧為： +*

6.讀取到運算符 -，棧不為空， - 優先級小于棧頂元素 *，* 出棧，此時表達式為：abc* ， 棧為： +，  

                            -優先級等于棧頂元素 +， + 出棧，此時表達式為：abc*+ ， 棧為： 空 

                            棧為空，是以 - 入棧，此時表達式為：abc*+ ， 棧為： -

7.讀取到運算符（ ， ( 直接入棧，此時表達式為：abc*+ ， 棧為： -(

8.讀取到操作數 d，将其放入最終字尾表達式，此時表達式為：abc*+d ， 棧為： -(

9.讀取到運算符 +，+ 優先級大于 (  , + 入棧，此時表達式為：abc*+d ， 棧為： -(+

10.讀取到操作數 e，将其放入最終字尾表達式，此時表達式為：abc*+de ， 棧為： -(+

11.讀取到運算符 ），棧頂元素為 +，出棧 ，此時表達式為：abc*+de+ ， 棧為： -(

                                 棧頂元素為（ ，出棧， 此時表達式為：abc*+de+ ， 棧為： -

12，此時表達式已經周遊完畢，按順序出棧，棧頂元素為 - ，出棧，此時表達式為：abc*+de+- ， 棧為： 空

結束。

字尾表達式求值：

從左到右讀取

1、設定一個棧，開始時，棧為空；

2、然後從左到右掃描字尾表達式，若遇操作數，則進棧；