林厚從信息學奧賽課課通第7單元第8課棧的應用課件

1、第第7單元第單元第8課課 棧的應用棧的應用例例1:括號匹配括號匹配(check,1s,256MB)假設表達式中允許包含兩種括號：圓假設表達式中允許包含兩種括號：圓括號和方括號括號和方括號,其嵌套的順序隨意其嵌套的順序隨意,即即()或或()等為正確的格式等為正確的格式,(或或()或或()均為不正確的格式均為不正確的格式.本題的任務是檢測一本題的任務是檢測一個給定表達式中的括號是否正確匹配個給定表達式中的括號是否正確匹配.輸輸入一個只包含上述括號的字符串入一個只包含上述括號的字符串,判斷字判斷字符串中的括號是否匹配符串中的括號是否匹配,匹配就輸出匹配就輸出”O(jiān)K”,不匹配就輸出不匹配就輸出”Wro

2、ng”。輸入格式：輸入格式：一行字符，只含有圓括號和方括號，一行字符，只含有圓括號和方括號，個數小于個數小于255。輸出格式：輸出格式：匹配就輸出一行文本匹配就輸出一行文本“OK”，不匹配不匹配就輸出一行文本就輸出一行文本“Wrong”。輸入樣例：輸入樣例：（）輸出樣例：輸出樣例：Wrong問題分析一個匹配的括號序列，必定是左、右圓括號、一個匹配的括號序列，必定是左、右圓括號、方括號的數量一樣多。但是反過來，一樣多方括號的數量一樣多。但是反過來，一樣多不一定是匹配的。不一定是匹配的。定義一個字符型的棧來維護左括號，按順序定義一個字符型的棧來維護左括號，按順序處理括號序列：處理括號序列：1）遇到

3、左括號：將它入棧。）遇到左括號：將它入棧。2）遇到右括號：檢查棧頂元素與右括號是否）遇到右括號：檢查棧頂元素與右括號是否匹配。如果匹配，將棧頂左括號出棧；否則，匹配。如果匹配，將棧頂左括號出棧；否則，判斷出序列不匹配，結束。判斷出序列不匹配，結束。如果讀到了左括號，而棧為空，也不匹配。如果讀到了左括號，而棧為空，也不匹配。如果序列處理完畢，棧非空，也不匹配。如果序列處理完畢，棧非空，也不匹配。例例2：表達式求值：表達式求值(NOIP2013普及組復賽普及組復賽,expr,1s,256MB)題目描述題目描述給定一個只包含加法和乘法的算術表達式，請你編程計算表達式的值。給定一個只包含加法和乘法的算

4、術表達式，請你編程計算表達式的值。輸入格式：輸入格式：輸入僅有一行，為需要你計算的表達式，表達式中只包含數字、加法運算輸入僅有一行，為需要你計算的表達式，表達式中只包含數字、加法運算符符“+”和乘法運算符和乘法運算符“*”，且沒有括號，所有參與運算的數字均為，且沒有括號，所有參與運算的數字均為 0 到到 231-1 之間的整數。輸入數據保證這一行只有之間的整數。輸入數據保證這一行只有 0 9、+、*這這 12 種字符。種字符。輸出格式：輸出格式：輸出只有一行，包含一個整數，表示這個表達式的值。注意：當答案長度輸出只有一行，包含一個整數，表示這個表達式的值。注意：當答案長度多于多于 4 位時，請

5、只輸出最后位時，請只輸出最后 4 位，前導位，前導 0 不輸出。不輸出。輸入輸出樣例輸入輸出樣例輸入樣例輸入樣例1： 輸入樣例輸入樣例2： 輸入樣例輸入樣例3：1+1*3+4 1+1234567890*1 1+1000000003*1輸出樣例輸出樣例1： 輸出樣例輸出樣例2： 輸出樣例輸出樣例3：8 7891 4說明說明對于對于 30%的數據，的數據，0表達式中加法運算符和乘法運算符的總數表達式中加法運算符和乘法運算符的總數100；對于對于 80%的數據，的數據，0表達式中加法運算符和乘法運算符的總數表達式中加法運算符和乘法運算符的總數1000；對于對于 100%的數據，的數據，0表達式中加法

6、運算符和乘法運算符的總數表達式中加法運算符和乘法運算符的總數100000。問題分析問題分析 由于只有加號和乘號，只要從左往右掃一由于只有加號和乘號，只要從左往右掃一遍，如果遇到乘號直接計算（做乘法）；如遍，如果遇到乘號直接計算（做乘法）；如果遇到加號，若后面沒有符號或者后面一個果遇到加號，若后面沒有符號或者后面一個符號也是加號，則直接計算（做加法）；否符號也是加號，則直接計算（做加法）；否則，先把后面緊接著的連續(xù)的乘號算完，最則，先把后面緊接著的連續(xù)的乘號算完，最后再加。算法實現中，只要設置一個棧保存后再加。算法實現中，只要設置一個棧保存沒有立即進行的加法，掃描結束后再一起處沒有立即進行的加法

7、，掃描結束后再一起處理棧中的加法運算；同時，因為把一個數字理棧中的加法運算；同時，因為把一個數字串轉換成數也需要單獨編寫一個子程序；最串轉換成數也需要單獨編寫一個子程序；最后，還要注意實現過程中及時對后，還要注意實現過程中及時對10000取模。取模。例例3：圖的深度優(yōu)先遍歷：圖的深度優(yōu)先遍歷(graph_dfs,1s,256MB)問題描述：問題描述：讀入一個用鄰接矩陣存儲的無向圖，輸出它的深度優(yōu)先遍歷讀入一個用鄰接矩陣存儲的無向圖，輸出它的深度優(yōu)先遍歷序列。序列。輸入格式：輸入格式：第第1行，行，1個正整數個正整數n，表示圖中的頂點數，表示圖中的頂點數，2=n=100。接下來的接下來的n行是一

8、個行是一個n*n的鄰接矩陣，的鄰接矩陣，aij=1表示頂點表示頂點i和頂和頂點點j之間有直接邊相連，之間有直接邊相連，aij=0表示沒有直接邊相連。保證表示沒有直接邊相連。保證i=j時，時，aij=0，并且，并且aij=aji。輸出格式：輸出格式：輸出輸出1n的某一種排列，表示從頂點的某一種排列，表示從頂點1開始，對該圖進行深度開始，對該圖進行深度優(yōu)先遍歷得到的頂點序列，每兩個數之間用一個優(yōu)先遍歷得到的頂點序列，每兩個數之間用一個“-“分隔。分隔。輸入樣例：輸入樣例：80 1 1 0 0 0 0 01 0 0 1 1 0 0 01 0 0 0 0 0 1 10 1 0 0 0 1 0 00 1

9、 0 0 0 1 0 00 0 0 1 1 0 0 00 0 1 0 0 0 0 10 0 1 0 0 0 1 0輸出樣例：輸出樣例：12465378練習練習1：瓷磚：瓷磚(tile,1s,256MB)問題描述：問題描述：在一個在一個w*h的矩形廣場上的矩形廣場上,每一塊每一塊1*1的地面都鋪設了紅色或的地面都鋪設了紅色或黑色的瓷磚。小謝同學站在某一塊黑色的瓷磚上，他可以從黑色的瓷磚。小謝同學站在某一塊黑色的瓷磚上，他可以從此處出發(fā)，移動到上、下、左、右四個相鄰的且是黑色的瓷此處出發(fā)，移動到上、下、左、右四個相鄰的且是黑色的瓷磚上?，F在他想知道，通過重復上述移動所能經過的黑色瓷磚上?，F在他想知

10、道，通過重復上述移動所能經過的黑色瓷磚數。磚數。輸入格式：輸入格式：第第1行為兩個數行為兩個數h和和w,2=w,h=50，之間有一個空格隔開。以，之間有一個空格隔開。以下為一個下為一個w行行h列的二維字符矩陣，每個字符為列的二維字符矩陣，每個字符為“.”“#”“”，分別表示該位置為黑色的瓷磚、紅色的瓷磚，以及小分別表示該位置為黑色的瓷磚、紅色的瓷磚，以及小Y的初的初始位置。始位置。輸出格式：輸出格式：1行，一個整數，表示小行，一個整數，表示小Y從初始位置出發(fā)可以到達的瓷磚數。從初始位置出發(fā)可以到達的瓷磚數。輸入樣例： 輸出樣例： 11 9 59. # . . . . . . . . . # .

11、#. # .# . . . . .#. # .# . .#.#. # .# . #. # . . . . . . . #. #. . . . . . . . . . .練習練習2：最大黑區(qū)域：最大黑區(qū)域(area,1s,256MB)問題描述：問題描述：二值圖像是由黑白兩種像素組成的矩形點陣，二值圖像是由黑白兩種像素組成的矩形點陣，圖像識別的一個操作是求出圖像中最大黑區(qū)圖像識別的一個操作是求出圖像中最大黑區(qū)域的面積。請設計一個程序完成二值圖像的域的面積。請設計一個程序完成二值圖像的這個操作。黑區(qū)域由黑像素組成，一個黑區(qū)這個操作。黑區(qū)域由黑像素組成，一個黑區(qū)域中的每個像素至少與該區(qū)域中的另一個像域

12、中的每個像素至少與該區(qū)域中的另一個像素相鄰，規(guī)定一個像素僅與其上、下、左、素相鄰，規(guī)定一個像素僅與其上、下、左、右的像素相鄰。兩個不同的黑區(qū)域沒有相鄰右的像素相鄰。兩個不同的黑區(qū)域沒有相鄰的像素。一個黑區(qū)域的面積是其所包含的像的像素。一個黑區(qū)域的面積是其所包含的像素的個數。素的個數。輸入格式：輸入格式：第第1行兩個正整數行兩個正整數n和和m，1=n,m=100，分別，分別表示二值圖像的行數和列數。后面緊跟著表示二值圖像的行數和列數。后面緊跟著n行，行，每行含每行含m個整數個整數0或或1，其中第，其中第i行表示圖像的行表示圖像的第第i行的行的m個像素，個像素，0表示白像素，表示白像素，1表示黑像表示黑像素。同一行的相鄰兩個整數之間用一個空格素。同一行的相鄰兩個整數之間用一個空格隔開，兩個測試例之間用一個空行隔開，最隔開，兩個測試例之間用一個空行隔開，最后一個測試例之后隔一