题解 | #括号序列#

用哈希表和栈解决括号序列有效性的问题
先用哈希表来保存右括号和左括号的对应关系，设置一个栈保存左括号
对括号序列进行遍历，如果是左括号，则进栈，如果是右括号，判断是否栈空，栈空或栈顶元素不等于相应的右括号，则括号序列不合法，return false;
遍历完后，如果栈空，则有效，栈非空，说明栈中的左括号没有得到匹配的右括号，则括号序列无效。

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    bool isValid(string s) {
        // write code here
        // s: "{}(["
        unordered_map<char, char> charmap{{'}', '{'}, {']', '['}, {')', '('}};
        // 哈希表可以直接用大括号进行初始化
        stack<char> stk;
        for (int i = 0; i < s.size(); i++) {
            if (charmap.count(s[i])) {
                // 如果是右括号，则出栈，并判断是否是相应的左括号，不是则退出
                if (stk.empty() || charmap[s[i]] != stk.top()) {
                    return false;
                } else {
                    stk.pop();
                }
            } else {
                // 左括号，直接入栈
                stk.push(s[i]);
            }
        }

        return stk.empty();
    }
};