给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-parentheses
思路：
遍历字符串
遇到左边括号，就入栈
遇到右边括号，就弹出栈顶
为空——》False
不为空——》弹出栈顶元素
栈顶元素和遇到的右边的括号匹配一下，看是否是相同类型
是不同类型就返回False
是相同类型就继续向下遍历
如果字符串全部匹配完了
栈为空 – True
占不为空 – False
创建栈
class Stack:
def __init__(self):
# 把列表的最后一个元素作为栈顶
self.__data = []
def push(self, item):
# 添加一个元素到栈顶
# append insert
self.__data.append(item)
def pop(self):
# 要判断栈是否为空
if self.is_empty():
raise ValueError('栈为空')
return self.__data.pop()
def top(self):
# 要判断栈是否为空
if self.is_empty():
raise ValueError('栈为空')
return self.__data[-1]
def is_empty(self):
return self.__data == []
def size(self):
return len(self.__data)
from stack01 import Stack
def func(string):
if len(string)%2:
return False
stack=Stack()
dic={
'(':')',
'[':']',
'{':'}'
}
for char in string:
#todo 判断遇到的是左括号还是右括号
if char in '([{':
stack.push(dic[char])
else:
if stack.is_empty() or stack.pop()!=char:
return False
return stack.is_empty()
if __name__ == '__main__':
print(func('{([])}'))
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/123181.html
