4-1 認識堆疊 4-2 堆疊的應用 4-3 算術運算式的求值 4-4 中序法轉換為前序法 4-5 前序與後序式轉換成中序式 第四章 堆疊 4-1 認識堆疊 4-2 堆疊的應用 4-3 算術運算式的求值 4-4 中序法轉換為前序法 4-5 前序與後序式轉換成中序式

認識堆疊 談到所謂後進先出(Last In，Frist Out)的觀念，其實就如同自助餐中餐盤由桌面往上一個一個疊放，且取用時由最上面先拿，這就是一種典型堆疊概念的應用：

堆疊的工作運算 下列特性： 五種工作定義： 只能從堆疊的頂端存取資料。 資料的存取符合「後進先出」(LIFO,Last In First Out)的原則。 CREATE 建立一個空堆疊。 PUSH 存放頂端資料，並傳回新堆疊。 POP 刪除頂端資料，並傳回新堆疊。 EMPTY 判斷堆疊是否為空堆疊，是則傳回true，不是則傳回false。 FULL 判斷堆疊是否已滿，是則傳回true，不是則傳回false。

堆疊的陣列實作 堆疊本身可以使用靜態陣列結構或動態鍵結串列結構來實作，只要維持堆疊後進先出與從頂端讀取資料的兩個基本原則即可。

範例程式：ch04_01.java

範例程式：ch04_02.java

堆疊的串列實作 以陣列結構來製作堆疊的好處是製作與設計的演算法都相當簡單，但因為如果堆疊本身是變動的話，陣列大小並無法事先規劃宣告。 鍵結串列來製作堆疊的優點是隨時可以動態改變串列長度，不過缺點是設計時，演算法較為複雜。

範例程式：ch04_03.java

堆疊的應用 1.二元樹及森林的走訪運算，例如中序追蹤(Inorder)、前序追蹤 (Preorder)等。 2.電腦中央處理單元(CPU)的中斷處理(Interrupt Handling)。 3.圖形的深度優先(DFS)追蹤法。 4.某些所謂堆疊計算機(Stack Computer)，是一種採用空位址(zero-address)指令。 5. 迴程式的呼叫及返回：在每次遞迴之前，須先將下一個指令的位址、及變數的值保存到堆疊中。

6. 算術式的轉換和求值，例如中序法轉換成後序法。 7. 呼叫副程式及返回處理，例如要執行呼叫的副程式前，必須先將返回位置儲存到堆疊中，然後才執行呼叫副程式的動作。 8. 編譯錯誤處理(Compiler Syntax Processing)：例如當編輯程式發生錯誤或警告訊息時，會將所在的位址推入堆疊中，才顯示出錯誤相關的訊息對照表。

範例 4.2.1 考慮如下所示的鐵路交換網路 在圖右邊為編號1,2,3,…,n的火車廂。每一車廂被拖入堆疊，並可以在任何時候將它拖出。

如n=3，我們可以拖入1，拖入2，拖入3然後再將車廂拖出，此時可產生新的車廂順序3,2,1。請問 當n=6時，325641這樣的排列是否可能發生？或者154236？或者154623？又當n=5時，32154這樣的排列是否可能發生？ 找出一個公式Sn，當有n節車廂時，共有幾種排方式？

河內塔問題 西元1883年法國數學家Lucas所提出流傳在印度的河內塔(Tower of Hanoil)遊戲，是典型使用遞迴式與堆疊觀念來解決的範例。 河內塔問題可以這樣形容： 有三根木樁，第一根上有n個盤子，最底層的盤子最大，依序最上層的盤子會愈來愈小。河內塔問題就是將所有的盤子從第一根木樁，並以第二根木樁當橋樑，全部搬到第三根木樁，如圖所示：

(當然是直接把盤子從1號木樁移動到3號木樁。) 不過在搬動時，尚須遵守以下遊戲規則： 1.每次只能從最上面移動一個盤子。 2.任何盤子可以從任何木樁搬到其他木樁。 3.直徑較小的盤子永遠必須放在直徑較大的盤子之上。 當有1個盤子時： (當然是直接把盤子從1號木樁移動到3號木樁。)

當有2個盤子時： 步驟1：從1到2 步驟2：1→3

步驟3：2→3 完成 結論：移動了22-1=3次，盤子移動的次序為1,2,1(此處為盤子次序) 步驟為：1→2，1→3，2→3(此處為木樁次序)

由以上得知，依此類推n=5、6、7…，我們得到一個結論：當有n 個盤子時：

