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]は'＃'と同じですが、do
    • j：=j-1
  • i：=i + 1>
  • 1を返す
• それ以外の場合、
  • 0を返す
• メインの方法から、次の手順を実行します-
• sのサイズが0と同じ場合、
  • Trueを返す
• それ以外の場合、
  • ans：=False
  • i
  • 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("{([])}"))

入力

"{(()[])}"

出力

True