檢查 Python 中兩個字串的連線是否平衡

假設我們有兩個括號序列 s 和 t，它們只包含字元 '(' 和 ')'。我們需要檢查 s 和 t 的連線字串是否平衡。連線可以透過 s | t 或 t | s 完成。

因此，如果輸入類似於 s = "()()))"，t = "()(()("，則輸出為 True，因為如果我們連線 t | s，則得到 "()(()(()()))"，它是平衡的。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式 `is_balanced_parenthesis()`。它將接收一個字串作為引數。
  • stack := 新建一個列表
  • 對於範圍從 0 到字串大小的 i：
    • 如果字串[i] 等於 '('，則：
      • 將字串[i] 推入棧中
    • 否則：
      • 如果棧為空，則：
        • 返回 False
      • 否則：
        • 從棧中彈出元素
  • 如果棧不為空，則：
    • 返回 False
  • 返回 True
  • 在主方法中執行以下操作：
  • 如果 `is_balanced_parenthesis(s + t)` 為真，則：
    • 返回 True
  • 返回 `is_balanced_parenthesis(t + s)`

讓我們看看下面的實現來更好地理解：

示例

線上演示

def is_balanced_parenthesis(string):
   stack = []
   for i in range(len(string)):
      if string[i] == '(':
         stack.append(string[i])
      else:
         if len(stack) == 0:
            return False
         else:
            stack.pop()
   if len(stack) > 0:
      return False
   return True
def solve(s, t):
   if is_balanced_parenthesis(s + t):
      return True
   return is_balanced_parenthesis(t + s)
s = "()()))"
t = "()(()("
print(solve(s, t))

輸入

"()()))", "()(()("

輸出

True

更新於：2020-12-30

278 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告