Javaで書く括弧検証プログラム その3

その1はこちら
その2(その1からの改良Ver)はこちら

括弧検証プログラムを作ろう その3

またまたチーム内課題で括弧検証プログラムを作る事になりました。

今度はHTMLのコメント行<!---->、JavaやC言語などのコメント行/* */などの、
「複数文字を一括りに括弧の様に扱うものでも対応出来る様に」すると言うもの。

また「後に対応する括弧が増えても、なるべく拡張性に富む様に。
理想は拡張のために1箇所のみを変更すれば良い様にする」とも告げられました。
折角だし、ユーザー入力で対応する括弧を拡張できたらなぁ…と思います。

そして、いつもの様にスクリプト言語は禁止みたいです。
まぁ使う言語に関しては、前回や前前回の様にJavaで行きましょうかね。

前回の課題時に、チーム内の先輩のふつくしいソースコードを見れたので…。
それを参考にしつつ、良いソースコードを書いていきましょう！

複数のクラスを使って書こう！

先輩が書いたソースコードを見ると、単一のクラスで全ての処理をするのではなく、複数のクラス同士を結びつけて処理を行わせていました。

しかもUML記法を用いたクラス設計図まであり…。
講義で学んだものはこう使えるのか！と凄く感動しました。

早速自分でも設計しちゃいましょう。
最終的には下記の様になりました。

BracketType
- typeN: String // 括弧の種類 - rawO: String // 対象の生の開き括弧データ - rawC: String // 対象の生の閉じ括弧データ

Bracket
- type: BracketType // 括弧の種類 - rawD: String // 対象の生のデータ - row: int // その括弧があった行数 - col: int // その括弧があった列数

それにしてもこうして書くとわかりやすいものなんですねぇ。
システム設計法的な講義でUML記法を学んでよかった。

それでは実装に向けてゴリゴリ書いて行きましょう。

プログラム全体の流れ

実装に向けてゴリゴリ書き始めている中で、少し問題が…。

前回などの「ファイルから一文字ずつ参照して行く」方式では、「複数文字から構成される括弧の対応を確認する」事がボトルネックになってしまいました。

2時間くらいウンウン悩んだ結果、これは一から考え直した方がいいなと思い…。
全体的な流れを今一度考えて見ることにしました。

具体的にはどこが問題点か？

今回問題点となった事は「ファイルから1文字ずつ参照すると次の文字を予測していかないといけない」と言う事です。
逆に言えば、それ以外は全く問題ないということ。

色々と考えた結果、最終的に「1文字ずつではなく1行で文字判定をする」事に落ち着きました。
この方式にすれば<!--が来た時に、「<の次に!が来たら…」と判定する必要はなくなりますしね。

ただ、今度は「複数文字列からどうやって目的の文字列を探し当てるか？」という問題に直面しました。

indexOfメソッドを使おう

これまたいろいろ探した結果、Javaの文字列メソッドには、文字列から指定した文字列を取り出す「indexOf」というメソッドがある事が判明しました。
つまり、1行ずつ読み込んだファイルの文字列から、「indexOf」メソッドで検証したい括弧を探せば…と思ったのですが。

ここでもまた問題点が2つ出てしまいました。
何とか解決は出来たので、その解決法も載せましたが…。
正直これがスマートな解決法かは分かりません。
もし他の解決法等ありましたら、コメントしてくれると嬉しいです。

問題点1: 行の先頭から検索ができない

従来は「1文字ずつ順番に文字列を検証していた」ので、
何も考えず閉じ括弧が来たらプッシュして、開き括弧が来たらポップして、と出来たのですが…。

今回の方法は「検証したい括弧を1行の中から探す」ため、
行の先頭から検索が出来ず、括弧を検知しながらプッシュポップをする事が不可能となってしまいました。

解決法: 括弧検知を全て終了→括弧対応検知を行う

解決法として「ファイル全ての括弧を抽出してからプッシュポップをしよう」と少し思い切った方法でやってみる事にしました。

