【leetcode】栈20，python用栈实现符号匹配问题

时间：2021-03-07 00:07:16 收藏：0 阅读：66

问题描述：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

问题解析：

优先级{ > [ > ( ；

利用栈先进后出的特点，将字符串逐一进栈，若栈为空则直接入栈；若非空，则即将入栈的元素与栈顶元素匹配，

若能配对，则栈顶元素出栈，继续遍历后面的元素

code：

 1 class Solution:
 2     def isValid(self, s: str) -> bool:
 3         self.stack = []
 4         for i in range(len(s)):
 5             if len(self.stack)==0:
 6                 self.stack.append(s[i])
 7             else:
 8                 if s[i]==‘)‘ and self.stack[-1]==‘(‘:
 9                     self.stack.pop()
10                     continue
11                 if s[i]==‘}‘ and self.stack[-1]==‘{‘:
12                     self.stack.pop()
13                     continue
14                 if s[i]==‘]‘ and self.stack[-1]==‘[‘:
15                     self.stack.pop()
16                     continue
17                 self.stack.append(s[i])
18         if len(self.stack) ==0:
19             return True
20         else:
21             return False

原文：https://www.cnblogs.com/zhixu/p/14491406.html