林厚从信息学奥赛课课通第7单元第8课 栈的应用课件.ppt
第第7单元第单元第8课课 栈的应用栈的应用例例1:括号匹配括号匹配(check,1s,256MB)假设表达式中允许包含两种括号：圆假设表达式中允许包含两种括号：圆括号和方括号括号和方括号,其嵌套的顺序随意其嵌套的顺序随意,即即()或或()等为正确的格式等为正确的格式,(或或()或或()均为不正确的格式均为不正确的格式.本题的任务是检测一本题的任务是检测一个给定表达式中的括号是否正确匹配个给定表达式中的括号是否正确匹配.输输入一个只包含上述括号的字符串入一个只包含上述括号的字符串,判断字判断字符串中的括号是否匹配符串中的括号是否匹配,匹配就输出匹配就输出”OK”,不匹配就输出不匹配就输出”Wrong”。输入格式：输入格式：一行字符，只含有圆括号和方括号，一行字符，只含有圆括号和方括号，个数小于个数小于255。输出格式：输出格式：匹配就输出一行文本匹配就输出一行文本“OK”，不匹配不匹配就输出一行文本就输出一行文本“Wrong”。输入样例：输入样例：（）输出样例：输出样例：Wrong问题分析一个匹配的括号序列，必定是左、右圆括号、一个匹配的括号序列，必定是左、右圆括号、方括号的数量一样多。但是反过来，一样多方括号的数量一样多。但是反过来，一样多不一定是匹配的。不一定是匹配的。定义一个字符型的栈来维护左括号，按顺序定义一个字符型的栈来维护左括号，按顺序处理括号序列：处理括号序列：1）遇到左括号：将它入栈。）遇到左括号：将它入栈。2）遇到右括号：检查栈顶元素与右括号是否）遇到右括号：检查栈顶元素与右括号是否匹配。如果匹配，将栈顶左括号出栈；否则，匹配。如果匹配，将栈顶左括号出栈；否则，判断出序列不匹配，结束。判断出序列不匹配，结束。如果读到了左括号，而栈为空，也不匹配。如果读到了左括号，而栈为空，也不匹配。如果序列处理完毕，栈非空，也不匹配。如果序列处理完毕，栈非空，也不匹配。例例2：表达式求值：表达式求值(NOIP2013普及组复赛普及组复赛,expr,1s,256MB)题目描述题目描述给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。输入格式：输入格式：输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符符“+”“+”和乘法运算符和乘法运算符“*”“*”，且没有括号，所有参与运算的数字均为，且没有括号，所有参与运算的数字均为 0 0 到到 231-1 231-1 之间的整数。输入数据保证这一行只有之间的整数。输入数据保证这一行只有 0 9 0 9、+、*这这 12 12 种字符。种字符。输出格式：输出格式：输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于多于 4 4 位时，请只输出最后位时，请只输出最后 4 4 位，前导位，前导 0 0 不输出。不输出。输入输出样例输入输出样例输入样例输入样例1 1：输入样例输入样例2 2：输入输入样例样例3 3：1+1*3+4 1+1234567890*1 1+1*3+4 1+1234567890*1 1+1000000003*11+1000000003*1输出样例输出样例1 1：输出样例输出样例2 2：输出输出样例样例3 3：8 7891 8 7891 4说明说明对于对于 30%30%的数据，的数据，00表达式中加法运算符和乘法运算符的总数表达式中加法运算符和乘法运算符的总数100100；对于对于 80%80%的数据，的数据，00表达式中加法运算符和乘法运算符的总数表达式中加法运算符和乘法运算符的总数10001000；对于对于 100%100%的数据，的数据，00表达式中加法运算符和乘法运算符的总数表达式中加法运算符和乘法运算符的总数100000100000。问题分析问题分析 由于只有加号和乘号，只要从左往右扫一由于只有加号和乘号，只要从左往右扫一遍，如果遇到乘号直接计算（做乘法）；如遍，如果遇到乘号直接计算（做乘法）；如果遇到加号，若后面没有符号或者后面一个果遇到加号，若后面没有符号或者后面一个符号也是加号，则直接计算（做加法）；否符号也是加号，则直接计算（做加法）；否则，先把后面紧接着的连续的乘号算完，最则，先把后面紧接着的连续的乘号算完，最后再加。算法实现中，只要设置一个栈保存后再加。算法实现中，只要设置一个栈保存没有立即进行的加法，扫描结束后再一起处没有立即进行的加法，扫描结束后再一起处理栈中的加法运算；同时，因为把一个数字理栈中的加法运算；同时，因为把一个数字串转换成数也需要单独编写一个子程序；最串转换成数也需要单独编写一个子程序；最后，还要注意实现过程中及时对后，还要注意实现过程中及时对10000取模。取模。例例3：图的深度优先遍历：图的深度优先遍历(graph_dfs,1s,256MB)问题描述：问题描述：读入一个用邻接矩阵存储的无向图，输出它的深度优先遍历读入一个用邻接矩阵存储的无向图，输出它的深度优先遍历序列。序列。输入格式：输入格式：第第1行，行，1个正整数个正整数n，表示图中的顶点数，表示图中的顶点数，2=n=100。接下来的接下来的n行是一个行是一个n*n的邻接矩阵，的邻接矩阵，aij=1表示顶点表示顶点i和顶和顶点点j之间有直接边相连，之间有直接边相连，aij=0表示没有直接边相连。保证表示没有直接边相连。保证i=j时，时，aij=0，并且，并且aij=aji。输出格式：输出格式：输出输出1n的某一种排列，表示从顶点的某一种排列，表示从顶点1开始，对该图进行深度开始，对该图进行深度优先遍历得到的顶点序列，每两个数之间用一个优先遍历得到的顶点序列，每两个数之间用一个“-“分隔。分隔。输入样例：输入样例：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 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*hw*h的矩形广场上的矩形广场上,每一块每一块1*11*1的地面都铺设了红色或的地面都铺设了红色或黑色的瓷砖。小谢同学站在某一块黑色的瓷砖上，他可以从黑色的瓷砖。小谢同学站在某一块黑色的瓷砖上，他可以从此处出发，移动到上、下、左、右四个相邻的且是黑色的瓷此处出发，移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在他想知道，通过重复上述移动所能经过的黑色瓷砖上。现在他想知道，通过重复上述移动所能经过的黑色瓷砖数。砖数。输入格式：输入格式：第第1行为两个数行为两个数h和和w,2=w,h=50，之间有一个空格隔开。以，之间有一个空格隔开。以下为一个下为一个w行行h列的二维字符矩阵，每个字符为列的二维字符矩阵，每个字符为“.”“#”“”，分别表示该位置为黑色的瓷砖、红色的瓷砖，以及小分别表示该位置为黑色的瓷砖、红色的瓷砖，以及小Y的初的初始位置。始位置。输出格式：输出格式：1行，一个整数，表示小行，一个整数，表示小Y从初始位置出发可以到达的瓷砖数。从初始位置出发可以到达的瓷砖数。输入样例：输出样例：11 9 59.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.练习练习2：最大黑区域：最大黑区域(area,1s,256MB)问题描述：问题描述：二值图像是由黑白两种像素组成的矩形点阵，二值图像是由黑白两种像素组成的矩形点阵，图像识别的一个操作是求出图像中最大黑区图像识别的一个操作是求出图像中最大黑区域的面积。请设计一个程序完成二值图像的域的面积。请设计一个程序完成二值图像的这个操作。黑区域由黑像素组成，一个黑区这个操作。黑区域由黑像素组成，一个黑区域中的每个像素至少与该区域中的另一个像域中的每个像素至少与该区域中的另一个像素相邻，规定一个像素仅与其上、下、左、素相邻，规定一个像素仅与其上、下、左、右的像素相邻。两个不同的黑区域没有相邻右的像素相邻。两个不同的黑区域没有相邻的像素。一个黑区域的面积是其所包含的像的像素。一个黑区域的面积是其所包含的像素的个数。素的个数。输入格式：输入格式：第第1行两个正整数行两个正整数n和和m，1=n,m=100，分别，分别表示二值图像的行数和列数。后面紧跟着表示二值图像的行数和列数。后面紧跟着n n行，行，每行含每行含m m个整数个整数0 0或或1 1，其中第，其中第i i行表示图像的行表示图像的第第i i行的行的m m个像素，个像素，0 0表示白像素，表示白像素，1 1表示黑像表示黑像素。同一行的相邻两个整数之间用一个空格素。同一行的相邻两个整数之间用一个空格隔开，两个测试例之间用一个空行隔开，最隔开，两个测试例之间用一个空行隔开，最后一个测试例之后隔一个空行，再接的一行后一个测试例之后隔一个空行，再接的一行含有两个整数含有两个整数0 0，标志输入的结束。，标志输入的结束。输出格式：输出格式：1行，行，1个数，表示相应的图像中最大黑区域个数，表示相应的图像中最大黑区域的面积。的面积。输入样例：输入样例：5 60 1 1 0 0 11 1 0 1 0 10 1 0 0 1 00 0 0 1 1 11 0 1 1 1 0输出样例：输出样例：7