全てのファイル内の括弧をBracket型のリストに1つ1つ追加していき、ComparatorとCollectorを使って行順と列順にリスト内をソート、
最後に前々回で考えた方法で括弧検証をする事に。

本当は括弧を検知しながらプッシュポップを…とする方がスマートだと思いますが、今回ばかりはしょうがないかもですね。

問題点2: 検知した括弧を「検知済」と出来ない

当たり前ですが、1行の中に複数個同種の括弧が入っているパターンも考えられます。
このため、私は検索したい括弧の種類ごとにループを回せばいいと思ったのですが…。

indexOfはあくまで「検索するだけ」なので、元の文字列には何も変更を加えません。
これだとせっかく括弧を検知しても、ループさせてしまうとまた同じ括弧を検出してしまう事に…。

解決法: 自作関数の作成

こちらは関数を自作することで対応しました。
指定した文字を除外し、無関係な文字を入れた文字列を返すremoveStrという関数です。
この関数は今後も使いまわせそうですね。

参考までに、この関数のソースコードを貼っておきます。

ソースコードを展開する

/**
* 指定した文字を除外し、無関係な文字を入れた文字列を返す関数
* @param String str: 除外したい文字が入った文字列
* @param int head: 除外したい文字の先頭番号(0からカウント)
* @param int num: 除外したい文字数
* @return String: 除外された文字列
*/
public static String removeStr(String str, int head, int num) {
    String dummyStrMulti = "";
    for(int i=0; i<num; i++) {
        dummyStrMulti = dummyStrMulti + dummyStr;
    }
    if(head == 0) { // 先頭に来た文字が対象だった場合
        return dummyStrMulti + str.substring(head+num, str.length());
    }else if(head+num == str.length()) { // 最後に来た文字が対象だった場合
        return str.substring(0, str.length()-num) + dummyStrMulti;
    }else { // それ以外に来た文字が対象だった場合
        return str.substring(0, head) + dummyStrMulti + str.substring(head+num, str.length());
    }
}

最終的なプログラムの流れ

色々とまとめた結果、最終的にはこんな形に収まりました。

• 専用クラス: Bracket、BracketTypeを定義
• 検証する括弧の種類をBracketType型で定義
• 括弧検証したい任意のファイルから文字列を1行ずつ読み込み
• 各1行に対してその括弧が含まれているかを検索
  • 該当部分がある: その括弧をBracket型として定義し、リストに追加(検査した文字列はremoveStrで検査済み文字列に変換)
• リストを行番号と列番号でソート
• スタックを用いて括弧対応検証

後は書くだけです。ゴリゴリ書いていきましょう。

書きながら気づいた事

プログラムを書く時に気づいた、ちょっとした小ネタなどを記します。

クラスについて改めておさらい

折角クラスを使うのですから、Javaのクラスという概念について改めておさらいしてみる事に。

クラスとは:
プログラムを実行するための処理をまとめたオブジェクトで、クラスの処理の中にはメンバ変数や処理を実行するためのメソッドがあります。
メンバ変数とはクラス内で使用する変数のことで、メソッドとはメンバ変数などを使って行う処理をひと塊にまとめたものです。

※参考記事: 【Java入門】クラスの使い方総まとめ | 侍エンジニアブログ

オブジェクト=部品、メソッド=手段/方法と考えれば分かりやすいでしょうか。
もう少しちゃんと言うなら「クラスとはプログラムの任意の処理を行える部品」…と言う感じでしょうか。
C言語とかにも外部ファイルを読み込んで〜とありますし、似た様なものでしょうか。

関数とメソッドの違い

これは別にJavaに限った話ではなく、他の言語にもありますけどね。
自分としては

• 関数: 単独で実行できる処理の集まり
• メソッド: オブジェクトに対する手段(このオブジェクトにこの動作をしてね、とか)/オブジェクトの後に.(ドット)をつけて記述する

くらいの認識だったのですが…。
本当にこの認識でOKなのか調べてみました。

結論からすると「大体あってる」という感じです。
参考までに、IT用語辞典に載ってるこれらの情報を載っけておきます。

