首页 > > 网络编程 > 其它 >

[LeetCode] 20. 有效的括号 (栈)

2019-02-20 00:46:05来源：博客园阅读 ()

思路：

首先用字典将三对括号存储，遍历字符串中每个字符，遇到左括号就入栈；遇到右括号就开始判断：是否与栈弹出的顶字符相同。

如果到最后栈被清空，说明全部匹配上了，为真。

class Solution(object):
    def isValid(self, s):
        stack=[]            #设置一个列表，把该列表当做栈来使用即可
        dic={'(':')','{':'}','[':']'}            #使用字典存储括号
        new_dic = {v : k for k, v in dic.items()}   #由于不能直接从value查找到对应的key,采用了字典反转
        for char in s:
            if char in dic.keys():          #左括号就入栈
                stack.append(char)
            elif char in dic.values():          #有右括号的话就进行比较
                if stack==[] or new_dic[char]!=stack.pop():  #分别对应'()]'以及'{]'两类情况
                    return False
            else:
                return False               #非字典中的输入直接输出错误
        return stack==[]            #如果栈最后是空的，那么符合要求输出true；如果不是，则输出false, 使用一个条件表达式
mm=Solution()
print(mm.isValid('(([]){})'))