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
    • 如果 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 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告