Stack（堆疊） 堆疊的定義 簡單的應用範例 Stack ADT

Presentation on theme: "Stack（堆疊） 堆疊的定義 簡單的應用範例 Stack ADT"— Presentation transcript:

1 Stack（堆疊） 堆疊的定義 簡單的應用範例 Stack ADT
Stack ADT Implementation Based on Array 應用範例 A Mazing Problem Evaluation of Expression

2 Stack（堆疊） 前述的 list ADT 中，函數： ListInsert (NewItem, Position, Success)
ListDelete (Position, Success) 允許我們刪除有效位置 Position 上的資料。函數： ListRetrieve (Position, DataItem, Success) 允許我們取出有效位置 Position 上的資料。

3 換句話說，ADT list 的資料插入、刪除、和讀取「蠻自由的」 。如果我們取消這樣的自由而限制
只能在資料列固定的某一端插入、刪除、和讀取資料 的話，那麼我們就得到所謂的「堆疊（stack）」抽象資料型 態了。插入和刪除的那一端稱為 top。 66 Top （插入/刪除） 98 資料儲存區 21 18 26 45

4 Push operation 將資料加入堆疊的動作稱為 push（壓入）。 33 66 66 push 33 98 98 21 21 18
Top 66 Top 66 push 33 98 98 21 21 18 18 26 26 45 45

5 Pop operation 將資料從堆疊中刪除的動作稱為 pop（彈出）。 66 66 pop 98 98 21 21 18 18 26
Top 66 pop 98 98 Top 21 21 18 18 26 26 45 45

