Javaのバランスブラケットアルゴリズム

投稿日: 2022-11-10 2022-11-10
タグ: Algorithms, Java

1. 概要

バランス括弧とも呼ばれるバランスブラケットは、一般的なプログラミングの問題です。

このチュートリアルでは、特定の文字列の角かっこがバランスされているかどうかを検証します。

このタイプの文字列は、ディック言語として知られているものの一部です。

2. 問題文

角かっこは、「（」、「）」、「[」、「]」、「{」、「}」のいずれかの文字と見なされます。

対応する閉じ括弧の左側に開始括弧、 “（”、 “[“、および “{“、が存在する場合、括弧のセットは一致したペアであると見なされます。、「）」、「]」、および「}」。

ただし、角かっこペアを含む文字列は、それが囲む角かっこセットが一致しない場合バランスが取れていません。

同様に、 az、AZ、0-9などの非括弧文字または＃、$、@ などの他の特殊文字を含む文字列も、不均衡と見なされます。

たとえば、入力が「{[（]）}」の場合、角かっこ「[]」のペアは、単一の不均衡な開き角かっこ「（」を囲みます。同様に、丸括弧のペア「（）」は、単一の不均衡な閉じ角括弧「]」を囲みます。したがって、入力文字列「{[（]）}」は不均衡です。

したがって、角かっこ文字を含む文字列は、次の場合にバランスが取れていると言われます。

対応する開始ブラケットは、対応する各終了ブラケットの左側にあります
バランスの取れたブラケットで囲まれたブラケットもバランスが取れています
角かっこ以外の文字は含まれていません

覚えておくべき特別なケースがいくつかあります。nullは不均衡であると見なされ、空の文字列はバランスが取れていると見なされます。

バランスブラケットの定義をさらに説明するために、バランスブラケットの例をいくつか見てみましょう。

()
[()]
{[()]}
([{{[(())]}}])

そして、バランスが取れていないいくつか：

abc[](){}
{{[]()}}}}
{[(])}

問題の理解が深まったので、問題を解決する方法を見てみましょう。

3. ソリューションアプローチ

この問題を解決するにはさまざまな方法があります。このチュートリアルでは、2つのアプローチを見ていきます。

Stringクラスのメソッドを使用する
Deque実装の使用

4. 基本的なセットアップと検証

まず、入力が平衡している場合は true を返し、入力が不平衡の場合はfalseを返すメソッドを作成しましょう。

public boolean isBalanced(String str)

入力文字列の基本的な検証について考えてみましょう。

null 入力が渡された場合、バランスが取れていません。
弦のバランスをとるには、開き角かっこと閉じかっこのペアが一致している必要があります。したがって、長さが奇数の入力文字列には、少なくとも1つの不一致のブラケットが含まれるため、バランスが取れていないと言っても過言ではありません。
問題の説明に従って、括弧の間でバランスの取れた動作をチェックする必要があります。したがって、角かっこ以外の文字を含む入力文字列は、不均衡な文字列です。

これらのルールがあれば、検証を実装できます。

if (null == str || ((str.length() % 2) != 0)) {
    return false;
} else {
    char[] ch = str.toCharArray();
    for (char c : ch) {
        if (!(c == '{' || c == '[' || c == '(' || c == '}' || c == ']' || c == ')')) {
            return false;
        }
    }
}

入力文字列が検証されたので、この問題の解決に進むことができます。

5. String.replaceAllメソッドの使用

このアプローチでは、入力文字列をループして、 String.replaceAll。を使用して、文字列から「（）」、「[]」、および「{}」のオカレンスを削除します。それ以上の出現は入力文字列で見つかります。

プロセスが完了すると、文字列の長さがゼロの場合、一致するブラケットのペアがすべて削除され、入力文字列のバランスがとられます。ただし、長さがゼロでない場合は、一致しない開始ブラケットまたは終了ブラケットが文字列に残っています。したがって、入力文字列は不均衡です。

完全な実装を見てみましょう：

while (str.contains("()") || str.contains("[]") || str.contains("{}")) {
    str = str.replaceAll("\\(\\)", "")
      .replaceAll("\\[\\]", "")
      .replaceAll("\\{\\}", "");
}
return (str.length() == 0);

6. Dequeを使用する

Deque は、 Queue の形式であり、キューの両端で追加、取得、およびピーク操作を提供します。このデータ構造の後入れ先出し（LIFO）順序機能を利用して、入力文字列のバランスをチェックします。

まず、Dequeを作成しましょう。

Deque<Character> deque = new LinkedList<>();

ここではLinkedListを使用していることに注意してください。これは、Dequeインターフェイスの実装を提供するためです。

deque が作成されたので、入力文字列の各文字を1つずつループします。文字が開き角かっこである場合は、Dequeの最初の要素として追加します。

if (ch == '{' || ch == '[' || ch == '(') { 
    deque.addFirst(ch); 
}

ただし、文字が閉じ括弧である場合は、LinkedListに対していくつかのチェックを実行します。

まず、LinkedListが空かどうかを確認します。空のlistは、閉じ括弧が一致しないことを意味します。したがって、入力文字列は不均衡です。したがって、falseを返します。

ただし、 LinkedList が空でない場合は、peekFirstメソッドを使用して最後の文字を確認します。閉じ括弧と組み合わせることができる場合は、 removeFirst メソッドを使用して、この最上位の文字をリストから削除し、ループの次の反復に進みます。

if (!deque.isEmpty() 
    && ((deque.peekFirst() == '{' && ch == '}') 
    || (deque.peekFirst() == '[' && ch == ']') 
    || (deque.peekFirst() == '(' && ch == ')'))) { 
    deque.removeFirst(); 
} else { 
    return false; 
}

ループの終わりまでに、すべての文字のバランスがチェックされるため、trueを返すことができます。以下は、Dequeベースのアプローチの完全な実装です。

Deque<Character> deque = new LinkedList<>();
for (char ch: str.toCharArray()) {
    if (ch == '{' || ch == '[' || ch == '(') {
        deque.addFirst(ch);
    } else {
        if (!deque.isEmpty()
            && ((deque.peekFirst() == '{' && ch == '}')
            || (deque.peekFirst() == '[' && ch == ']')
            || (deque.peekFirst() == '(' && ch == ')'))) {
            deque.removeFirst();
        } else {
            return false;
        }
    }
}
return deque.isEmpty();

7. 結論

このチュートリアルでは、バランスブラケットの問題ステートメントについて説明し、2つの異なるアプローチを使用して解決しました。

いつものように、コードはGithubでから入手できます。

getdocs

13036