這時假設an為移動n個盤子所需要的最少移動次數，且a1=1 從上圖中，可得知如下結果： an =2an-1+1 　 =2(an-2+1) 　 =4an-2+2+1 　 =4(2an-3+1)+2+1 　 =8an-3+4+2+1 　 =8(2an-4+1)+4+2+1 　 =16an-4+8+4+2+1 　 =．．． 　 =2n-1a1+

範例程式：ch04_04.java

迷宮問題 在迷宮中行進，必須遵守以下三個原則： 先來了解如何在電腦中表現一個模擬迷宮的方式。這時可以利用二維陣列MAZE[row][col]，並符合以下規則： 一次只能走一格。 遇到牆無法往前走時，則退回一步找找看是否有其他的路可以走。 走過的路不會再走第二次。 MAZE[i][j]=1表示[i][j]處有牆，無法通過 =0表示[i][j]處無牆，可通行 MAZE[1][1]是入口，MAZE[m][n]是出口

模擬迷宮地圖

範例程式：ch04_05.java

八皇后問題 在西洋棋中的皇后可以在沒有限定一步走幾格的前題下，對棋盤中的其它棋子直吃、橫吃及對角斜吃(左斜吃或右斜吃皆可) 。 只要後放入的新皇后，放入前必須考慮所放位置直線方向、橫線方向或對角線方向是否已被放置舊皇后，否則就會被先放入的舊皇后吃掉。 可以將其應用在4*4的棋盤，就稱為4-皇后問題；應用在8*8的棋盤，就稱為8-皇后問題。 應用在N*N的棋盤，就稱為N-皇后問題。

4-皇后及8-皇后 底下分別是4-皇后及8-皇后在堆疊存放的內容及對應棋盤的其中一組解。

範例程式：ch04_06.java

算術運算式求值 一個算術運算式是由運算子(+、-、*、/..)與運算元(1、2、3…及間隔符號) 所組成。下式為一個典型算術運算式： 以上運算式表示法，稱為中序表示法(Infix Notation)，這也是一般人所習慣的寫法。 運算過程需注意括號內的運算式先行處理，且需注意運算子優先權。 (6*2+5*9)/3

運算式種類 1.中序法(Infix) 2.前序法(Prefix) 3.後序法(Postfix) 例如2+3、3*5、8-2等等都是中序表示法。 2.前序法(Prefix) 例如中序運算式2+3，前序運算式的表示法則為+23，而2*3+4*5則為+*23*45 3.後序法(Postfix) 例如後序運算式2+3，後序運算式的表示法為23+，而2*3+4*5的後序表示法為+*23*45 <運算元1><運算子><運算元2> <運算子><運算元1><運算元2> <運算元1><運算元2><運算子>

中序表示法求值 由中序表示法來求值，請依照以下五個步驟： 1.建立兩個堆疊，分別存放運算子及運算元。 2.讀取運算子時，必須先比較堆疊內的運算子優先權，若堆疊內運算子的優先權較高，則先計算堆疊內運算子的值。 3.計算時，取出一個運算子及兩個運算元進行運算，運算結果直接存回運算元堆疊中，當成一個獨立的運算元。 4.當運算式處理完畢後，一步一步清除運算子堆疊，直到堆疊空了為止。 5.取出運算元堆疊中的值就是計算結果。

前序表示法求值 好處是不需考慮括號及優先權問題，所以可以直接使用一個堆疊來處理運算式即可，不需把運算元及運算子分開處理。 接著來實作前序運算式+*23*45如何使用堆疊來運算的步驟：

從堆疊中取出元素，遇到運算子則進行運算，結果存回運算元堆疊： 步驟1 從堆疊中取出元素： 步驟2 從堆疊中取出元素，遇到運算子則進行運算，結果存回運算元堆疊：

從堆疊中取出元素，遇到運算子則從運算元取出兩個運算元進行運算，運算結果存回運算元堆疊： 步驟3 從堆疊中取出元素： 步驟4 從堆疊中取出元素，遇到運算子則從運算元取出兩個運算元進行運算，運算結果存回運算元堆疊： 完成 把堆疊中最後一個運算子取出，從運算元取出兩個運算元進行運算，運算結果存回運算元堆疊。

後序表示法的求值 具有和前序運算式類似的好處，沒有優先權的問題，而且後序運算式可以直接在電腦上進行運算，而不需先全數放入堆疊後再讀回運算。 它使用迴圈直接讀取運算式，如果遇到運算子就從堆疊中取出運算元進行運算。

我們繼續來實作後序表示法23*45*+的求值運算： 放入2及3後取回*，這時取回堆疊內兩個運算元進行運算，完畢後放回堆疊中。 步驟1 直接讀取運算式，遇到運算子則進行運算：

接著放入4及5遇到運算子*，取回兩個運算元進行運算，運算完後放回堆疊中： 步驟2 接著放入4及5遇到運算子*，取回兩個運算元進行運算，運算完後放回堆疊中： 完成 最後取回運算子，重複上述步驟。 6+20=26

