5.2《符号匹配问题》

5.2符号匹配问题 高中信息技术/教科版/选择性必修1 目录 1.情境引入、手动操作 2.分析与抽象 3.编程解决符号匹配 4.课堂小结 1.情境引入、手动操作 同学们，信息处理中最重要的是字符处理，其中对符号的配对检查也是重要的一项工作。有经验的编辑能很快发现符号配对上的问题，比如双引号是否配对等。 编辑文章时需要识别书名号、双引号等符号是否正确匹配;程序编译和运行时需进行语法检查，即检验各类符号是否正确匹配等。 由此可见，符号匹配检查是一项重要的工作。本节将围绕“符号匹配识别”项目展开学习，通过项目活动理解符号匹配的含义，认识栈在解决符号匹配问题中的重要作用，并掌握用栈解决符号匹配问题的方法。本节主要包含“体验手动符号匹配”和“编程实现符号匹配”两个任务。 任务一体验手动符号匹配 活动1手动检查符号是否匹配 《算法与数据结构》一书中提到:“我们定义“类class)去描述数据的外观 ( 状态) 和功能 (行为)。“类类似于抽象数据类型，“类’的用户只能看到数据项的状态和行为。数据项在面向对象的范式里被称为对象 (objects )。 小明审稿时边读边在稿子上做标注。 (1)读到第一个左书名号，在左书名号下方标注①。 (2) 读到右书名号，标注①，表示与左书名号匹配成功。 (3)读到左双引号，标注② (4)读到左单引号，标注③ (5) 读到与前一个左单引号对应的右单引号，便在右单引号下标注③。 任务一体验手动符号匹配 活动1手动检查符号是否匹配 标注完成后，小明进行匹配检查，发现标注的段落文本中的符号是匹配的，于是得出结论: 该段落符号匹配正确。 任务一体验手动符号匹配 活动1手动检查符号是否匹配 下面的内容是小明审稿过程中遇到的第2段话，完成标注后，结果如下: 小明进行符号匹配检查，发现标注的段落文本中2左双引号与右双引号是成对出现的，但是匹配失败，这是怎么回事? 配对的符号要完全嵌套，但不能交叉。在标注的段落中，符号②和符号③出现了交叉。 符号的使用需要遵循一定的平衡原则:： 1.每个左符号要恰好对应一个右符号; 2.每对左右符号要正确地嵌套，不能互相交错。如图所示，符号串中每个左符号都有对应的右符号，且左右符号配对次序正确，因此该符号串符号匹配正确。 符号匹配 任务一体验手动符号匹配 活动1手动检查符号是否匹配 通过活动1，我们可以总结出以下符号匹配失败的三种可能: (1)左右符号配对次序不正确; (2)右符号多于左符号; (3)左符号多于右符号.。 任务一体验手动符号匹配 活动2单人符号纸牌匹配游戏 午休间隙，为了活跃气氛，小明提议大家一起玩一个自制符号纸牌游戏。他拿起待审的书稿随机选取了一段文字，依次摘取段落中的符号(<(8))，并将这些符号依次画在了纸牌上，如图5.2.2所示。 图5.2.2符号纸牌的排列 将纸牌按从左到右的顺序叠成扇形拿在手中，第一张在最左边。从手中一张张依次取牌。具体操作如表5.2.1所示。请补全表中的操作步骤。 任务一体验手动符号匹配 活动2单人符号纸牌匹配游戏 任务一体验手动符号匹配 活动2单人符号纸牌匹配游戏 取完手中所有符号牌且桌面上左符号牌区域为空，说明符号串匹配成功。 任务一体验手动符号匹配 活动2单人符号纸牌匹配游戏 此轮游戏结束后，小明和出版社工作人员意犹未尽，又随机选取了如下三个符号串继续自制符号纸牌游戏，符号匹配结果会是怎样的呢? 不成功 不成功 不成功 任务一体验手动符号匹配 活动2单人符号纸牌匹配游戏 通过以上游戏，思考并总结出以下单人符号纸牌匹配游戏规则。 (1) 从左到右依次取符号牌直到结束。 (2) 取出的牌如果是 ，放在桌面上叠成一摞，后取出的牌放在上面。 (3) 取出的牌如果是 ，，则检查它是否与桌面上最上面的那张牌配对(即左右符号匹配)。若不是，则表明匹配失败，游戏结束。若是，将这对牌取走，继续游戏。如果此时桌面上没牌，表明匹配失败，游戏结束。 左符号 右符号 任务一体验手动符号匹配 活动2单人符号纸牌匹配游戏 4)当手中的牌已发完，但是桌面上还有牌，则匹配 游戏结束。 (5)当手中的牌已发完，并且桌面上也没有牌，则匹配 游戏结束。 失败 成功 通过以上游戏发现， 先放在桌面上的符号后匹配，后放在桌面上的符号先匹配，其特点就像栈一样，可以利用栈来实现符号匹配。 2.分析与抽象 任务二编程实现符号匹配 活动1建立数据结构 定义parChecker(symbolString)函数以进行符号匹配检测，参数symbolString为需要检验符号匹配的符号串，变量s为存放左符号牌的栈。请补全下面的代码。 01. from stack import Stack #导人stack类 02..checkstring="(<({})>)" #初始化需要检验的符号串 03.#定义符号匹配检验函数parChecker 04.def parChecker(symbolstring)： 05.s=Stack() #创建一个空栈s 3.编程解决符号匹配 任务二编程实现符号匹配 活动2设计算法 用栈解决符号匹配检测问题的算法描述如下(1) 从左到右依次读取存放各类符号的字符串。 (2)如果为左符号则进栈。 (3) 如果为右符号，则判断是否为空栈。如果是，此次匹配失败;否则，取栈顶符号并判断跟右符号是否同类。如果是，此次匹配成功，否则此次匹配失败。 (4)如果符号字符串结束且栈空了，则匹配成功，否则匹配失败。 任务二编程实现符号匹配 活动2设计算法 根据以上算法，请补全下面的代码。 06.for index in range(len(symbolString)): #依次扫描所有字符 07.symbol=symbolString[index] 08.if symbol in "<[({": #如果为左符号则进栈 09.s.push( ） 10.else: #如果为右符号则需要判断是否与栈顶左符号匹配 11.if s.isEmpty(): #如果栈为空则匹配失败 break #跳出循环 symbol 任务二编程实现符号匹配 活动2设计算法 根据以上算法，请补全下面的代码。 13.else: 14.top= . 15.#取栈顶左符号进行匹配判定 16.if not matches(top,symbol): 17. break 18.else: 19.#已读取的全部符号匹配成功且左符号栈为空则符号串匹配成功 20.if s.isEmpty(): 21.return True 22.return False s.pop( ) 任务二编程实现符号匹配 活动2设计算法 定义matches(open,close)函数来判定栈顶的左符号是否跟右符号属于同一类，参数open存放左符号串，参数close存放对应的右符号串。通过比较字符串的index 函数返回值来比较左符号和右符号是否属于同一类。请补全下面的代码。 23.#判定栈顶左符号是否与右符号匹配 24.def matches(open,close): 25.opens="<[([" 26.closers=">])}" 27.#字符串的index相同则左右符号匹配，否则不匹配 28.returnopens.index(open)== 29.print(parChecker(checkString)) 4.课堂小结 人类解决复杂的任务时，通常把任务分解成许多子任务。这样能自顶向下、逐步细化地思考问题，让思路清晰自然，也便于多人合作。在程序设计中也需要自顶向下、逐步细化地把复杂任务分解为子任务，并通常用函数来实现各个任务。 作业布置：请同学们认真完成教材中的拓展练习。 下节课见！ $$