iT邦幫忙

1

【小馬的資結演算法秘笈】(11) 四則運算與expression tree

嗨,大家好,今天來繼續談談資料結構的應用,
我們從最簡單的一個算式看起,
比如說「5-4*3+2」,
想要求這個算式的答案

一般來說,我們學過國小數學,
知道應該先乘除、後加減,
並不是由左到右先算5-4,
應該算「5-4*3+2 = 5-12+2 = -7+2 = -5」
對程式來說,要怎麼知道「4*3」應該先算呢?(更複雜一些,有時候算式還會有括號)

我們可以根據「5-4*3+2」這個算式,產生出一個expression tree出來,
https://ithelp.ithome.com.tw/upload/images/20200507/20117114SSP53Ihzpt.png

如果我們並不知道運算符號的優先順序,
那麼便很難正確計算出「5-4*3+2」的值,
可是若有了expression tree就超簡單,
計算順序一目瞭然,
從root開始做DFS,
如果是運算符號,
就看左、右兩個子樹是不是已經有數字了,
已經有數字就可以做運算,否則就繼續往下做

譬如說單純一點,我們算「5-4*3」,
https://ithelp.ithome.com.tw/upload/images/20200507/20117114PLYD6zMwk3.png

現在要計算 5-「一個運算樹」,
繼續往下做,看到乘號「*」,左右兩邊都是數字,
就可以算出「4*3=12」,
所以原來的算式就是計算「5-12 = -7」

逆波蘭表示法- 不需要括號的神奇表示法

如果我們把expression做後序遍歷(postorder)的話
https://ithelp.ithome.com.tw/upload/images/20200507/20117114SSP53Ihzpt.png

我們會得到5 4 3 * - 2 +
這種表達一個四則運算的方法稱為逆波蘭表示法

神奇的是,程式可以很方便計算出答案,
而不需要知道運算子的優先順序

計算方法:
首先準備一個stack,
從左到右掃一遍5 4 3 * - 2 +
如果看到數字就把數字丟進stack裡面,
如果碰到運算符號,
就把stack前兩個數字抓出來做運算再丟回stack裡面

譬如一開始stack裡面先依序放入數字「5,4,3」,
先著讀到乘號,就把前兩個數字「4,3」抓出來做乘法,
得到「4*3=12」
現在stack裡面有數字「5,12」,讀到減號
把「5,12」抓出來做減法得到-7,
看到數字「2」丟進stack裡面,
最後讀到加號,把「-7,2」抓出來做加法,即得到最後的答案-5

參考資料

  1. 四則運算 v.s. stack
  2. wiki- 逆波蘭表示法

尚未有邦友留言

立即登入留言