在 Python 中检查表达式中括号的匹配性，O(1) 空间 O(N^2) 时间复杂度

pythonserver side programmingprogramming更新于 2025/10/17 4:28:17

假设我们有一个字符串 str，其中包含这些括号 '(', ')', '{', '}', '[' 和 ']'，我们必须检查括号是否匹配。当左括号和右括号类型相同时，我们可以说括号是匹配的。括号以正确的顺序关闭。

因此，如果输入类似于 {([])}，则输出将为 True。

为了解决这个问题，我们将遵循以下步骤 −

cnt := 0
i := 0
j := -1
定义一个函数 resolve() 。这将采用 s、temp
cnt := cnt - 1
s := a new list from s
if 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
- while i < s 的大小非零，则执行
  - 如果 s[i] 与 '}' 相同，则
    - ans := resolve(s, '{')
    - 如果 ans 与 0 相同，则
      - 返回 False
    - 否则，当 s[i] 与 ')' 相同时，则
      - ans := resolve(s, '(')
      - 如果 ans 与 0 相同，则
        
        返回 False
    - 否则，当 s[i] 与 ']' 相同时，然后
      - ans := resolve(s, '[')
      - 如果 ans 与 0 相同，则
        
        返回 False
    - 否则，
      - j := i
      - i := i + 1
      - cnt := cnt + 1
- 如果 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("{([])}"))