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

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

链接: link

2. 思路分析

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

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

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

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

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

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

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

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

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

有三种情况：

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

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();
    }
};