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

本文主要是介绍栈的拿手好戏——括号匹配问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

1. 栈的应用——括号匹配问题
2. 思路分析
3. AC代码

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

链接: link
在这里插入图片描述

2. 思路分析

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

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

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

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

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

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

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

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

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

有三种情况：

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

3. AC代码

在这里插入图片描述

class Solution {
public:bool isValid(string& s) {stack<char> st;for(auto e:s){//如果是左括号就入栈if(e=='['||e=='{'||e=='(')st.push(e);//如果是右括号就获取栈顶元素与之匹配else if(e==']'||e==')'||e=='}'){//此时若栈为空，则没有左括号去匹配if(st.empty())return false;char top=st.top();st.pop();//左右括号不匹配if((e==']'&&top!='[')||(e==')'&&top!='(')||e=='}'&&top!='{')return false;}}//匹配完所有的右括号之后栈不为空return st.empty();}
};