Scratch用堆栈算法解决括号匹配

堆栈类算法是计算机科学中非常重要的一类算法，它模拟了现实生活中的堆栈结构。栈的本义是储存货物或供旅客住宿的房屋，如货栈、客栈。计算机中“栈”的实体就是随机存储器（RAM），它存储数据的物理特性决定了堆栈类算法的基本形式“后进先出”。

堆栈：堆栈（Stack）是一种遵循后进先出（LIFO）原则的线性表数据结构。它只允许在表的一端进行插入和删除操作。举一个简单的例子。堆栈就像一个盒子，只能从盒子顶端放入或者取出物品。当你往堆栈里面放东西的时候，就像把书本往盒子里堆，每放一个新书本进去，就把它放在其他书本的上面。这个动作叫做“入栈”或者“推栈”。当你从堆栈里取出东西的时候，只能把盒子里最上面的那本书拿出来。这本最后放入的书现在第一个取出，这就是“后进先出”顺序。这个动作叫做“出栈”或者“弹栈”。堆栈就像一个自动排序的盒子，每次只允许在固定的一端进行添加和移除。

实际编程中，堆栈主要用于需要后进先出的场景，比如函数调用、递归算法、表达式语法解析等。利用堆栈的这种特性，可以解决很多看起来复杂的问题。所以堆栈作为一种数据结构，它简单但非常实用，值得我们好好理解和运用。 

接下实践一下“后进先出”，看一下这道简单的堆栈算法例题：

字符括号匹配游戏，规定用户必须输入大中小括号 ()、[]、{}的非空字符串，输入数量不做任何的限制，需要判断字符串是否合理有效，即一个左括号必须有一个相同类型的右括号进行闭合，且左右括号必须以正确的顺序闭合。

例如(()[])为有效的字符串，该字符串中第二个左括号和第三个右括号属于同类型已经闭合，第四个左括号和第五个右括号属于同类型可以闭合，第一个左括号和最后一个右括号属于同类型可以闭合，所以该字符串属于有效字符串。

(([)])为无效的字符串，因为第三个字符和第四个字符并不属于同类型无法闭合，所以该字符串属于无效字符串。

相信聪明的大家应该看懂规则了，那么接下来我们一起设计一个程序来完成这个目标，判断输入的字符串是否有效，如果字符串有效输出true，无效输出false。为了更加直观我们选择通过Scratch来编写，当然掌握算法的核心思路后你也可以移植到Python或其他编程语言。 

首先创建一些用于存储的变量：字符串个数、chart1、chart2、i、result、str。创建列表：栈队列。

运行程序后系统会弹出对话框请用户输入校验的字符括号串，用户输入字符串后将字符串保存在str变量中，同时获取字符串str的长度作为字符串的个数保留，并增加新的变量result对最后的结果进行统计（true代表成功，false代表失败）。

第一步，我们对字符串的个数进行判断，当字符串的个数为奇数的时候字符串肯定无法成功匹配，因为无论如何都会多出一个字符，用字符串个数除以2的余数等于1判断奇数。 

当字符串的个数为偶数的时候我们才可以进行下一步的判断，使用“栈队列”列表存储从用户输入字符串中提取的内容，重复循环检查字符串每一个字符的内容，当字符串的内容为左括号{、[、(时将字符内容插入到栈队列中。 

将字符插入队列中也是有讲究，需满足堆栈的规则“先进后出”，所以每当有新字符串插入的时候，我们需要将字符的内容插入到栈队列中的第一项，切记不可插在队列的尾部，不然不符合堆栈的要求。

当字符串的内容为右括号)、]、}的时候，我们则需要进行一个小小的转换，将右括号转化为左括号字符[{()}]，然后与队列中的第一项字符内容进行比对，判断是否相等，若相等即可删除队列中第一项内容，继续进行下一轮比较，若不相等则判定当前字符串不符合规则，result结果为false。 

通过使用堆栈的后进先出特性，可以很好地解决括号匹配问题。相信大家对堆栈算法有了更深的理解。后期我们会继续练习不同的堆栈算法，例如十进制转二进制等。

编辑｜张毅

审核｜吴新