1.堆疊應用:計算後序式(postfix)之四則運算
當我們在計算四則運算時,所用的式子稱為中序式(infix)。中序式,是因為運算符號
被夾在兩個運算數字的中間(如 1+2 或 3*4),但是當多筆數字及運算符號在同一個式
子時,便會有運算符號優先順序的問題。請看下面兩個算式:
1*2+3*4=14,答案是對的(依照先加減後乘除的順序計算)
1*2+3*4=24,若依照先加減後乘除的順序,則答案是錯的,但反之則是對的。
為了避免這種運算符號優先順序不同造成的困擾，當我們在計算時有時會加上括號
明確的表明運算順序。(例: 1*(2+3)*4 )
若利用程?茬B理四則運算的話,中序式雖然容易被人類判讀,但對程?茖市o會造
成上述的困擾與麻煩,而用後序?茬B理則不必考慮運算符號順序的問題。
後序式的規則是將兩運算數字排在前,運算符號排在最後。例:
前序式 => 後序式
1*2 12*
1*2+3*4 12*34*+
1*(2+3)*4 123+*4*
1+2*3+4 123*+4+
利用堆疊來計算四則運算:
(1)先將中序式:a*b+c*d 轉換成 後序式:ab*cd*+
(2)
由左至右掃描整個後序式,若遇到數字則放入堆疊;若遇到運算符號,則從堆疊內取
出兩個數字作運算,再將結果放入堆疊。重覆處理到式子結束。
(3)取出堆疊內的最後筆資料,即為結果。
處理流程:
postfix: stack: op: comment:
ab*cd*+ 原始算式
b*cd*+ a 放入a至堆疊
*cd*+ ab 放入b
cd*+ (a*b) * 運算*,取出b,a 並將(a*b)結果放入堆疊
d*+ (a*b)c 放入c
*+ (a*b)cd 放入d
+ (a*b)(c*d) * 運算*,取出d,c 並將(c*d)結果放入堆疊
(a*b)+(c*d) + 運算+,取出(c*d),(a*b)並將(a*b)+(c*d)放入堆疊
故以程式計算四則運算的流程如後:
中序式=>後序式=>運算處理
(中序式轉換為後序式的作法因為需要較多篇幅,在此先省略。)
2.佇列應用:走迷宮
走迷宮是一種考驗計憶力的遊戲。(not yet!)