演習問題

解答は

• ホスト: earth.mlab.im.dendai.ac.jp
• ディレクトリ: /home/submit/JavaLib/[今日の日付]/[学籍番号]

に提出しなさい。クラスファイル (〜.class) は提出不要。 提出は gFTP 等の ftp ソフトを用いて行うこと。

問題1

キューおよびスタックの例を、それぞれ3つ以上挙げなさい。 身近な例でも身近でない例でもかまわない。 なお、友達が思いついたものを採用しないこと。

記述するファイルのファイル名は Queue.txt とする。 なお、ファイルの permission の設定を、他人にも読める状態にして提出すること。 以下のコマンドを実行すると誰にでも読めるようになる。

$ chmod a+r ファイル名

問題2

キューを用いた簡単なプログラムを作成しなさい。 Queue インタフェースを実装しているクラスを用いること。 問題1で挙げた例のうちの1つをシミュレートするものでもよいし、違うものでもよい。 友達とは違うものにすること。

キューに入れるものはキーボードから入力してもよいし、ファイルから読み込んでもよいし、 ソースに直接書いてもよいし、その方法は問わない。

main メソッドのあるクラスのクラス名は QueueTest とする。

問題3

スタックを用いた簡単なプログラムを作成しなさい。 Deque インタフェースを実装したクラス (LinkedList, ArrayDeque など) をスタックとして用いてもよいし、Stack クラスを用いてもよい。 友達とは違うものにすること。 スタックに入れるものの入力の方法は問わない。

main メソッドのあるクラスのクラス名は StackTest とする。

注: 再履修者で Java SDK の version が 1.6 よりも前の場合には Deque が使えないので、Stack クラスを用いること。Java の version は java -version とすると確認することができる。

問題4

スタックの機能を持つクラスを自作し、そのスタックを用いた簡単なプログラムを作成しなさい。 push, pop, size の各メソッドが実装されていれば、それ以外の機能は問わない。 クラスの内部での情報の格納には配列を用いること。 ただし、外からは内部が配列であることを意識せずに使えるようにすること。

格納する要素の型は、何らかのクラスとすること (int, double などのプリミティヴ型にしないこと)。 なお、格納する要素の型はあらかじめ特定のクラスに決めてよい。new LinkedList<Music> のように、その場で格納する要素の型を指定できるようにはしなくてよい (やり方を知っている人は、そうしてもよい)。

配列は、あらかじめ十分大きいサイズのものを用意することにしてよい。 配列のサイズを越える追加の要求があった場合に、より大きな配列を用意する ArrayList のような機能は実現しなくてよい。

main メソッドのあるクラスのクラス名は MyStackTest とする。

「明解 Java によるアルゴリズムとデータ構造」に掲載されているサンプルプログラムは int の配列を用いたものなので、この問題の条件は満たさないが、 配列の利用のしかた、特にスタックポインタの使い方は参考になる。 なお、そのサンプルプログラムのようにさまざまなメソッドを用意する必要はない。

問題5 (Advanced)

四則演算などの演算を式で表すときに、通常次のように記述する。

3 + 5

この書き方は演算される 3 と 5 の間に演算子(+)を置くことから、中置記法と呼ばれる。 これに対し、演算子を後ろに置く書き方もあり、これを後置記法(逆ポーランド記法)と呼ぶ。

3 5 +

項が増えると以下のようになる。

3 + 5 * 7 => 3 5 7 * +
(3 + 5) * 7 => 3 5 + 7 *

後置記法では実際に演算をする順序で演算子が現れるように記述するため、 括弧や演算子の優先順位が考慮済みである。 そのため、スタックを使った簡単なアルゴリズムで演算を進めることができる。

先頭から1つ(1トークン)ずつ順に見ていくとして、次のルールのようにスタックを使う。

• 数字 -> そのままスタックに積む
• 演算子 -> 演算に必要な数の値をスタックから取り出し、演算をして結果をスタックに積む

入力式を末尾まで処理したときには、スタックに計算結果の値1つが入っている状態になる。

import java.util.*;

public class Calculator {
    public static void main(String[] args) {
        System.out.println("数式を後置記法・空白区切りで入力してください(例: 3 5 +)");
        // 標準入力(キーボード)から1行読み込み
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        // 空白で区切って String の配列に
        String[] token = line.split(" ");
        // 内容確認
        for(int i = 0; i < token.length; i++) {
            System.out.println("token[" + i + "] :  " + token[i]);
        }
        // スタックを使った演算

        // まずは空のスタックを用意(型は?)
        // 入力された後置記法の式を先頭から見ていく
        //   いま見ているものが + だったら? -> 数を2つ pop して+の演算、結果をpush
        //   いま見ているものが * だったら? -> 数を2つ pop して*の演算、結果をpush
        //   ...
        //   演算子でなければ数字なので、スタックに push

    }
}

スタックを使った演算の部分を実装し、上記プログラムを完成させなさい。

ユーザが入力したものは数字であっても文字列なので、 演算をする前のどこかの段階で int の値に変換する必要がある。 どの段階で変換するかで、 スタックの中身を String にするか Integer にするかが決まる。

演算結果が正しいか、動作確認をすること。 特に - と / は項の順序を取り違えると結果が異なるので注意すること。