第四章：如何判定括号合法性

labuladong 如何判定括号合法性

解题思路：遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号（栈顶元素），看是否匹配。

20. 有效的括号

Krahets的极简思路及实现

栈 stack 为空： 此时 stack.pop() 操作会报错；因此，我们采用一个取巧方法，给 stack 赋初值 ? ，并在哈希表 dic 中建立 key: '?'，value:'? 的对应关系予以配合。

• 建立哈希表 dic 构建左右括号对应关系：key 左括号，value 右括号
• 如果 c 是左括号，则入栈 push
• 否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c不对应，则提前返回 False

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        dic={'(':')','{':'}','[':']','?':'?'}
        stack=['?']
        for c in s:
            if c in dic:
                stack.append(c)
            elif c==dic[stack[-1]]:
                stack.pop()
            else:
                return False # 和栈顶的左括号不匹配
        return len(stack)==1

class Solution {
public:
    bool isValid(string s) {
        map<char, char> m{{'(', ')'},
                          {'{', '}'},
                          {'[', ']'},
                          {'?', '?'}};
        stack<char> stk;
        stk.push('?');
        for (auto &c : s) {
            if (m.count(c)) stk.push(c); // 若是左括号，则入栈
            else if (c == m[stk.top()]) stk.pop(); // 若当前字符能和栈顶元素配对，则栈顶出栈
            else
                return false;// 既不是左括号，也不能互相抵消
        }
        return stk.size()==1; // 判断是否能全部抵消完，只剩下'?'
    }
};

• 如果不想用额外的?,则在弹出栈顶时添加栈不为空（!stk.empty()）的判断即可。最后判断栈是否为空：

class Solution(object):
    def isValid(self, s):
        dic={'(':')','{':'}','[':']'}
        stack=[]
        for c in s:
            if c in dic:
                stack.append(c)
            elif stack and c==dic[stack[-1]]:
                stack.pop()
            else:
                return False
        return len(stack)==0

class Solution {
public:
    bool isValid(string s) {
        map<char, char> m{{'(', ')'},
                          {'{', '}'},
                          {'[', ']'},
                          };
        stack<char> stk;
        for (auto &c : s) {
            if (m.count(c)) stk.push(c); // 若是左括号，则入栈
            else if (!stk.empty() && c == m[stk.top()]) stk.pop(); // 若当前字符能和栈顶元素配对，则栈顶出栈
            else
                return false;// 既不是左括号，也不能互相抵消
        }
        return stk.size()==0; // 判断是否能全部抵消完，只剩下'?'
    }
};