数据结构day05

一 栈的应用（括号匹配）

各位同学大家好，在之前的小结中，我们学习了栈和队列这两种数据结构，那从这个小节开始，我们要学习几种栈和队列的典型应用。这个小节中，我们来看一下括号匹配问题，这是栈这种数据结构的一个经典应用，那什么是括号匹配问题呢？这儿我在我的IDE上写了一小段代码，大家会发现我们写的代码当中这些小括号，大括号。还有中括号，它们都是成双成对出现的。所以你看这个地方，如果我们只有一个左括号而没有写与它对应的右括号，那这个IDE它是可以检测出来的。那如果我们加上与它对应的这个右括号啊IDE，就不会再报这个错误啊，对了，跨考的同学可能不知道这个名词是什么意思？IDE就是可视化的一个编程环境，反正就是大家用来写代码的那个东西好，那除了IDE之外，其实我们在对这段代码进行编译的时候。我们的编译器也会进行这样括号匹配的检查，因此这就是括号匹配的问题，我们必须保证我们在代码当中出现的这些括号。它们都是成双成对的，出现的除了左括号和右括号，在数量上必须匹配之外，那形状上是不是也必须匹配，比如我这儿写的是一个。左边的小括号，而这儿如果写一个呃，右边的中括号，那这样的代码也是有错误的

好，那我们先用手算的方式捋一下这个括号匹配的过程。那这几个括号是不是很简单，大家可以下意识的看出中间的这两个是一对，然后这两个是一对，这两个是一对，最外侧的两个是一对。那这是我们人脑的反应，

如果要用计算机来匹配这些括号的话，那只能一个一个依次扫描，对吧？也就是从左到右扫描，那不难发现这样的一个规律。越往后出现的左括号会越先被匹配，比如当我们从左往右扫描，扫描到这个右括号的时候。寻找与它匹配的左括号，应该是找到这个对吧？而这个左括号是最后出现的左括号，那扫描到再往后的一个右括号的时候。下一个被匹配的就是这个组合好，对吧？那算法的这种特性是不是就和栈的后进先出，其实是异曲同工的？我们是不是可以把这些左括号依次压入栈中，然后越往后压入栈的左括号越先被弹出栈，越先被匹配对吧？

来看另一个例子，从左往右依次扫描这些括号，那前面几个都是左括号，当扫描到第一个右括号的时候，是不是需要检查最近出现的一个左括号是哪一个？好发现是这个与它匹配，那就可以继续往后扫描后一个还是右括号，那是不是同样的，我们依然是往前找，最近出现的，并且没有被匹配的括号是这个好，

所以它们俩进行了配对。好，那再往后的过程都是类似的，总之每当出现一个右括号的时候，就需要消耗一个左括号，那这儿的消耗其实是不是就对应了出栈的一个操作？当我们遇到左括号的时候，就把它压入栈中，当我们遇到右括号的时候，就把栈顶的那个左括号给弹出，然后检查它们俩是否匹配。所以这就是用站来实现括号匹配的一个啊，大体的思路，

 

 

好，那如果用代码实现的话，就是这样的啊，这个函数里边传入了两个参数，这个参数是一个字符型的数组，里边就是存储了啊，什么左括号右括号这一串的字符。然后第二个参数lenth是表示我的这个数组，它的长度有多少好，另外我们这在这定义了一个顺序栈，这个栈里边它的数据元素是不是都是char类型的？然后还有一个站顶指针top考试的时候，大家是可以直接使用和数据结构相对应的，这些基本操作的，但是个人建议是要简要的说明一下这些接口分别是什么？就是用这种注释的方式呃，把各个接口进行一个说明，那这样的话，即便你的这个基本操作接口的名字，你命名的不太规范。但是只要你用中文把它注释讲明白了，那改卷老师肯定也不会算你的错，所以这是给大家的一个小建议。

好回到算法本身，首先是定义一个栈，并且初始化这个栈接下来用一个for循环从左往右啊，依次扫描这些字符。如果此次扫描到的字符，它是某一种左括号的话，那么我们就把这个字符给它push，给它压入栈中。而如果此次扫描到的是右括号，那么就首先需要检查啊栈是否为空。如果栈为空的话，那么就说明右括号单身匹配失败。而如果栈不空的话，我们就用呃pop，也就是出站的操作，把栈顶元素弹出，然后用top Elem这个变量来存储，接下来是不是要检查此次扫描到的这个右括号和当前栈点的左括号是否匹配？

如果此次扫描到的是右小括号，而栈顶的这个元素，它不是左小括号的话，那么就说明配对失败就可以直接return FALSE。算法就到此结束，那中括号和大括号也是一样的好，所以用这样的方式处理完所有的括号之后，是不是还需要检查？最后，这个栈是否为空？如果栈此时为空，那么就说明匹配成功。而如果最后这个栈是非空的，也就这个基本操作，它的返回值是FALSE的话。那就说明有单身的左括号，这样也是匹配失败

好，那这个地方我们是用顺序栈，也就是用一个静态数组来存储啊，栈里边的各个数据元素。之前我们说过，这种顺序栈的容量是固定不变的，所以如果给的这个括号串它很长很长的话，那么就有可能出现栈的溢出。因此，在实际开发的过程中，如果要实现这个代码的话，那其实可以用链栈的方式来实现。不过在考试中，我们用顺序战的这种方式实现，

相对来说会更简单一些。所以考试的时候用这种方式也是没问题的，好这个地方给大家留一个小小的练习，如果在这个代码当中并不是直接定义了一个栈。而是在里边定义了一个这样的数组，还有一个top指针，那么大家可以尝试着把这些基本操作给去掉。把相应的这些逻辑换成啊，对数组还有top指针直接的判断和操作好，这个一定要动手练习一下，特别是基础不太好的同学

 

好，那这一小节中我们学习了如何用栈来解决括号匹配的问题？概括来讲，算法思路就是啊，

从左到右依次扫描所有的字符，遇到左括号入栈，遇到右括号的话，弹出栈顶的左括号。检查是否匹配，如果所有的括号都检查完了，但是最终栈是非空的话，那么说明有左括号单身。然后如果扫描到右括号，但是此时栈已经空的话，那说明有右括号单身，而如果此时弹出的这个栈顶左括号和当前的右括号不匹配的话，也会出现匹配失败的情况，其实只要理解这个算法的大体思想之后。

啊，具体的代码应该是大家能够在考场上临场把它写出来的东西。