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 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告