数据结构
网络
关系型数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python中检查表达式中括号是否平衡（空间复杂度O(1)，时间复杂度O(N^2)）
假设我们有一个包含这些括号'('，')'，'{'，'}'，'['和']'的字符串str，我们需要检查括号是否平衡。当开括号和闭括号类型相同且括号按正确顺序闭合时，我们可以说括号是平衡的。
因此，如果输入类似于{([])}, 则输出为True。
为了解决这个问题，我们将遵循以下步骤：
- cnt := 0
- i := 0
- j := -1
- 定义一个函数solve()。这将接收s, temp作为参数
- cnt := cnt - 1
- s := 将s转换为新的列表
- 如果 j > -1 且 s[j] 与 temp 相同，则
- s[i] := '#'
- s[j] := '#'
- 当 j >= 0 且 s[j] 等于 '#' 时，循环执行：
- j := j - 1
- i := i + 1
- 返回 1
- 否则：
- 返回 0
- 在主方法中，执行以下操作：
- 如果 s 的大小为 0，则
- 返回 True
- 否则：
- ans := False
- 当 i < s 的大小且不为零时，循环执行：
- 如果 s[i] 等于 '}'，则
- ans := solve(s, '{')
- 如果 ans 等于 0，则
- 返回 False
- 否则，如果 s[i] 等于 ')'，则
- ans := solve(s, '(')
- 如果 ans 等于 0，则
- 返回 False
- 否则，如果 s[i] 等于 ']'，则
- ans := solve(s, '[')
- 如果 ans 等于 0，则
- 返回 False
- 否则：
- j := i
- i := i + 1
- cnt := cnt + 1
- 如果 s[i] 等于 '}'，则
- 如果 cnt 不等于 0，则
- 返回 False
- 返回 True
示例
让我们看看下面的实现，以便更好地理解：
cnt = 0
i = 0
j = -1
def solve(s, temp):
global i, j, cnt
cnt -= 1
s = list(s)
if j > -1 and s[j] == temp:
s[i] = '#'
s[j] = '#'
while j >= 0 and s[j] == '#':
j -= 1
i += 1
return 1
else:
return 0
def bracketOrderCheck(s):
global i, j, cnt
if len(s) == 0:
return True
else:
ans = False
while i < len(s):
if s[i] == '}':
ans = solve(s, '{')
if ans == 0:
return False
elif s[i] == ')':
ans = solve(s, '(')
if ans == 0:
return False
elif s[i] == ']':
ans = solve(s, '[')
if ans == 0:
return False
else:
j = i
i += 1
cnt += 1
if cnt != 0:
return False
return True
print(bracketOrderCheck("{([])}"))输入
"{(()[])}"输出
True
更新于: 2020-08-27
361 次浏览
广告