棧的應用----四則運算,后綴逆波蘭表示法(RPN) -开发者知识库

棧的應用----四則運算,后綴逆波蘭表示法(RPN) -开发者知识库,第1张

   我們從小就學習四則運算――加減乘除四則。我們也知道,要先乘除后加減,遇到括號要先算括號內的。可是,想讓計算機進行這樣的四則運算可不容易,它可不知道什么乘除優先,然后加減。那么,該如何讓計算機也能進行這樣的四則運算呢?就是通過棧。

   我們人類非常熟悉也非常喜歡用中綴表示法進行算數運算,什么是中綴表示法呢?也就是,一個運算符在兩個數字中間。比如,5 3,3*5,5/2等等,這些都是中綴表示法。這種表示法很適合人類使用,但是卻不適用於計算機,於是,我們就想出了一種適合計算機的表示方式,叫做,后綴表示法,也就是運算符出現在待運算數字的后面。比如,5 3,這種叫做中綴表示法,用后綴表示法就是,5 3 ,這樣的方式就是后綴表示法。也就是說,想讓計算機進行運算,首先就要把中綴表達式轉換成后綴表達式。接着才是對后綴表達式進行運算。

   那么先來講,中綴表達式轉換成后綴表達式是如何通過棧實現的。我們假設有這么一個中綴表達式:

5   4 * 6 / ( 3   7 ) * 2   1

我們遵循這樣的一個原則,遇到數字就直接將數字輸出,遇到運算符就將運算符壓入棧中。如果當前運算符跟棧頂運算符相比,優先級高於棧頂運算符,就將此運算符壓入棧中,該運算符成為新的棧頂運算符。換言之,如果該運算符不高於棧頂運算符,則棧頂元素依次出棧,並將當前符號進棧。好了,開始轉換。首先是5,所以,我們要將5輸出,因為5是數字,遇到數字就直接輸出,那么輸出為:

5

接着是一個“ ”,因為是運算符,所以將運算符入棧。

 

接着,仍然是數字,所以將4輸出,

5 4

由於接下來的是一個乘號,所以,要將它與棧頂的運算符進行對比,發現*號優先級高於 號優先級,所以,將*號入棧,這樣以來,棧頂元素就為*號。

  *

由於6也是數字,所以,可以將其輸出

5 4 6

接下來,是個關鍵。因為,接下來的一個符號是/號,所以,當它和*號對比時,發現/號優先級並不高於*號優先級,所以,將棧頂元素依次出棧,也就是

*

所以,目前,輸出元素為

5 4 6 *

然后,將/號入棧,此時棧中只有一個符號/

  /

接着,是一個左括號( ,所以要將(入棧,直到碰到)是將括號內的內容出棧。

  / (

因為是數字,所以將3出棧

5 4 6 * 3

接着將 號入棧

  / (  

接着是一個數字7,很明顯,將數字7出棧

5 4 6 * 3 7

這時碰到了),所以要將 出棧,

5 4 6 * 3 7  

此時,棧中元素為,

  /

接着是一個*號,將它與/號對比,發現,它不高於*號,所以,將/出棧,然后跟 號對比,發現高於 號,所以,*可以入棧了,所以,輸出元素如下:

5 4 6 * 3 7   /

棧中數據如下:

  *

接着是一個數字2,將2直接輸出

5 4 6 * 3 7   / 2

接着是一個 號,優先級並不高於*號,也不高於棧底的 號,所以,將棧頂元素依次出棧,

5 4 6 * 3 7   / 2 *  

然后將該 號入棧,所以,此時棧內元素為

 

當碰到最后一個1的時候,直接將1輸出。

5 4 6 * 3 7   / 2 *   1

最后了,已經沒有元素了,此時,就將棧中的 號輸出,所以,最后,后綴表達式為:

5 4 6 * 3 7   / 2 *   1  

   此時,已經將我們人類認識的中綴表達式轉換成了機器認識的后綴表達式。那么,此時,就可以開始運算了,運算還是需要借助棧。當碰到數字時,還是需要將數字壓入棧,當碰到運算符時,從棧頂將元素取出,並進行運算。比如,5 4 6都是數字,於是,將5 4 6入棧,

5 4 6

接下來碰到了*號,所以,將6取出作為乘數,將4取出作為被乘數,進行相乘運算,4 * 6 = 24,此時,將運算結果24存入棧中。所以,棧中元素為:

5 24

因為3 7都是數字,所以,將3 7保存至棧中。

5 24 3 7

因為接下來碰到了一個 號,所以,將7和3取出,進行3 7 = 10的運算,然后將運算結果10放入棧中。

5 24 10

接下來是一個/號,所以,將10取出作為除數,將24取出作為被除數,所以,24 / 10 = 2.4,然后將2.4存入棧中,所以,

5 2.4

接下來,是一個數字2,所以,將2壓入棧中

5 2.4 2

然后是一個乘號,所以將2和2.4取出,執行2.4 * 2 = 4.8,將4.8壓入棧中

5 4.8

因為接下來是一個 號,所以將5和4.8取出,執行5 4.8 = 9.8,此時將9.8入棧

9.8

然后將數字1入棧

9.8 1

最后一個 號,所以將兩個數出棧,執行9.8 1 = 10.8,最后運算結果為,10.8。到此就完全結束了。

其實,我舉的這個例子是有問題的,棧中保存的是類型相同的元素,所以我這個例子舉的不好,不過不影響總結計算機執行四則運算的過程。

本文出自 “梵高說我腦子有病” 博客,請務必保留此出處http://chen0547.blog.51cto.com/12489941/1968001

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复