中序法轉換為前序法 二元樹法 括號法 堆疊法

二元樹法 二元樹法就是把中序運算式依優先權的順序，建成一棵二元樹。 之後再依樹狀結構的特性進行前、中、後序的走訪，即可得到前中後序運算式。 這個方法是使用樹狀結構進行走訪來求得前序及後序運算式。

括號法 先用括號把中序運算式的優先順序分出來，再進行運算子的移動，最後把括號拿掉就可完成中序轉後序或中序轉前序了。 中序轉前序 中序轉後序 將中序運算式根據順序完全括號起來。 移動所有運算子來取代所有的左括號，並以最近者為原則 將所有右括號去掉 將中序運算式根據順序完全括號起來。 移動所有運算子來取代所有的右括號，並以最近者為原則 將所有左括號去掉

範例4.4.1 範例 4.4.2 範例 4.4.3 請將6+2*9/3+4*2-8用括號法轉成前序法或後序法。 求A-B*(C+D)/E的前序式和後序式。 範例 4.4.3 將下列中序算術式轉換為前序與後序算術式。 A/B↑C+D*E-A*C (A+B)*D+E/(F+A*D)+C A↑B↑C A↑-B+C

範例 4.4.4 將下列中序算術式轉換為前序與後序算術式 (A/B*C-D)+E/F/(G+H) (A+B)*C-(D-E)*(F+G)

堆疊法 利用堆疊將中序法轉換成前序，其ISP(In Stack Priority)是「堆疊內優先權」的意思，ICP(In Coming Priority)是「輸入優先權」的意思。運作步驟如下： 中序轉前序 由右至左讀進中序運算式的每個字元。 如果輸入為運算元則直接輸出。  ')'在堆疊中的優先權最小，但在堆疊外卻是優先權最大。 如果遇到'('，則彈出堆疊內的運算子，直到彈出到一個')'為止。 如果ISP>ICP則將堆疊的運算子彈出，否則就加入到堆疊內。

中序轉後序 由左至右讀每次讀入一個字元。 輸入為運算元則直接輸出。 如果ISP>=ICP，則將堆疊內的運算子直接彈出，否則就加入到堆疊內。  '('在堆疊中的優先權最小，不過如果在堆疊外，它的優先權最大。 如果遇到')'，則直接彈出堆疊內的運算子，一直到彈出一個'('為止。

範例 4.4.5 範例 4.4.6 範例 4.4.7 請將中序式(A+B)*D+E/(F+A*D)+C以堆疊法轉換成前序式與後序式。 求下列中序式(A+B)*D-E/(F+C)+G的後序式。 範例 4.4.7 將下面的中序法轉成前序與後序算術式：(以下皆用堆疊法)A/B↑C+D*E-A*C

範例程式：ch04_07.java

前序與後序式轉換成中序式 括號法 堆疊法

括號法 以括號法來求得運算式(前序式與後序式)的反轉為中序式的作法，若為前序必須以「運算子+運算元」的方式括號，若為後序必須以「運算元+運算子」的方式括號。 另外還必須遵守以下原則： 前序轉中序： 依次將每個運算子，以最近為原則取代後方的右括號，最後再去掉所有左括號。 後序轉中序： 依次將每個運算子，以最近為原則取代前方的左括號，最後再去掉所有右括號。

範例 4.5.1 下列哪個算術表示法不符合前表示法的語法規則？ (A)+++ab*cde(B)-+ab+cd*e(C)+-**abcde(D)+a*-+bcde

堆疊法 以堆疊法來求得運算式(前序式與後序式)的反轉為中序式的作法必須遵照下列規則： 1.若要轉換為前序，由右至左讀進運算式的每個字元；若是要轉換成後序，則讀取方向改成由左至右。 2.辨別讀入字元，若為運算元則放入堆疊中。 3.辨別讀入字元，若為運算子則從堆疊中取出兩個字元，結合成一個基本的中序運算式(<運算元><運算子><運算元>)後，再把結果放入堆疊。

在轉換過程中，前序和後序的結合方式是不同的，前序是<運算元2><運算子><運算元1>而後序是<運算元1><運算子><運算元2>，如下圖所示： 運算子 OP2 OP1 前序轉中序：<OP2><運算子><OP1> 後序轉中序：<OP1><運算子><OP2>

範例 4.5.2 範例 4.5.3 請以堆疊法將下列兩種表示法轉為中法。 -+/A**BC*DE*AC AB*CD+-A/ 請計算下列後序式abc-d+/ea-*c*的值？(a=2,b=3,c=4,d=5,e=6)