堆疊的應用—後序表示法之計算 - 筆記長也

堆疊的應用—後序表示法之計算

2018-02-10 12:56:11   資料結構

後序表示法之計算

關於何謂後序表示法,請看「堆疊的應用—中序表示轉後序表示」這一篇文章。

計算步驟

1.把此後序運算式以一字串表示

2.每次取一個字為一token,此token若為一運算元,則把該運算元push至堆疊。若此token為一運算子,則從堆疊pop出2個運算元做適當的運算

3.將步驟2的結果push到堆疊,重複執行步驟2

4.當運算式結束時(token為\0),則彈出堆疊中的資料,即為此後序運算式之結果。

實例

我們以中序表示式10+/-6*5,後序為10 8+6 5*-為例子,依照上面步驟計算:

Token 堆  疊 計  算 說  明
10 10   10為一運算元,故放入堆疊
8 8
10
  8為一運算元,也放入堆疊
+ 18 10+8 +為運算子,則pop出2個運算元做運算,並將結果18 push回堆疊當中
6 6
18
  6為運算元,放入堆疊當中
5 5
6
18
  5為運算元,放入堆疊當中
* 30
18
6*5 *為運算子,故pop出2個運算元做運算,並將結果30 push回堆疊當中
-   18-30 -為運算子,故pop出2個運算元做運算,其結果 -12 就是此後序之計算結果

關於最後的減法運算請注意,在加法與乘法順序相對不重要,其結果相同。但是遇到除法或減法就會影響。正確的計算順序應該是由下而上,而不是上而下,計算時請務必注意這一點!

 

關於作者


長也

資管菸酒生,嘗試成為網頁全端工程師(laravel / React),技能樹成長中,閒暇之餘就寫一些筆記。 喔對了,也愛追一些劇,例如火神跟遺物整理師,推推。最愛的樂團應該是告五人吧(?)