Python で有効な括弧を確認する方法

このチュートリアルでは、Python で有効な括弧をチェックする方法を学習します。

かっこの文字列が与えられた場合、そのかっこの組み合わせが有効かどうかを確認することは、コーディング面接でよくある質問です。次の数分間で、この質問を解決するテクニックを学び、指定された文字列を検証する Python 関数のコードも作成します。

有効括弧問題とは何ですか?

有効な括弧の問題とは何ですか? という質問に答えることから議論を始めましょう。

単純括弧、中括弧、角括弧() [] {}の文字を含む文字列を指定した場合、指定された括弧の組み合わせが有効かどうかを確認する必要があります。

有効な括弧文字列は、次の 2 つの条件を満たします。

1. すべての左括弧には、同じタイプの対応する右括弧が必要です。
2. 括弧は正しい順序で閉じる必要があります。

以下に、有効な括弧文字列と無効な括弧文字列の例をいくつか示します。

 test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!

私たちの問題解決アプローチにおいて、スタックは極めて重要な役割を果たすデータ構造です。次のセクションでスタックの基本を確認しましょう。

スタック データ構造の再考

スタックは後入れ先出し (LIFO) データ構造であり、スタックの先頭に要素を追加したり、スタックの先頭から要素を削除したりできます。

スタックトップに要素を追加する場合はプッシュ操作を実行し、スタックトップから要素を削除する場合はポップ操作を実行します。

次の 2 つのルールを使用して、括弧文字列に対して実行できる一連の操作を考え出します。

• すべての開始ブラケットをスタックに押し込みます。
• 閉じ括弧を見つけたら、スタックの一番上から外します。

有効な括弧のチェック問題の解決に進みましょう。

有効な括弧を確認する方法

上記の例から得られた観察をすべてまとめると、次のようになります。

括弧の文字列の長さを確認します。奇数の場合、文字列は無効です。

すべての左括弧には右括弧が必要であるため、有効な文字列には偶数の文字が含まれている必要があります。文字列の長さが奇数の場合は、括弧の組み合わせが無効であるとすぐに結論付けることができます。

 # len(test_str) = 3 (odd); ] does not have an opening [
test_str = "{}]"

# len(test_str) = 3 (odd); ( does not have a closing )
test_str = "[(]"

# len(test_str) = 5 (odd); there's a spurious )
test_str = "{())}"

次に、文字列内の文字数が偶数の場合にどのように対処できるかを見てみましょう。

括弧の文字列の長さは偶数です。次は何ですか?

ステップ 1:文字列を左から右にトラバースします。文字列test_str 、文字列内の個々の文字をcharと呼びましょう。

