計算機底層運算小科普

四則運算對於我們來說，再熟悉不過了。例如「1+1=2「、「2*2=4」，小學的時候我們就不陌生了，即使稍微難一點的「先乘除後加減」，「7+(6-3)×4+8÷2」，我們也能很容易的心算出是23。

對我們來說四則運算當然容易，但是對計算機來說就不一樣了，他們可不能一眼看出先計算後面的乘號還是先計算括弧內的加減。

不過，人類是非常聰明的，波蘭邏輯學家盧卡西維茨發明了一種名為後綴表達式的方法，讓計算機能非常方便的處理四則運算。

先讓我們看看後綴表達式和一般的表達式有什麼不同，例如上文提到的

「7+(6-3)×4+8÷2」

它的後綴表達式是這個樣子的

「7 6 3 – 4 * + 8 2 / +」

看到這裡，你可能會一臉懵逼，不過沒關係，我們先觀察一下後綴表達式有什麼特點。

我們日常的算術方法被稱作中綴表達式，因為運算符號夾在運算對象中間（1+1）；那麼顧名思義，後綴表達式就是運算符號在運算對象後面（1 1 +），而且沒有括弧。

通過後綴表達式進行計算可以說是嚴格從左向右進行的，所有的計算按運算符出現的順序，不會在中途停下，因此計算機運算會十分方便。

想要了解後綴表達式，首先我們要知道一種數據結構——棧，棧是僅允許在一端進行插入和刪除的線性表，可以把棧想像成一個坑，最後進去的才能最先出來。

準備工作都做好了，那麼我們就開始吧。

後綴表達式的計算

我們只需要一個棧，然後按照以下兩點，就能方便地計算後綴表達式了：

從左到右看後綴表達式，遇到數字就按順序放入棧中；

遇到符號就把棧最上兩個數字拉出來運算，遇到減號時，下面的數字是被減數，除號同理。

讓我們來試一試前面提到的算式

「7 6 3 – 4 * + 8 2 / +」

按照，我們向棧中依次填入7 6 3，遇到減號時，按照對6 3進行運算

接下來繼續重複就能得到結果啦

是不是很簡單呢？

這樣計算沒有括弧，也不用考慮運算順序，比正常的運算簡單多了~

不過問題也來了，後綴表達式計算起來的確簡單，但我們平時輸入給計算機的確實正常的中綴表達式，那麼計算機是如何將中綴表達式轉換為後綴表達式的呢？

中綴表達式轉為後綴表達式

同樣的，我們需要一個裝運算符號的棧，並且也有幾點規則：

從左到右看中綴表達式，遇到數字就輸出，作為後綴表達式的一部分；

遇到加減乘除號時，我們按照優先順序 乘除>加減 ，如果當前符號優先順序低於棧頂符號，那麼將棧中所有符號依次輸出，並且將當前符號放入棧中。

舉個例子，當棧中有乘號和加號時遇到減號，減優先順序低於棧頂的乘，按照，棧中乘號和加號依次輸出

遇到括弧時，如果是「 （ 」，那麼直接進棧，如果是「 ） 」，那麼依次輸出棧中符號，直到輸出與其匹配的「 （ 」。當然，後綴表達式是沒有括弧的，所以輸出的括弧就直接扔掉，下面再舉個例子

當沒有東西可以放入棧中時，依次輸出棧中符號，直到全部符號輸出。

看到這裡，大家可能會有點頭暈。不過沒關係，讓我們拿前面的例子試一試

「7+(6-3)×4+8÷2」

遇到「 ） 」，按進行輸出

遇到乘號之後的加號，按進行輸出

到這裡已經沒有東西能放進棧里了，按進行輸出

最終結果：「7 6 3 – 4 * + 8 2 / +」

完全正確。

至此，我們了解了什麼是後綴表達式，也學會了怎樣計算後綴表達式，以及如何將中綴表達式轉化為後綴表達式。不過計算速度和計算機比起來還是有很大差距的。

當然，計算機中運算的實現，可不是像我們一樣動動腦子就可以想出來的。想要了解更多的話，我們一起探索吧~

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！