括号匹配检验

数据结构课上讲了栈可以用来实现括号匹配，我就来试试看。

括号匹配：检测字符串中的左括号和右括号是否匹配。

如“（akjkafa”，“）akdjka”，“（（akfdjakfjaklsf）”，“【akfja}”是不匹配的，“（abs(exp(x))）”是匹配的。

01

没有看教材以外任何资料的胡乱分析

括号匹配步骤：

遍历需要匹配的字符串。

如果当前字符是左括号，则将其压入栈内；

如果当前字符是右括号，则看看栈顶是否是左括号；（如果是括号匹配的字符串，那么在出现右括号字符的前一个括号字符必定是左括号）

如果是，弹出栈顶元素；

否则，返回匹配失败；

移到下一个位置检测字符；

如果检测完了，栈不为空，则返回匹配失败；（刚开始栈空，如果栈不为空，则说明栈内有未匹配的括号）

否则匹配成功。（说明字符串中没有括号或者括号全部匹配成功）

02

开始敲代码

和我上面的伪代码描述一致，就不解释了，懒得自己实现栈了，就直接用了STL（就是别人写好的一些数据类型的类，用了类模板实现不同的数据类型，比如我这里用了stack,也就是字符栈）里面的栈。

不过一执行发现停止运行了？？？

刚开始我的测试字符串是“a)”，可以先想想为啥这个会使得程序崩溃。答案在下面。

因为在检测到右括号的时候，栈里面没有元素我还让它检测栈顶元素，下溢了（也算下溢吧？如果不是请告诉我一下蟹蟹）

然后改成了这个。

其实貌似还有错，如果检测到右括号并且栈空，那个else下面那个弹出栈顶元素应该也会出错，然而并没有？？？有点奇怪，可能是这个栈的内部结构是如果空栈就不弹出吧？

还是再改改。

测试效果如下：（不要吐槽为啥我要声明那么多变量，因为懒，直接复制）

03

更多括号

上面的代码只支持英文圆括号，现在要增加更多的括号。

把条件增加成下面这样？

s[i]==')'||s[i]==']'||s[i]=='}'

感觉不太好，虽然简单易懂，但是感觉可扩展性不怎么好？

新想法：写一个函数检测是不是括号，还得知道是左括号还是右括号。你们先想想怎么弄。我的想法在下面。

函数返回值为int，如果为负就是左括号，为正就是右括号，为零就不是括号。（想想数轴是啥样的，左边负，右边正，中间零）

这样子如果有更多的括号，直接在对应的字符数组里面增加就好。不仅用正负区分了左右括号，还可以知道这是什么类型的括号。

（话说本来想着还有中文括号，但是写的时候想起来一个中文括号俩字符的诶……）

然而替换了一半之后发现……诶诶诶，

这句咋搞？？

emmmm对啦我上面那个函数是左右括号是一对相反数，那么——

结果不对！

没理由啊，我再测试一下。

你们再猜猜是啥原因？

对，圆括号在数组里面索引是0；

稍微修改一下：

识别括号函数没问题了，现在来修复括号匹配检测函数的bug。

我也不知道我改了什么之后，终于完成！前两个检测正确。

等会，t5[]="(([d)u]st)";括号数量对，但是也是不匹配的，却检测为匹配？

……

……

……

一个小时之后……

QAQ感觉要死了……找bug太痛苦了。关键是看电脑久了思维开始混乱，更加难找。

04

最终伪代码

括号匹配步骤：

遍历需要匹配的字符串。

如果当前字符是左括号，则将其压入栈内；

如果当前字符是右括号，则看看栈顶是否是左括号；（如果是括号匹配的字符串，那么在出现右括号字符的前一个括号字符必定是左括号）

如果栈空，返回匹配失败；

如果匹配成功，弹出栈顶元素（改着改着把这个语句忘了写了就导致了调试了很久）；

否则，返回匹配失败；

移到下一个位置检测字符；

如果检测完了，栈不为空，则返回匹配失败；（刚开始栈空，如果栈不为空，则说明栈内有未匹配的括号）

否则匹配成功。（说明字符串中没有括号或者括号全部匹配成功）

还是得在开始就把所有情况想到。