カッコが対応しているかどうか判定する - 「プロになるJava」ボツ原稿

「プロになるJava」ボツ原稿、今回は「13章 処理の難しさの段階」の「隠れた状態を扱う処理」のもうひとつの例として、カッコの対応を判定する処理です。13.1.2のあとに入る想定です。
書籍にのせたランレングス圧縮よりもカッコの対応の判定のほうが「隠れた状態」がわかりやすいのですが、重複を省く処理からの流れでランレングス圧縮を残しました。

隠れた状態を扱う処理

カッコの対応の判定

((test(data))test)」のような文字列で、カッコ「(~)」が正しく対応しているかどうかを判定するプログラムを考えます。このとき、単純に前の要素を見ても、正しく対応しているかどうかの判断はできません。
最初に思いつくのは、開きカッコと閉じカッコが同じ数だけあればいいというものです。確かに先にあげた例では開きカッコが3つ、閉じカッコが3つで正しく対応しています。しかし、「)test(」では開きカッコと閉じカッコの数は正しいものの、正しく対応してるとは言えませんね。

開きカッコの数を数えるという方針は正しいのですが、閉じカッコは開きカッコと別に数えるのではなく、閉じカッコが来ると開きカッコの数を減らしていくようにすれば対応を判定できます。最終的に0になれば全ての開きカッコが正しく閉じられ、途中でマイナスになるなら閉じカッコが多すぎると判断できます。

src/main/java/projava/CheckParentheses.java

package projava;

public class CheckParentheses {

    static boolean check(String data) {
        int count = 0;
        for (var ch : data.toCharArray()) {
            switch (ch) {
                case '(' -> count++;
                case ')' -> {
                    count--;
                    if (count < 0) {
                        return false;
                    }
                }
            }
        }
        return count == 0;
    }

    public static void main(String[] args) {
        System.out.println(check("((test(data))test)" ));
        System.out.println(check("((test(data)test)" ));
        System.out.println(check("()test)data(test" ));
    }

}

実行すると、mainメソッドでのカッコの対応が取れているのは最初の行だけなので、次のように表示されます。

true
false
false

処理はcheckメソッドとして書いていきます。判定する文字列を引数dataで受け取ります。カッコの対応が正しければtrueを返すことにします。

static boolean check(String data) {

変数countで開きカッコの数を管理します。

int count = 0;

文字列中の文字の数だけ繰り返します。

for (var ch : data.toCharArray()) {

取り出した文字で処理を振り分けるようswitch文で分岐します。

switch (ch) {

開きカッコの場合は変数countの値を増やします。

case '(' -> count++;

閉じカッコの場合は変数countの値を減らします。

case ')' -> {
    count--;

このとき、もし変数countの値が負になっていれば、対応が取れていないことをあらわすfalseを返して処理を終了します。

if (count < 0) {
    return false;
}

すべての文字を処理したあと、変数countが0であれば対応が取れていることをあらわすtrueが返るようにして処理を終了します。

return count == 0;

mainメソッドで、カッコが正しく対応している文字列、閉じカッコの数が足りない文字列、開きカッコと閉じカッコの数は同じでも順番がよくない文字列の判定をしています。

public static void main(String[] args) {
    System.out.println(check("((test(data))test)" ));
    System.out.println(check("((test(data)test)" ));
    System.out.println(check("()test)data(test" ));
}