林厚从信息学奥赛课课通第单元第课栈的应用课件.ppt

林厚从信息学奥林厚从信息学奥赛课课通第通第单元第元第课栈的的应用用课件件例1:括号匹配(check,1s,256MB)假设表达式中允许包含两种括号：圆括号和方括号,其嵌套的顺序随意,即()或()等为正确的格式,(或()或()均为不正确的格式.此题的任务是检测一个给定表达式中的括号是否正确匹配.输入一个只包含上述括号的字符串,判断字符串中的括号是否匹配,匹配就输出OK,不匹配就输出Wrong。输入格式：一行字符，只含有圆括号和方括号，个数小于255。输出格式：匹配就输出一行文本“OK，不匹配就输出一行文本“Wrong。输入样例：输出样例：Wrong问题分析一个匹配的括号序列，必定是左、右圆括号、方括号的数量一样多。但是反过来，一样多不一定是匹配的。定义一个字符型的栈来维护左括号，按顺序处理括号序列：1遇到左括号：将它入栈。2遇到右括号：检查栈顶元素与右括号是否匹配。假如匹配，将栈顶左括号出栈；否则，判断出序列不匹配，完毕。假如读到了左括号，而栈为空，也不匹配。假如序列处理完毕，栈非空，也不匹配。例2：表达式求值(NOIP普及组复赛,expr,1s,256MB)题目描绘给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。输入格式：输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+和乘法运算符“*，且没有括号，所有参与运算的数字均为 0 到 231-1 之间的整数。输入数据保证这一行只有 0 9、+、*这 12 种字符。输出格式：输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于 4 位时，请只输出最后 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表达式中加法运算符和乘法运算符的总数100000。问题分析 由于只有加号和乘号，只要从左往右扫一遍，假如遇到乘号直接计算做乘法；假如遇到加号，假设后面没有符号或者后面一个符号也是加号，则直接计算做加法；否则，先把后面紧接着的连续的乘号算完，最后再加。算法实现中，只要设置一个栈保存没有立即进展的加法，扫描完毕后再一起处理栈中的加法运算；同时，因为把一个数字串转换成数也需要单独编写一个子程序；最后，还要注意实现过程中及时对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*h的矩形广场上,每一块1*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行，每行含m个整数0或1，其中第i行表示图像的第i行的m个像素，0表示白像素，1表示黑像素。同一行的相邻两个整数之间用一个空格隔开，两个测试例之间用一个空行隔开，最后一个测试例之后隔一个空行，再接的一行含有两个整数0，标志输入的完毕。输出格式：1行，1个数，表示相应的图像中最大黑区域的面积。输入样例：输入样例：5 65 60 1 1 0 0 10 1 1 0 0 11 1 0 1 0 11 1 0 1 0 10 1 0 0 1 00 1 0 0 1 00 0 0 1 1 10 0 0 1 1 11 0 1 1 1 01 0 1 1 1 0输出样例：输出样例：7 7