020 有效的括号

官方答案

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

思路：
首先判断字符串长度，如果是奇数肯定不匹配直接返回false；
利用unordered_map（见001）建立括号对；
用stack建立栈，需要注意的是这里的栈用char实现；
for语言遍历字符串中的字符，对于每个字符，当栈空或栈顶非对应括号则返回false；否则则压入栈（也就是说遇见所有左括号压栈，右括号判断）；
读取完字符串若栈空则返回true，否则返回false。

1.unordered_map count函数
https://vimsky.com/examples/usage/unordered_map-count-in-c.html
由于unordered_map不允许存储具有重复键的元素，因此count()函数本质上检查unordered_map中是否存在具有给定键的元素。

2.for语句遍历
https://www.cnblogs.com/132818Creator/p/11208541.html

自己写的答案，用的switch，需要注意的是遇见右括号时先要判断栈是否为空，否则程序运行错误。

class Solution {
public:
    bool isValid(string s) {
        if(s.size()%2==1)
            return false;
        stack<char> stk;
        for(char c:s){
            switch(c){
                case '(':
                    stk.push(c);
                    break;
                case '[':
                    stk.push(c);
                    break;
                case '{':
                    stk.push(c);
                    break;
                case ')':
                    if(stk.empty() ||  stk.top()!='(' )
                        return false;
                    else{
                        stk.pop();
                    }
                    break;
                case ']':
                    if(stk.empty() || stk.top()!='[')
                        return false;
                    else{
                        stk.pop();
                    }
                    break;
                case '}':
                    if(stk.empty() ||stk.top()!='{')
                        return false;
                    else{
                        stk.pop();
                    }
                    break;
            }
        }
        return stk.empty();

    }
};