008-力扣刷题20--有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()" 输出: true 示例 2:

输入: "()[]{}" 输出: true 示例 3:

输入: "(]" 输出: false 示例 4:

输入: "([)]" 输出: false 示例 5:

输入: "{[]}" 输出: true

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
    #还是使用字典数据结构
        stack=[]  #这个stack存储的是左边的括号
        lookup  = {"(":")","[":"]","{":"}"}  #首先定义一个字典的映射,将各种括号进行对应
        for parenthese in s: #对s进行遍历
            if parenthese in lookup: #如果说输入的括号是左括号,那么在字典中
                stack.append(parenthese) #就将左括号添加到stack这个列表中去
            elif len(stack)==0 or lookup[stack.pop()] != parenthese:
                #or 后面的意思很好理解当我们取出的parenthes是右括号时,那么它的前一个元素对应的一定是对应的左括号,否则就是错的  比如(],()(}都是不能对应的,这个地方仔细研究就懂了,只要是第一个出现的右括号前面上一个 出现的一定得是对应的左括号不然就是错的.  
                # or 后面的是这种情况 ) 只出现了一个) 或者第一次出现的就是右括号,那么stack中是空的,也认为是错的
                return False

        return len(stack) == 0   #这一种情况考虑的是 只出现了一个 [  那么此时stack中只会存储一个 [  就完事了,但是这种情况是错的.
    #为什么这个最后判断使用的stack的长度呢,这是因为我们在elif判断左右括号的时候是用了弹出元素的方法,最后左括号和右括号数量相等的情况下,stack中的元素最终会全部被弹出
    #就会返回True
     #比如 () []
    # stack=['(' ]
    #stack=[] pop操作
    #stack=[[]
    #stack=[] pop操作