leetcode-20. 有效的括号

栈+map

• 最后判断栈是否为空，如果不为空说明有单独的左括号

• 这里最后一定要看看栈是不是空的！！！

• 阿里面试，问“左括号必须以正确的顺序闭合”，这个条件去掉如何实现？

  需要用三个遍历记录三种左括号的数量。然后遍历字符串，遍历过程中，遇到右括号就把对应的左括号的数量减去。

class Solution {
public:
    bool isValid(string s) {
        // 双指针？错！
        // 栈 + map 
        if (s.size() % 2 == 1) 
            return false;

        stack<char> stk;
        unordered_map<char,char> umap;

        umap['['] = ']';
        umap['('] = ')';
        umap['{'] = '}';

        for (auto ch : s)
        {
            // 如果是左括号，入栈
            if (umap.count(ch))
            {
                stk.push(ch);
            }
            else
            {
                // 是右括号，
                if (stk.empty() || umap[stk.top()] != ch)
                {
                    return false;
                }
                else stk.pop();
            }
        }
        return stk.empty(); // 如果所有括号都有效匹配，栈应为空
    }
};