《林厚从信息学奥赛课课通第7单元第8课栈的应用课件》由会员分享，可在线阅读，更多相关《林厚从信息学奥赛课课通第7单元第8课栈的应用课件（13页珍藏版）》请在金锄头文库上搜索。
1、第7单元第8课栈的应用 例1 括号匹配 check 1s 256MB 假设表达式中允许包含两种括号 圆括号和方括号 其嵌套的顺序随意 即 或 等为正确的格式 或 或 均为不正确的格式 本题的任务是检测一个给定表达式中的括号是否正确匹配 输入一个只包含上述括号的字符串 判断字符串中的括号是否匹配 匹配就输出 OK 不匹配就输出 Wrong 输入格式 一行字符 只含有圆括号和方括号 个数小于255 输出格式 匹配就输出一行文本 OK 不匹配就输出一行文本 Wrong 输入样例 输出样例 Wrong 问题分析 一个匹配的括号序列 必定是左 右圆括号 方括号的数量一样多 但是反过来 一样多不一定是匹配
2、的 定义一个字符型的栈来维护左括号 按顺序处理括号序列 1 遇到左括号 将它入栈 2 遇到右括号 检查栈顶元素与右括号是否匹配 如果匹配 将栈顶左括号出栈 否则 判断出序列不匹配 结束 如果读到了左括号 而栈为空 也不匹配 如果序列处理完毕 栈非空 也不匹配 例2 表达式求值 NOIP2013普及组复赛 expr 1s 256MB 题目描述给定一个只包含加法和乘法的算术表达式 请你编程计算表达式的值 输入格式 输入仅有一行 为需要你计算的表达式 表达式中只包含数字 加法运算符 和乘法运算符 且没有括号 所有参与运算的数字均为0到2 31 1之间的整数 输入数据保证这一行只有0 9 这12种字符
3、 输出格式 输出只有一行 包含一个整数 表示这个表达式的值 注意 当答案长度多于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 问题分析 由于只有加号和乘号 只要从左往右扫一遍 如果遇到乘号直接计算 做乘法 如果遇到加号 若
4、后面没有符号或者后面一个符号也是加号 则直接计算 做加法 否则 先把后面紧接着的连续的乘号算完 最后再加 算法实现中 只要设置一个栈保存没有立即进行的加法 扫描结束后再一起处理栈中的加法运算 同时 因为把一个数字串转换成数也需要单独编写一个子程序 最后 还要注意实现过程中及时对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表示没有直
5、接边相连 保证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的地面都铺设了红色或黑色的瓷砖 小谢同学站在某一块黑色的瓷砖上 他可以从此处出发 移动到上 下 左 右四个相邻的且是黑色的瓷砖上 现在他想知道
6、通过重复上述移动所能经过的黑色瓷砖数 输入格式 第1行为两个数h和w 2 w h 50 之间有一个空格隔开 以下为一个w行h列的二维字符矩阵 每个字符为 分别表示该位置为黑色的瓷砖 红色的瓷砖 以及小Y的初始位置 输出格式 1行 一个整数 表示小Y从初始位置出发可以到达的瓷砖数 输入样例 输出样例 11959 练习2 最大黑区域 area 1s 256MB 问题描述 二值图像是由黑白两种像素组成的矩形点阵 图像识别的一个操作是求出图像中最大黑区域的面积 请设计一个程序完成二值图像的这个操作 黑区域由黑像素组成 一个黑区域中的每个像素至少与该区域中的另一个像素相邻 规定一个像素仅与其上 下 左 右的像素相邻 两个不同的黑区域没有相邻的像素 一个黑区域的面积是其所包含的像素的个数 输入格式 第1行两个正整数n和m 1 n m 100 分别表示二值图像的行数和列数 后面紧跟着n行 每行含m个整数0或1 其中第i行表示图像的第i行的m个像素 0表示白像素 1表示黑像素 同一行的相邻两个整数之间用一个空格隔开 两个测试例之间用一个空行隔开 最后一个测试例之后隔一个空行 再接的一行含有两个整数0 标志输入的结束 输出格式 1行 1个数 表示相应的图像中最大黑区域的面积 输入样例 56011001110101010010000111101110输出样例 7