関数とは: 引数と呼ばれるデータを受け取り、定められた通りの処理を実行して結果を返す一連の命令群。
多くのプログラミング言語では、関数がプログラムを構成する要素となっている。
多くの言語や処理系では、開発者の負担を軽減するため、よく使う機能が関数としてあらかじめ用意されている。
※参考記事: 関数（ファンクション）とは - IT用語辞典 e-Words

メソッドとは: 方法、方式、手法、やり方、などの意味を持つ英単語。
ITの分野では、オブジェクト指向プログラミングにおいて各オブジェクトに属する処理や操作のことや、
通信プロトコルにおける要求の種類などのことをメソッドということが多い。
一般の外来語としては、一定の形式として確立した奏法、教授法、指導法、その他様々な技法のことを「○○メソッド」のように言う。
※参考記事: メソッド（メンバ関数）とは - IT用語辞典 e-Words

オブジェクト指向プログラミングにおけるメソッドについて:
オブジェクト指向ではデータと手続きをオブジェクトとして一体化(カプセル化)して定義、利用する。
この、オブジェクトに内包された手続き(データに対する処理内容を記述したプログラム)のことをメソッドという。
言語によっては「メンバ関数」などということもあるが、ほぼ同じ機能を表す。
メソッドはそのオブジェクトに対する操作内容の詳細が実装されており、外部からメソッドを呼び出して起動することにより、その内容が実行される。
操作の詳細をオブジェクト内部に隠蔽することができ、プログラムの再利用性や生産性を高めやすくなると言われている。
※参考記事: メソッド（メンバ関数）とは - IT用語辞典 e-Words

privateとpublicについて

以前から気になってた、"private"と"public"の違い。
この際なのでガッツリ調べてみました。

まずこれら二つは「アクセス修飾子」というもので、
クラス、インタフェース、メソッド、コンストラクタ、変数に対してこれを付けることが出来るとの事。

そしてアクセス修飾子というものは、

「指定した変数やクラスなどを、どの範囲から参照可能かのスコープを制御する」のに用いられるもの

※参照記事: とほほのJava入門 - とほほのWWW入門

だそうです。
また、このアクセス修飾子には"private"と"public"の他にも"protected"と言うものもあるらしく、
それぞれの違いは下記のようになっております。

アクセス修飾子	概要	自ファイル			他ファイル
		自クラス	サブクラス	他クラス	サブクラス	他クラス
public	すべてのクラスからの参照を許す	○	○	○	○	○
private	自クラスからのアクセスしか許さない	○	×	×	×	×
protected	他ファイル・他クラスからのアクセスをプロテクトする	○	○	○	○	×
なし		○	○	○	×	×

※参照記事: とほほのJava入門 - とほほのWWW入門

完成です！

いつものようにソースコードを貼り付けておきます。
※長ったらしいので折りたたんでおきました

ソースコードを展開する

Bracketクラス

/**
 * 実際の括弧を格納するクラス
 * 行数や列数も共に格納できる
 * @param BracketType type: 括弧の種類
 * @param String rawD: 対象の生のデータ
 * @param int row: その括弧があった行数
 * @param int col: その括弧があった列数
 * @param int judOC: 対象は開き括弧か閉じ括弧かどちらか(1:open 2:close)
 */
class Bracket {
    // メンバ変数
    public BracketType type;
    public String rawD;
    public int row;
    public int col;
    public int judOC;

    /**
    * 引数ありコンストラクタ
    * この時点では生データと行数、列数のみを入れる(括弧の種類、開きか閉じかは後から決める)
    * @param String typeN: 括弧の種類
    * @param String rawO: 対象の生の開き括弧データ
    * @param String rawC: 対象の生の閉じ括弧データ
    */
    public Bracket(String rawD, int row, int col) {
        this.rawD = rawD;
        this.row = row;
        this.col = col;
    }

