有效的括号(力扣20)

这道题属于栈的经典应用，第一次写确实比较难想。很多这种对称匹配的问题用栈解决都比较方便，得益于栈后进先出的特点。下面我讲一下此题的一些注意点。

在遍历字符串的过程中，如果是左括号，我们需要往栈里存入数据，用于后续的匹配，但是我们存入的时候不要直接放左括号，我们存入该左括号对应的右括号，这样在遇到右括号进行匹配时，就只需要判断是否相等即可。如果直接存入左括号，遇到右括号进行匹配时需要写很多判断条件。因为括号的类型有三种，而我们并不知道栈里弹出的括号是属于哪一种，需要分类讨论，这样就太繁琐了。

另外还有一些注意点比较好理解，我直接写在代码注释中了。

代码如下：

class Solution {
public:
    bool isValid(string s) {
        //如果长度为奇数，一定不符合要求
        if(s.size() % 2 != 0) return false;
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里的右括号和遍历到的右括号不相等，说明左括号和右括号的类型不匹配。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有的左括号没有相应右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};