エディター（Visual Studio Codeなど）を使って、コーディングをしていると対応する括弧（中括弧、丸括弧など）がない場合、「対応する括弧がありませんよ」と教えてくれる便利な機能があったりします。

今回は、このロジックを考えていきたいと思います。

スタック（データ構造）

基本的なデータ構造にスタックというのがあります。 スタックはデータの取り出し方に特徴があります。最後に入れたデータからしか取り出すことができないということです。 後入れ先出しなどと呼ばれたりしています。 例えば、下の絵のように、お皿を順番に積み上げていくと、後から置いたお皿からしか取っていけないといったイメージです。 スタック このデータ構造を使って、対応する括弧があるかを判別していきます。

では、ロジックを考えていきたいと思います。

まず、データ構造のスタックをどこで使うかですが、 渡された文字列をひとつずつ見ていって、始め括弧が出てきた時に、スタック構造の配列（リスト）にその括弧を一時的に保存するときに使います。（このブログでは、実際は、その対応する終わり括弧を保存していきます。）

一時的に保存する配列（リスト）は、 要素の操作として、「末尾に追加」と「末尾から取り出して削除」することしか行わないことにします。

では、実際に考えていきたいと思います。

例えばこのような文字列があったとします。

(apple[orange])

この文字列の文字をひとつずつみていって、括弧があった場合に次のような処理を行っていきます。 １．始め括弧の「(」が出てきたので、スタック構造のリストに対応する終わり括弧「)」を入れます。 ２．始め括弧の「[」が出てきたので、スタック構造のリストに対応する終わり括弧「]」を入れます。 ３．終わり括弧「]」が出てきたので、スタック構造のリストの一番上のものを取り出して、比較します。 ４．終わり括弧の「)」が出てきたので、スタック構造のリストから取り出して、比較します。

OK

文字列のすべてをみていって、スタック構造のリストに何も残ってなければOKということになります。 この説明はエラーにならない場合になります。

反対にどういったときにエラーになるのかを考えておく必要もあります。

エラーになるパターン１
(apple[orange)

１．始め括弧の「(」がでてきたので、対応する「)」をスタック構造のリストに入れます。 ２．始め括弧の「[」が出てきたので、対応する「]」をスタック構造のリストに入れます。 ３．終わり括弧の「)」が出てきたので、スタックの一番上のものを取り出して比較します。

002.png

スタックの一番上は、「]」なので比較すると「)」 ≠ 「]」になるので、この時点でエラーとなります。

エラーになるパターン２
apple](orange)

終わり括弧が最初に出てくる場合は、スタック構造のリストに何も入っておらず、比較するものがないのでエラーとなります。

エラーになるパターン３
(apple)[orange

この場合は文字列すべてみ終わった時にスタック構造のリストに「]」が残ることになります。 文字列をすべて取り出し終わった後、スタック構造のリストの中に何かしら残っている場合はエラーとなります。

以上がエラーになる場合になります。（もしかしたら他にあるかもしれませんが。。。）

これをコーディングしていきます。

def check_format(chars):
    # 括弧があるかどうかの判定用にオブジェクトを作成する
    brackets = { '(': ')', '[': ']', '{': '}' }
    # 配列（スタック構造）をつくる
    stack = []

    # 引数で渡されたcharsの文字列を一文字一文字を取り出していく
    for char in chars:
        # bracketsのkeyがあった場合
        if char in brackets.keys():
            # stackにkeyに応じたvalueを入れる
            stack.append(brackets[char])
        # bracketsのvalueがあった場合
        if char in brackets.values():
            # stackが空の場合
            if not stack:
                return "Error"
            # stackから取り出したものと比較する（比較したものが同じであればforループを続ける）
            if char == stack.pop():
              continue
            else:
              return "Error"

    # 文字列をすべてみたあと
    # stackに何かしら残っている場合はError
    if stack:
        return "Error"
    
    return "OK"


if __name__ == '__main__':
    s = '[apple(orange)]'
    print(check_format(s))

この部分は

  if char == stack.pop():
    continue
  else:
    return "Error"

次のようにも書けます。

if char != stack.pop()
  return "Error"

以上となります。 今回は、スタック構造を使ったロジックを考えてみました。