■ 計算後序式之值:
一般的運算式有三種不同的表示法:
1. 中序式(inx):運算子(operator)寫在運算元(operand)中間,如 3+8
2. 前序式(prex):運算子寫在運算元之前,如 +38
3. 後序式(postx):運算子寫在運算元之後,如 38+
中序式是我們日常生活中用的表示法,必須考慮運算子的優先順序(如先乘除後加減)及
結合性(如+-﹡∕為由左而右計算的左結合,而指數為由右而左計算的右結合),而若
能夠將其改為後序式,則可以免除這些檢查。前序式又稱為波蘭式(Polish notation)而
後序式又稱為反波蘭式(reverse Polish notation),以下我們介紹後序式的計算程序,
我們以流程圖來表示:
註:波蘭式(Polish notation)是為了紀念波蘭的邏輯學家 Jan Lukasiewicz,而後來又
有人們注意到若將運算子置於運算元之後,則在計算上又具有更大的好處,這種稱為反
波蘭(reverse Polish notation)或後序式(postx notation)。
圖 1.堆疊用於計算後序式之值
註 : 運算單元表示運算子或運算元
否
否
*
4
2
1
4
op2=pop(=2)
op1=pop(=3)
push(3-2=1)
例 如 : 求 後 序
式 32-24 *
+ 之值
圖 2-3. 堆疊
於後序式之
應用
註 : 運算單元表示
運算子或運算元
彈出並存入 y
彈出 (pop) 並
存入否
否
push(op1 與
op2 之計算結
果 )
否 (x 是 運 算
子 )
結束結束
是
壓入 (push) X
X 是
運算元
(operand)?
印出 y
否
是
輸入結束 ?
否 (x 是 運 算
子 )
是
是
開始
輸入
運算單元 x
( 註 )
輸入結
束 ?
x 是
運算元
(operand)?
彈出並
存入 y
印出
y
結 束
結束
彈出 (pop) 並存入 op2
彈出 (pop) 並存入 op1
push(op1 與 op2 之計算結果 )
彈出 (pop) 並存入 op1
push(op1 與 op2 之計算結果 )
壓 入 (push)
x