6 簡單的應用範例 Checking for Balanced Braces Requirements for balanced braces:
1. Each time you encounter a "}", it matches an already encountered "{". 2. When you reach the end of the string, you have matched each "{". abc{defg{ijk}{l{mn}}op}rr abc{def}}{ghij{kl}m

7 Stack as algorithm executes
Input string Stack as algorithm executes {a{b}c} 1. Push '{' 2. Push '{' 3. Pop 4. Pop Stack empty ==> balanced { { { {a{bc} 1. Push '{' 2. Push '{' 3. Pop Stack not empty ==> not balanced { { { {ab}c} 1. Push '{' 2. Pop Stack empty when last '}' ==> not balanced {

8 解法： while (not at the end of the string) { c = GetNextChar();
if ( c is a '{' ) Push '{' into the stack; else if ( c is a '}' ) { if (Stack is empty) return FALSE; Pop the stack; } return (stack is empty)? TRUE : FALSE;

9 另解 int counter = 0; while (not at the end of the string) {
c = GetNextChar(); if ( the next character is a '{' ) counter++; else if ( the next character is a '}' ) { counter--; if (counter < 0) return false; } return (counter == 0) ? true : false; abc{defg{ijk}{l{mn}}op}rr 1 2 3 abc{def}}{ghij{kl}m 1 -1

10 Recognizing palindromes
A string is called a palindrome if it is the same when reading forward and backward. 為了簡化問題起見，此處我們假設字串中含有單一個 字元 $，此字元區分字串為兩半部，如下圖所示： a b c d e f $ f e d c b a a b c d e f $ f e d k b a X YES NO

11 作法示範：假定字串為 a b c d e f $ f e d c b a
（一）將 $ 之前的字元依序 push 至堆疊中 a b c d e f $ f e d c b a top b a c d e f $ f e d c b a top

12 （二）碰到 $ 字元 ，捨棄 $ 字元後， 不再 push 其後的字 元至 stack 中，而進 入比較階段。 c b a
d e f $ f e d c b a top d c b a e f $ f e d c b a top e d c b a f $ f e d c b a top f e d c b a $ f e d c b a top f e d c b a f e d c b a top （二）碰到 $ 字元 ，捨棄 $ 字元後， 不再 push 其後的字 元至 stack 中，而進 入比較階段。

13 （三）在這個階段，我們比較 stack 中由上而下的字元和 $ 之後 剩餘的字元，如下所示：
f e d c b a f e d c b a top e d c b a e d c b a top d c b a d c b a top c b a c b a top b a b a top a top

14 則此字串是一個 palindrom，否則不是一個 palindrom。
（四）若比較之後，下列三個條件都成立： (1) 相比的字元一樣； (2) stack 變成空的； (3) 沒有剩餘的字元； 則此字串是一個 palindrom，否則不是一個 palindrom。 a top c b a k b a top c b a top c b a top YES NO NO NO

15 Stack ADT OBJECTS: a finite list with zero or more elements.
FUNCTIONS: Stack Create(max_stack_size) Boolean IsFull(stack, max_stack_size) Boolean IsEmpty(stack) boolean Push (stack, item) boolean Pop (stack) boolean GetTop (stack, top_item)

16 Stack 又稱為 LIFO ( Last In First Out ):
Create (S); Push (S, 1); Push (S, 2); Push (S, 3); Push (S, 4); 1 2 1 3 2 1 4 3 2 1 4 3 2 1 3 2 1 2 1 1 Pop(S);

17 Stack ADT Implementation Based on Array
靜宜大學資訊管理學系 資料結構講義 2018/11/28 Stack ADT Implementation Based on Array /** ** FILE : StackA.h **/ #define MAX_STACK 100 typedef int itemType; typedef enum {FALSE, TRUE} boolean; typedef struct { int Top; itemType Items[MAX_STACK]; } stack; 1 2 MAX_STACK - 1 k Top Items 蔡奇偉副教授 編製

18 boolean IsEmpty (stack *S) return (S->Top == -1) TRUE : FALSE;
/** ** FILE: StackA.c **/ #include “StackA.h” void Create (stack *S) { S->Top = -1; } boolean IsEmpty (stack *S) return (S->Top == -1) TRUE : FALSE; boolean IsFull (stack *S) return (S->Top >= MAX_STACK-1) TRUE : FALSE; 1 2 MAX_STACK - 1 k Top Items

19 boolean Push (stack *S, itemType NewItem) { if (IsFull(S))
return FALSE; S->Items[++S->Top] = NewItem; return TRUE; } MAX_STACK - 1 MAX_STACK - 1 Push(&S, 41) k+1 k+1 41 k+1 k 12 k 12 k Top Top 25 2 25 2 36 1 36 1 77 77 Items Items

20 boolean Pop (stack *S) { if (IsEmpty(S)) return FALSE; --S->Top;
return TRUE; } MAX_STACK - 1 MAX_STACK - 1 Pop(&S) k 41 k k 12 k-1 k-1 12 k-1 Top Top 25 2 25 2 36 1 36 1 77 77 Items Items

21 boolean GetTop (stack *S, itemType *TopItem) { if (IsEmpty(S))
return FALSE; *TopItem = S->Items[S->Top]; return TRUE; } MAX_STACK - 1 GetPop(&S, &TopItem) k 41 k+1 TopItem = 41 12 k Top 25 2 36 1 77 Items

22 A Mazing Problem 0 : open 1 : close N E W NE SE NW SW S

23 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 1 1 SE row col dir

24 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 2 2 NE 1 1 SE row col dir

25 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 1 3 E 2 2 NE 1 1 SE row col dir

26 靜宜大學資訊管理學系 資料結構講義 2018/11/28 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 1 4 E 1 3 E 2 2 NE 1 1 SE row col dir 蔡奇偉副教授 編製

27 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 1 5 SW 1 4 E 1 3 E 2 2 NE 1 1 SE row col dir

28 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 2 4 SE 1 5 SW 1 4 E 1 3 E 2 2 NE 1 1 SE row col dir

29 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 4 14 E 17 3 13 SE 16 3 12 E 15 1 4 E 3 1 3 E 2 2 2 NE 1 1 1 SE row col dir

30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 4 14 E 17 3 13 SE 16 3 12 E 15 1 4 E 3 1 3 E 2 2 2 E 1 1 1 SE Backtracking row col dir

31 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 3 13 SE 16 3 12 E 15 1 4 E 3 1 3 E 2 2 2 E 1 1 1 SE Backtracking row col dir

32 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 3 6 NE 9 3 5 E 8 1 4 E 3 1 3 E 2 2 2 E 1 1 1 SE Backtracking row col dir

33 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 3 6 E 9 3 5 E 8 1 4 E 3 1 3 E 2 2 2 E 1 1 1 SE row col dir

34 代數運算 Infix, Postfix, and Prefix Expressions
Evaluation of Postfix Expressions Conversion from Infix to Postfix Expressions

35 從小我們就熟悉計算式 a+b 表示 「a 加上 b」，也知道「先乘除
後加減」這個口訣，所以 a+b*c 這個式子表示「 a 加上 b 乘 c 的 結果」 而不是「a 加 b以後再乘以 c」— 後者必須用括號寫為 ( a+b )*c。像 a+b 這樣的計算式寫法，我們稱之為中置算式 （infix expression），所以這樣稱呼，原因是運算子 + 擺在兩個 運算元 a 和 b 之間。 有沒有必要一定這樣寫呢？譬如：我們是否 可以將同樣的算式寫成 前置算式（prefix expression） + a b 或者後置算式（postfix expression） a b + 呢？雖然這兩種寫法看起來「怪怪的」，但是在電腦科學的領域 中卻常常會看到類似的寫法。

36 前置算式 + a b 可以看成 + (a, b) 而解讀為：「+ 代表
解釋任何 C 的函數： func (p1, p2, ..., pk) 都是前置算式，其中 func 是運算子，而參數 p1, p2, ..., pk 為其運算元。許多的函數型的程式語言，如 ML 和 LISP 等等，就是採用這樣的「函數即為運算子」 的觀點，如此一來，使得該類型程式語言的語法變 得簡鍊許多。 堆疊可以用於很有效率地計算後置算式。這個技巧用 於一些程式語言，如 FORTH 和用於雷射印表機的 Postscript。

37

38 計算後置算式 2 * ( 3 + 4 ) = 14 2 * 3 + 4 = 10 A - ( B / C * D ) 2 3 4 + *
2 * = 10 A - ( B / C * D ) * * A B C / D * - 7 6 10 A - ( B / C * D ) B / C B / C * D 14

39 2 * ( ) = 14 * * 4 + * 3 2 * 7 2 7 14 * 2 + * 4 3 2 14

40 2 * = 10 * 6 10 2 3 * 4 + * 4 + 3 2 + 4 6 3 * 4 + 2 4 + 6 10

41 Algorithm for calculating postfix expression
Assumptions: The input string is a syntactically correct postfix expression. No unary operators are present. No exponentiation operators are present. Operands are single uppercase letters that represent integer values. A B C / D * - 【範例】

42 for (each character Ch in the string) {
if (Ch is an operator named Op) { /* evaluate and push the result */ Operand2 = top of the stack Pop the stack Operand1 = top of the stack Result = Operand1 Op Operand2 Push Result onto stack } else /* Ch is an operand */ Push Ch onto stack

43 中置算式轉換為後置算式 從前面的例子，我們知道利用堆疊可以很容易地計算 後置算式。因此，計算中置算式可以分為底下的兩個 步驟來執行：
1. 將中置算式轉換為後置算式 2. 用堆疊來計算所得的後置算式

44 【範例】 2 * = 10 * 6 10 2 * ( ) = 14 * 7 14

45 【範例】

46 Observations: 運算元的次序在中置算式和後置算式是完全相同的。 在中置算式中，如果運算元 X 在運算子 Op 之前， 那麼，在後置算式中，運算元 X 也會在運算子 Op 之前。 所有括號在轉換後均被消除。 運算子在後置算式中的出現順序是依照其在中置算式 的運算順序而定。

47 中置算式的運算法則 括號內算式先做 先乘除後加減 由左至右運算 A - ( B + C * D ) / E Þ ( A - ( ( B + ( C * D ) ) / E ) ) Þ ( A - ( ( B + C D *) / E ) ) Þ ( A - ( B C D * + / E ) ) Þ ( A - B C D * + E / ) Þ A B C D * + E / - A - B + C * D / E Þ ( ( A - B ) + ( ( C * D ) / E ) ) Þ ( A B - + ( ( C * D ) / E ) ) Þ ( A B - + ( C D * / E ) ) Þ ( A B - + C D * E / ) Þ A B - C D * E / +

48 中置算式轉換為後置算式的演算法 1. 當碰到運算元時，將其直接加附於輸出字串之後。 2. 當碰到左括號時，將其 push 至堆疊中。
3. 當碰到右括號時，將堆疊中的運算子 pop 出來並加 附於輸出字串之後直到碰到左括號為止，然後再將 此左括號 pop 掉。

49 4. 當碰到運算子時，若此時堆疊是空的，則直接將此
運算子加附於輸出字串之後；否則，將堆疊中運算 優先次序較高或相同的運算子 pop 出來並加附於輸 出字串之後直到下列條件成立為止 (i) 碰到左括號 (ii) 碰到優先次序較低的運算子 (iii) 堆疊變為空 然後將此輸入運算子 push 至堆疊中。 5. 當輸入字串全部處理完時，將堆疊中所剩餘的運算 子逐一地 pop 出來並加附於輸出字串之後直到堆疊 變為空為止。

50 Algorithm for ( each character ch in the infix expression ) {
switch ( Ch ) { case operand : PE = PE‧Ch; break; case ‘(‘ : S.Push ( Ch, Success); break; case ‘)’ : while ( top of S is not ‘(‘ ) { pop down to the matching open ( PE = PE‧( top of S ); S.Pop (Success ); } S.Pop ( Success ); remove the open ( break; case operator: PE‧Ch : PE concatenate Ch

51 while ( !S.StackIsEmpty () and ( top of S is not ‘(‘ ) and
靜宜大學資訊管理學系 資料結構講義 2018/11/28 while ( !S.StackIsEmpty () and ( top of S is not ‘(‘ ) and ( Precedence ( top of S ) >= Precedence ( Ch ) ) { PE = PE‧( top of S ); S.Pop (Success ); } S.Push ( Ch, Success); while ( !S.StackIsEmpty () ) { add the remaining operators in the stack 蔡奇偉副教授 編製

52 【範例】 A - ( B + C * D ) / E A B C D * + E / - A A 1 - - A 4 ( - ( A 2
Ch Stack S ( bottom to top) PE rule A A 1 A 4 ( - ( A 2 B - ( A B 1 + - ( + A B 4 C - ( + A B C 1 * - ( + * A B C 4 D - ( + * A B C D 1

53 ) - ( + A B C D * 3 - ( A B C D * + 3 - A B C D * + 3 / - / A B C D * + 4 E - / A B C D * + E 1 - A B C D * + E / 5 A B C D * + E / - 5