括弧の正しい順序の検証

括弧の正しい順序を検証する、よくある課題について話しましょう。
この問題はここで見つけることができます： Valid Parentheses

課題の設定

ある文字列が与えられ、それには '(', ')', '{', '}', '[' と ']' の記号が含まれています。その文字列が、妥当な括弧の順序かどうかを判断する必要があります。

括弧の順序が妥当であるためには、以下の二つの条件を満たす必要があります：

同じ種類の開き括弧は、同じ種類の閉じ括弧で閉じられる
開き括弧は、正しい順序で閉じられる

入力データの例

例1

() - この文字列は、条件1と2を満たすため、正しい括弧の順序です。

例2

()[]{} - この文字列は、条件1と2を満たすため、正しい括弧の順序です。

例3

([)] - この文字列は、条件1と2を満たすため、正しい括弧の順序です。

例4

([}] - この文字列は、条件1を満たさないため、正しい括弧の順序ではありません。

例5

({)} - この文字列は、条件2を満たさないため、正しい括弧の順序ではありません。

解決方法

最初のアイデアは、開き括弧と閉じ括弧の数を数えることかもしれません。しかし、それでは条件2を満たせないかもしれません。したがって、順序も重要です。そのためには、スタック構造を使う必要があります。開き括弧をスタックに積み、閉じ括弧が現れた時には取り出します。

スタックには、ArrayDequeクラスが適しています。これはダブルエンドキューの実装です。

ステップごとの解決方法

文字列から次の要素を取り出す。それを行うために、forEach構造を使って文字列をイテレートします。イテレーションの各要素はChar型となります。

s.forEach { char ->
    ...
}

その文字が開き括弧または閉じ括弧かどうかをチェックします。そのために、whenコンストラクションを使います。
開き括弧であれば、スタックに積む

...
when(char) {
    '(' -> stack.addLast(char)
    '[' -> stack.addLast(char)
    '{' -> stack.addLast(char)
    ...
}
...

閉じ括弧であれば、スタックから括弧を取り出して対応するものかを比較する
括弧が対応していれば、続けてイテレーションする
括弧が対応していなければ、falseを戻す

when(char) {
    ...
    else -> if (stack.isNotEmpty() || isCorrectChar(stack.removeLast())) return false
}
...

最後に、スタックが空であればtrueを、スタックに要素が残っていればfalseを戻す

return stack.isEmpty()

最適化

スタックに開き括弧を積むため、閉じ括弧との対応を比較する必要が生じます。これはかなり煩雑な構成で、維持する必要があります。代わりに、最初から対応する閉じ括弧をスタックに積み、その後で等価性を比較します。

when(char) {
    '(' -> stack.add(')')
    '[' -> stack.add(']')
    '{' -> stack.add('}')
}

複雑さの評価

時間に関しては - O(s.length)です。文字列全体をループするため、O(s.length)になります。また、ダブルエンドキューの末尾に挿入や抽出を行う操作がO(1)です。
メモリに関しては - O(s.length)です。使う追加メモリの最大サイズはO(s.length)で、なぜならスタックに入力データの長さ以上を追加することはありません。

完全な解決方法

fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>()
    s.forEach { char ->
        when(char) {
            '(' -> stack.addLast(')')
            '[' -> stack.addLast(']')
            '{' -> stack.addLast('}')
            else -> if (stack.isNotEmpty() || stack.removeLast() != char) return false
        }
    }
    return stack.isEmpty()
}
```<br><br>こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。<br>[https://dev.to/ivsivak/validatsiia-skobochnoi-posliedovatielnosti-ai1](https://dev.to/ivsivak/validatsiia-skobochnoi-posliedovatielnosti-ai1)