[数据结构与算法]【LeetCode】20. 有效的括号

解题思路：

? ? ? ? 由于括号只能是左边是左括号，且加右括号时，每加一个就在最右边减少一个左括号，这样才符合题意。那么可以用栈的特性来存储

遍历字符串，如果是左括号就放到一个列表中，就是我们的栈，这样如果遍历到右括号，就说明左括号已经遍历完了，

将新遍历的右括号与栈中最后一个元素对比（最里边的括号），判断是否相等（要转化一下），因为每个右括号对一个左括号，可以将右括号及对应的左括号存储在一个字典中，用右括号对应的左括号来比较。

每配对一个，就把栈中最后一个配对的括号删去。

如果还有其他情况都是不符合要求的，返回FALSE

最后栈中应该没有括号了，否则返回FALSE

解：

        match_dic = {')':'(', ']':'[', '}':'{'}     #右括号对应的左括号
        zuo_list = []       #存放左括号
        for ch in s:
            if ch in '([{':         #是左括号就入栈
                zuo_list.append(ch)
            elif ch in ')]}':       #是右括号就开始判断 
                if not zuo_list:    # 如果栈中无左括号，右括号就不能配对，错
                    return False
            #如果右括号与上一个括号配对，就删去左括号，继续遍历，直到无左括号
                if match_dic[ch] == zuo_list[-1]:   
                    zuo_list.pop(-1)
                else:               
                    return False
        # 正常闭合的情况下, 栈里面应该是空的
        if not zuo_list:
            return True
        else:
            return False