    public BracketType getType(){
        return this.type;
    }
    public String getTypeN(){ // 括弧の種類をString型で返す
        return this.type.getTypeN();
    }
    public String getRawD(){
        return this.rawD;
    }
    public int getRow(){
        return this.row;
    }
    public int getCol(){
        return this.col;
    }
    public int getJudOC(){
        return this.judOC;
    }

    /**
    * 与えられたBracket型とが同じBracketTypeであるかを返す
    * @param Bracket b: 比較するBracket型
    * @return true: 同じ
    * @return false: 違う
    */
    public boolean equalsBracket(Bracket b){ // 括弧の種類をString型で返す
        if(this.getTypeN().equals(b.getTypeN())) {
            return true;
        }else {
            return false;
        }
    }
}

BracketTypeクラス

/**
 * 括弧の種類を格納するクラス
 * これ自体に実態の括弧を入れる用途はない(実態の括弧はBracketクラスに入れてね)
 * @param String typeN: 括弧の種類
 * @param String rawO: 対象の生の開き括弧データ
 * @param String rawC: 対象の生の閉じ括弧データ
 */
class BracketType{
    // メンバ変数
    public String typeN;
    public String rawO;
    public String rawC;

    /**
    * 引数ありコンストラクタ
    * @param String typeN: 括弧の種類
    * @param String rawO: 対象の生の開き括弧データ
    * @param String rawC: 対象の生の閉じ括弧データ
    */
    public BracketType(String typeN, String rawO, String rawC) {
        this.typeN = typeN;
        this.rawO = rawO;
        this.rawC = rawC;
    }

    /**
    * 対象が複数文字から構成される括弧かどうかを返す
    * @return true: 複数文字から構成される括弧
    * @return false: 単一文字から構成される括弧
    */
    public boolean judMultiBra() {
        if(this.rawO.length()!=1 || this.rawO.length()!=1) {
            return true;
        }else {
            return false;
        }
    }

    public String getTypeN(){ // 括弧の種類を返す
        return this.typeN;
    }
    public String getrawO(){ // 開き括弧の生データを返す
        return this.rawO;
    }
    public String getrawC(){ // 閉じ括弧の生データを返す
        return this.rawC;
    }
}

メインクラス

import java.io.File; // ファイルオブジェクト宣言用
import java.io.FileReader; // ファイルの読込屋さん
import java.io.BufferedReader; // FileReaderの強化版,FileReaderの機能を利用し更に強くなる
import java.io.FileNotFoundException; // 例外処理用
import java.io.IOException; // 例外処理用
import java.util.Deque; // スタックオブジェクト宣言用

import java.util.ArrayDeque; // Dequeの実装クラス
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.stream.Collectors;
import java.util.Iterator;

/**
 * 括弧を検査するプログラム
 */
class checkkakko4 {

    // 括弧に無関係なダミーテキスト
    public static String  dummyStr;
    // 検査する括弧の種類を定義するリスト
    public static List<BracketType> braTypeList  = new ArrayList<BracketType>();
    // 検査する括弧の生データ格納リスト
    public static List<String> braRawListM = new ArrayList<String>(); // 複数文字からなる括弧
    public static List<String> braRawListS = new ArrayList<String>(); // 単一文字からなる括弧

    /**
    * 与えられたBracketがどの括弧の種類か&開きか閉じか精査する
    * @param Bracket bra: 精査するBracket
    */
    public static void checkBracket(Bracket bra) {
        for(BracketType b: braTypeList) {
            if(bra.getRawD().equals(b.getrawO())) {
                bra.type = b;
                bra.judOC = 1; //open
            }else if(bra.getRawD().equals(b.getrawC())) {
                bra.type = b;
                bra.judOC = 2; // close
            }
        }
    }

