栈的拿手好戏——括号匹配问题

1. 栈的应用——括号匹配问题

链接: link

2. 思路分析

这道题呢就非常适合用栈来搞：

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s。 定义一个栈，然后我们只需去遍历这个字符串： 如果遇到左括号，就给它入栈；如果遇到右括号，就取栈顶元素与之进行匹配（同时pop掉栈顶元素） 举个例子

遍历括号字符串，前三个都是左括号，入栈 再往后是一个右括号，那就pop掉栈顶的左括号与之匹配

匹配成功，继续往后遍历 再往后还是右括号，再去取栈顶元素匹配

匹配成功； 接着再往后是左括号，入栈

再往后，右括号，取栈顶匹配

匹配成功； 再往后，还是右括号，取栈顶元素匹配

匹配成功，至此字符串遍历结束，全部匹配成功。

但是，上面是匹配成功的情况，那哪些情况会匹配失败呢？

有三种情况：

1. 第一种就是在匹配的过程中左右括号不匹配
2. 右括号单身 即在匹配过程中，遇到右括号，此时去取栈顶元素，但是栈为空，没有左括号去跟它匹配
3. 左括号单身 遍历完字符串，都匹配成功，但是最后栈不为空，即还有剩余的单独的左括号，没有右括号来匹配

3. AC代码