网络编程
位置：首页>> 网络编程>> Python编程>> python实现有效的括号判断实例代码

python实现有效的括号判断实例代码

作者：修炼之路　　发布时间：2023-11-24 14:40:34　

标签：python,判断,括号

题目描述

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

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

LeetCode原题地址：https://leetcode-cn.com/problems/valid-parentheses/

测试用例

示例 1

输入：s = “()”
输出：true

示例 2

输入：s = “()[]{}”
输出：true

示例 3

输入：s = “(]”
输出：false

示例 4

输入：s = “([)]”
输出：false

示例 5

输入：s = “{[]}”
输出：true

代码实现

实现这个算法我们可以利用栈的先进后出的特性，对于每个括号它需要找到与它匹配的括号。

我们先遍历字符串，将字符串的字符存入到栈中，当匹配到结束的括号时，如果此时栈不为空并且栈顶的字符与当前的括号相匹配时，我们将栈顶的字符进行出栈操作，否则直接返回False。如果最终栈为空表示每个括号都找到了匹配的结束括号，否则匹配失败。


class Solution:
   def isValid(self, s: str) -> bool:
       #如果字符串是奇数一定不满足条件
       if len(s) ％ 2 != 0:
           return False
       #定义一个括号字典
       bracket_dict = {")":"(","]":"[","}":"{"}
       #定义一个栈
       stack = []
       for c in s:
           #当匹配到括号的结束符时
           if c in bracket_dict:
               #栈不能为空,并且栈顶要与结束的括号匹配
               if len(stack) > 0 and bracket_dict[c] == stack[-1]:
                   stack.pop()
               else:
                   return False
           else:
               stack.append(c)
       return not stack

s = Solution()
print(s.isValid("()[]{}"))
print(s.isValid("([)]"))

参考：LeetCode详解

来源：https://blog.csdn.net/sinat_29957455/article/details/113193617

0
投稿

猜你喜欢

手机版 网络编程 asp之家 www.aspxhome.com