    /**
   * 括弧対応を2つのスタックを用いて精査する
   * @param Stack: 括弧のみが入った精査する用のスタック
   * @return boolean: true-成功 / false-失敗
   **/
    private static boolean judgeBracket(Deque<Bracket> Stack){
        Deque<Bracket> bracketsStackJudge = new ArrayDeque<Bracket>();
        while(!Stack.isEmpty()){
        // スタックから1つ取り出す
            Bracket p = Stack.getFirst();
            Stack.removeFirst();
            if(p.getJudOC() == 2){// 閉じ括弧だったら
                bracketsStackJudge.addFirst(p);
            }
            else if(p.getJudOC() == 1){
                // 開き括弧があるのにスタックが空->エラー
                if(bracketsStackJudge.isEmpty()){
                    System.out.println("!----- Error -----!");
                    System.out.println("close bracket run short");
                    System.out.printf("This bracket type - " +p.getTypeN()+ " ");
                    if(p.getJudOC() == 1){
                        System.out.println("open");
                    }else {
                        System.out.println("close");
                    }
                    System.out.println("This bracket place - row:" +p.getRow()+ " col:" +p.getCol());
                    return false;
                }else{ // bracketsStackJudgeから対応する閉じ括弧を取り出す
                    Bracket pp = bracketsStackJudge.getFirst();
                    if(pp.equalsBracket(p)) {
                        bracketsStackJudge.removeFirst();
                    }else {
                        System.out.println("!----- Error -----!");
                        System.out.println("non-Support bracket");
                        System.out.printf("This bracket type - " +p.getTypeN()+ " ");
                        if(p.getJudOC() == 1){
                            System.out.println("open");
                        }else {
                            System.out.println("close");
                        }
                        System.out.println("This bracket place - row:" +p.getRow()+ " col:" +p.getCol());
                        return false;
                    }
                }
            }
        }
        // 両方とものスタックが空な事を確認する
        if(bracketsStackJudge.isEmpty()){
            return true;
        }else{
            System.out.println("!----- Error -----!");
            System.out.println("The number of brackets doesn't match");
            for(Bracket b: bracketsStackJudge) {
                System.out.printf("This bracket type - " +b.getTypeN()+ " ");
                if(b.getJudOC() == 1){
                    System.out.println("open");
                }else {
                    System.out.println("close");
                }
                System.out.println("This bracket place - row:" +b.getRow()+ " col:" +b.getCol());
            }
            return false;
        }
    }

    /**
    * 指定した文字を除外し、無関係な文字を入れた文字列を返す関数
    * @param String str: 除外したい文字が入った文字列
    * @param int head: 除外したい文字の先頭番号(0からカウント)
    * @param int num: 除外したい文字数
    * @return String: 除外された文字列
    */
    public static String removeStr(String str, int head, int num) {
        String dummyStrMulti = "";
        for(int i=0; i<num; i++) {
            dummyStrMulti = dummyStrMulti + dummyStr;
        }
        if(head == 0) { // 先頭に来た文字が対象だった場合
            return dummyStrMulti + str.substring(head+num, str.length());
        }else if(head+num == str.length()) { // 最後に来た文字が対象だった場合
            return str.substring(0, str.length()-num) + dummyStrMulti;
        }else { // それ以外に来た文字が対象だった場合
            return str.substring(0, head) + dummyStrMulti + str.substring(head+num, str.length());
        }
    }

