Duffblog

?在計算機中進行算術表達式的計算是通過棧來實現的。這一節首先討論算術表達式的兩種表示方法，即中綴表示法和后綴表示法，接著討論后綴表達式求值的算法，最后討論中綴表達式轉換為后綴表達式的算法。
1.?算術表達式的兩種表示
通常書寫的算術表達式是由操作數(又叫運算對象或運算量)和運算符以及改變運算次序的圓括號連接而成的式子。操作數可以是常量、變量和函數，同時還可以是表達式。運算符包括單目運算符和雙目運算符兩類，單目運算符只要求一個操作數，并被放在該操作數的前面，雙目運算符要求有兩個操作數，并被放在這兩個操作數的中間。單目運算符為取正’+’和取負’-’，雙目運算符有加’+’,減’-’,乘’*’和除’/’等。為了簡便起見，在我們的討論中只考慮雙目運算符。
如對于一個算術表達式2+5*6，乘法運算符’*’的兩個操作數是它兩邊的5和6；對于加法運算符’+’的兩個操作數，一個是它前面的2，另一個是它后面的 5*6的結果即30。我們把雙目運算符出現在兩個操作數中間的這種習慣表示叫做算術表達式的中綴表示，這種算術表達式被稱為中綴算術表達式或中綴表達式。
中綴表達式的計算比較復雜，它必須遵守以下三條規則：
(1)?先計算括號內，后計算括號外；
(2)?在無括號或同層括號內，先進行乘除運算，后進行加減運算，即乘除運算的優先級高于加減運算的優先級；
(3)?同一優先級運算，從左向右依次進行。
從這三條規則可以看出，在中綴表達式的計算過程中，既要考慮括號的作用，又要考慮運算符的優先級，還要考慮運算符出現的先后次序。因此，各運算符實際的運算次序往往同它們在表達式中出現的先后次序是不一致的，是不可預測的。當然憑直觀判別一個中綴表達式中哪個運算符最先算，哪個次之，……，哪個最后算并不困難，但通過計算機處理就比較困難了，因為計算機只能一個字符一個字符地掃描，要想得到哪一個運算符先算，就必須對整個中綴表達式掃描一遍，一個中綴表達式中有多少個運算符，原則上就得掃描多少遍才能計算完畢，這樣就太浪費時間了，顯然是不可取的。
那么，能否把中綴算術表達式轉換成另一種形式的算術表達式，使計算簡單化呢??回答是肯定的。波蘭科學家盧卡謝維奇(Lukasiewicz)很早就提出了算術表達式的另一種表示，即后綴表示，又稱逆波蘭式，其定義是把運算符放在兩個運算對象的后面。采用后綴表示的算術表達式被稱為后綴算術表達式或后綴表達式。在后綴表達式中，不存在括號，也不存在優先級的差別，計算過程完全按照運算符出現的先后次序進行，整個計算過程僅需一遍掃描便可完成，顯然比中綴表達式的計算要簡單得多。例如，對于后綴表達式12! 4!-!5!/，其中’!’字符表示成分之間的空格，因減法運算符在前，除法運算符在后，所以應先做減法，后做除法；減法的兩個操作數是它前面的12和 4，其中第一個數12是被減數，第二個數4是減數；除法的兩個操作數是它前面的12減4的差(即8)和5，其中8是被除數，5是除數。
中綴算術表達式轉換成對應的后綴算術表達式的規則是：把每個運算符都移到它的兩個運算對象的后面，然后刪除掉所有的括號即可。
例如，對于下列各中綴表達式：
(1)?3/5+6
(2)?16-9*(4+3)
(3)?2*(x+y)/(1-x)
(4)?(25+x)*(a*(a+b)+b)
對應的后綴表達式分別為：
(1)?3!5!/!6!+
(2)?16!9!4!3!+!*!-
(3)?2!x!y!+!*!1!x!-!/
(4)?25!x!+!a!a!b!+!*!b!+!*

2.?后綴表達式求值的算法
后綴表達式的求值比較簡單，掃描一遍即可完成。它需要使用一個棧，假定用S表示，其元素類型應為操作數的類型，假定為浮點型float，用此棧存儲后綴表達式中的操作數、計算過程中的中間結果以及最后結果。假定一個后綴算術表達式以字符’@’作為結束符，并且以一個字符串的方式提供。后綴表達式求值算法的基本思路是：把包含后綴算術表達式的字符串定義為一個輸入字符串流對象，每次從中讀入一個字符（空格作為數據之間的分隔符，不會被作為字符讀入）時，若它是運算符，則表明它的兩個操作數已經在棧S中，其中棧頂元素為運算符的后一個操作數，棧頂元素的下一個元素為運算符的前一個操作數，把它們彈出后進行相應運算即可，然后把運算結果再壓入棧S中；否則，讀入的字符必為操作數的最高位數字，應把它重新送回輸入流中，然后把下一個數據作為浮點數輸入，并把它壓入到棧S中。依次掃描每一個字符（對于浮點數只需掃描它的最高位并一次輸入整個浮點數）并進行上述處理，直到遇到結束符’@’為止，表明后綴表達式計算完畢，最終結果保存在棧中，并且棧中僅存這一個值，把它彈出返回即可。具體算法描述為：
此算法的運行時間主要花在while循環上，它從頭到尾掃描后綴表達式中的每一個數據（每個操作數或運算符均為一個數據），若后綴表達式由n個數據組成，則此算法的時間復雜度為O(n)。此算法在運行時所占用的臨時空間主要取決于棧S的大小，顯然，它的最大深度不會超過表達式中操作數的個數，因為操作數的個數與運算符（假定把’@’也看作為一個特殊運算符，即結束運算符）的個數相等，所以此算法的空間復雜度也同樣為O(n)。
假定一個字符串a為：
char?a[30]="12?3?20?4?/?*?8?-?6?*?+@";
對應的中綴算術表達式為12+(3*(20/4)-8)*6@，則使用如下語句調用上述函數得到的輸出結果為54。
cout<?在進行這個后綴算術表達式求值的過程中，從第四個操作數入棧開始，每處理一個操作數或運算符后，棧S中保存的操作數和中間結果的情況如圖4-4所示。

?

?

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1423390