Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


Presentation on theme: "4-1 認識堆疊 4-2 堆疊的應用 4-3 算術運算式的求值 4-4 中序法轉換為前序法 4-5 前序與後序式轉換成中序式"— Presentation transcript:

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

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

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

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

5 範例程式:ch04_01.java

6 範例程式:ch04_02.java

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

8 範例程式:ch04_03.java

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

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

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

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

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

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

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

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

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

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

19 範例程式:ch04_04.java

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

21 模擬迷宮地圖

22 範例程式:ch04_05.java

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

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

25 範例程式:ch04_06.java

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

27 運算式種類 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><運算子>

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

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

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

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

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

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

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

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

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

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

38 範例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

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

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

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

42 範例 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

43 範例程式:ch04_07.java

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

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

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

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

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

49 範例 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)


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

Similar presentations


Ads by Google