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

第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+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的邻接矩阵，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开始，对该图进行深度优先遍历得到的顶点序列，每两个数之间用一个“-“分隔。 输入样例： 8 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 输出样例： 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的初始位置。 输出格式