ステップ 2:最初の文字char左括弧( 、 { 、または[ )の場合、それをスタックの先頭にプッシュし、文字列内の次の文字に進みます。

ステップ 3:次に、次の文字 ( char ) が左括弧か右括弧かを確認します。

ステップ 3.1:開始ブラケットの場合は、スタックに再度押します。

ステップ 3.2:代わりに閉じ括弧が見つかった場合は、スタックの一番上から外し、ステップ 4 に進みます。

ステップ 4:ここでも、スタックからポップされた値に基づいて 3 つの可能性があります。

ステップ 4.1:が同じタイプの開始ブラケットの場合は、ステップ 3 に戻ります。

ステップ 4.2:別のタイプの左括弧である場合は、再度、それが有効な括弧文字列ではないと結論付けることができます。

ステップ4.3: 最後の可能性は、スタックが空であることです。繰り返しますが、これは無効な文字列の場合です。対応する左括弧のない閉じ括弧に遭遇したためです。

有効な括弧文字列の例のチュートリアル

ここで 3 つの例を取り上げ、上記の手順を見てみましょう。

📑 すでにこの仕組みを理解している場合は、次のセクションに進んでください。

#1 。最初の例として、 test_str = "{()"とします。

• {は最初の文字であり、開始括弧なので、スタックにプッシュします。
• 次の文字 ( も開始括弧なので、先に進んでこれもスタックにプッシュします。
• 文字列の 3 番目の文字 ) は閉じ括弧なので、スタックの一番上からポップする必要があり、これは (を返します)。
• この時点で、文字列の終わりに到達しました。しかし、スタックにはまだ閉じられていない開始部分 { が含まれています。したがって、指定された括弧文字列test_strは無効です。

#2 。この 2 番目の例では、 test_str = "()]"とします。

• 最初の文字(は左括弧であり、スタックにプッシュされます。
• 2 番目の文字)は閉じ括弧です。スタックの一番上から飛び出すと、これはたまたま ) – 同じタイプの開始ブラケットです。次の文字に進みます。
• 3 番目の文字]閉じ角括弧であり、スタックの一番上から再度ポップする必要があります。ただし、ご覧のとおり、スタックは空です。これは、一致する左括弧[が存在しないことを意味します。したがって、この文字列は無効です。

#3 。この最後の例では、 test_str = "{()}" 。

• 最初の 2 文字{(は左括弧なので、スタックにプッシュします。
• 3 番目の文字は終了)なので、スタックの一番上からポップします – ( 。
• 次の文字}は閉じ中括弧であり、スタックの先頭をポップすると、 { – 開き中括弧が表示されます。
• 文字列全体を走査すると、スタックは空になり、 test_strが有効になります。 ✅

📌 有効な括弧チェック問題の手順の概要を示す次のフローチャートをまとめました。すぐに参照できるように保存できます。

次のセクションでは、私たちの概念を Python コードに変換する方法を見てみましょう。

有効な括弧をチェックする Python プログラム

Python では、リストを使用してスタックをエミュレートできます。

.append()メソッドを使用して、リストの末尾に要素を追加できます。これは、スタックの先頭にプッシュすることに似ています。

.pop()メソッドはリストの最後の要素を返します。これは、最後に追加された要素を削除するためにスタックの一番上からポップするのと似ています。

これで、スタックをエミュレートして、Python リストにプッシュおよびポップ操作を実装する方法がわかりました。

次のステップとして、開き括弧と閉じ括弧をどのように区別するかという質問に答えてみましょう。

Python 辞書を使用できます。開き括弧'{', '[', '('辞書のキーとして使用し、対応する閉じ括弧'}', ']', ')'値として使用できます。 .keys()メソッドを使用して、辞書内の個々のキーにアクセスできます。

学んだことをすべて利用して、 is_valid()関数の定義を作成しましょう。

関数定義を理解する

関数定義を含む次のコードセルを読んでください。フローチャートのステップを上記の説明と並行して使用していることがわかります。

さらに、次のようなdocstringも追加しました。

• 関数の簡単な説明
• 関数呼び出しの引数
• 関数からの戻り値

▶ help(is_valid)またはis_valid.__doc__使用して docstring を取得できます。

 def isValid(test_str):
  '''Check if a given parentheses string is valid.

  Args:
    test_str (str): The parentheses string to be validated
  
  Returns:
    True if test_str is valid; else False 
  '''
  # len(test_str) is odd -> invalid!
  if len(test_str)%2 != 0:
    return False
  # initialize parentheses dict
  par_dict = {'(':')','{':'}','[':']'}
  stack = []
  for char in test_str:
    # push opening bracket to stack
    if char in par_dict.keys():
      stack.append(char)
    else:
      # closing bracket without matching opening bracket
      if stack == []:
          return False
      # if closing bracket -> pop stack top
      open_brac = stack.pop()
      # not matching bracket -> invalid!
      if char != par_dict[open_brac]:
        return False
  return stack == []

Python 関数is_valid括弧の文字列が有効かどうかをチェックし、次のように動作します。

• 関数is_valid 、検証される括弧文字列であるtest_strという 1 つのパラメータを受け取ります。文字列test_str有効かどうかに応じて、 TrueまたはFalseを返します。
• ここで、 stackスタックをエミュレートする Python リストです。
• par_dictは Python 辞書で、開き括弧がキー、閉じ括弧が対応する値になります。
• 文字列のトラバース中に、括弧の文字列が無効になる条件に遭遇した場合、関数はFalseを返して終了します。
• 文字列内のすべての文字を走査した後、 stack == [] stackが空かどうかをチェックします。 「はい」の場合、 test_str有効であり、関数はTrueを返します。それ以外の場合、関数はFalseを返します。

それでは、いくつかの関数呼び出しを行って、関数が正しく動作することを確認しましょう。

 str1 = '{}[]'
isValid(str1)
# Output: True

str2 = '{((}'
isValid(str2)
# Output: False

str3 = '[{()}]'
isValid(str3)
# Output: True

str4 = '[{)}]'
isValid(str4)
# Output: False

str5 = '[[]}'
isValid(str5)
# Output: False

上記のコード スニペットから、関数は期待どおりに動作すると結論付けることができます。

結論

ここで学んだことを簡単にまとめます。

• まず、有効な括弧のチェックの問題について説明しました。
• 次に、選択したデータ構造としてスタックを使用して問題を解決するアプローチを学びました。
• 次に、Python 辞書を使用して、左括弧、キー、および対応する閉じ括弧を値として使用して、括弧の組み合わせを検証する方法を学習しました。
• 最後に、指定された括弧文字列が有効かどうかを確認する Python 関数を定義しました。

次のステップとして、 のオンライン Python エディターで問題をコーディングしてみます。サポートが必要な場合は、お気軽にこのガイドをもう一度ご覧ください。

Python チュートリアルをさらに確認してください。コーディングを楽しんでください!