    //------------------------------------------
    // メイン関数
    //------------------------------------------
    public static void main(String args[]){
    // 処理時間計測用タイマーセット
    long start = System.nanoTime();

    // 括弧に無関係なダミーテキストの設定
    dummyStr = "a";
    // 検査する括弧の種類を定義するリストの設定
    braTypeList.add(new BracketType("PAREN ()", "(", ")"));
    braTypeList.add(new BracketType("ANGLE <>", "<", ">"));
    braTypeList.add(new BracketType("SQUARE []", "[", "]"));
    braTypeList.add(new BracketType("BRACE {}", "{", "}"));
    braTypeList.add(new BracketType("COMMENT1 /* */", "/*", "*/"));
    braTypeList.add(new BracketType("COMMENT2 <!-- -->", "<!--", "-->"));

    // 検査する括弧の生データ格納
    for(BracketType b: braTypeList) {
        if(b.judMultiBra()) { // 複数文字からなる括弧なら
            braRawListM.add(b.rawO);
            braRawListM.add(b.rawC);
        }else { // 単一文字からなる括弧なら
            braRawListS.add(b.rawO);
            braRawListS.add(b.rawC);
        }
    }

    // 読み込みたいファイルのパス
    String filename = args[0];
    System.out.println("************************");
    System.out.println("Check of Brackets.");
    System.out.println("File name - " +filename);
    System.out.println("************************");
    System.out.println("Check bracket type is");
    for(BracketType b: braTypeList) {
        System.out.println(" - " +b.typeN);
    }
    System.out.println("");

    // ファイルの読み込み
    try{
         // 指定パスのファイルを読み込む
        File file = new File(filename);
        // ファイルが読み込めるかチェック、読みこめたら処理続行
        if (isExistReadfile(file)){
            BufferedReader br = new BufferedReader(new FileReader(file));


            List<Bracket> braList = new ArrayList<Bracket>();
            String str;
            int nowRow = 0;
            while((str = br.readLine()) != null){ // 一行ごとに文字を読み込み
                nowRow++;
                for(String s: braRawListM) { // 複数文字からなる括弧の処理
                    boolean nextC = false;
                    while(!nextC) {
                        int index = str.indexOf(s); // 括弧が入ってる文字の先頭位置を入れる
                        if(index == -1) {
                                nextC = true;
                                break;
                        }else {
                            Bracket bra = new Bracket(str.substring(index, index+s.length()), nowRow, index);
                            checkBracket(bra);
                            braList.add(bra);
                            str = removeStr(str, index, s.length());
                        }
                    }
                }
                for(String s: braRawListS) { // 単一文字からなる括弧の処理
                    boolean nextC = false;
                    while(!nextC) {
                        int index = str.indexOf(s); // 括弧が入ってる文字の先頭位置を入れる
                        if(index == -1) {
                                nextC = true;
                                break;
                        }else {
                            Bracket bra = new Bracket(str.substring(index, index+s.length()), nowRow, index);
                            checkBracket(bra);
                            braList.add(bra);
                            str = removeStr(str, index, s.length());
                        }
                    }
                }
            }

            // リストの並び替え、スタックに格納
            Comparator<Bracket> braComparator =
               Comparator.comparing(Bracket::getRow)
                          .thenComparing(Comparator.comparing(Bracket::getCol));
            List<Bracket> sorted_braList = braList.stream()
                                                .sorted(braComparator)
                                                .collect(Collectors.toList());
            Deque<Bracket> braStack = new ArrayDeque<Bracket>();
            for(Bracket b: sorted_braList) {
                braStack.addFirst(b);
            }

            if(judgeBracket(braStack)){
                System.out.println("");
                System.out.println("************************");
                System.out.println("Brackets Check - Clear");
                System.out.println("************************");
            }else{
                System.out.println("");
                System.out.println("************************");
                System.out.println("Brackets Check - failed");
                System.out.println("************************");
            }
            br.close();
        }else{ // ファイルが読みこめなかったら処理はしない
            System.out.println(filename+ "can't Read.");
        }
    }catch(FileNotFoundException e){
        System.out.println(e);
    }catch(IOException e){
        System.out.println(e);
    }

    // 処理速度計測用タイマーストップ
    long end = System.nanoTime();
    System.out.println("");
    System.out.println("Program Time:" + (end - start) / 1000000f + "ms");
    }

    /**
    * 指定したファイルが存在し、かつそれが読み込み出来るファイルかチェック
    * @param file: チェックしたいFile型のオブジェクト
    */
    private static boolean isExistReadfile(File file){
        if (file.exists()){
            if (file.isFile() && file.canRead()){
                return true;
            }
        }
        System.out.println("File is Not Found.");
        return false;
    }
}

余談

他の方のプログラムを見ると、正規表現やMapを用いてとってもスマートに完成させておられました。

もう括弧検査プログラムの改良課題はありませんが、個人的にものすごく気になる分野でもあるため、
ぜひJavaの正規表現について学んで見たいと思います。

学べば学ぶほど、学びたい事が出てくる！