林厚从信息学奥赛课课通第7单元第8课 栈的应用课件VIP免费

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