System.out.print 先段まで使用してきた上記 System/Math/String クラスは基本パッケージと呼ばれ,import 文の記述なしに提供されるクラス 2.2 BufferedReader クラスと例外処理 端末から文字列をプログラムに入力したい場合,java.io.Buff

16 

Loading.... (view fulltext now)

Loading....

Loading....

Loading....

Loading....

全文

(1)

2章 スタックを用いた後置(逆ポーランド)記法による演算

電卓の制御構造作成に不可欠な逆ポーランド記法について学習し,プログラム作成を目的する。 逆ポーランド記法およびコード作成に不可欠なスタック概念の理解を行う。スタック概念と java.util パッケージからStack クラスを使用したスタック制御構造をプログラム作成する。その後,逆ポーラ ンド記法の制御構造を作成して動作検証する。

2.1 Java API(Application Programming Interface)の利用

Java は様々な用途のクラスをクラスライブラリで提供しており,これらを活用することで効率的に プログラム作成ができる。クラスライブラリはパッケージと呼ばれる単位でまとめられている。

以下に主要なパッケージを示す。

パッケージ名 機能 クラス例

java.awt 描画・GUI 部品関係 Graphics Image Button java.awt.event イベント処理関係 ActionEvent MouseEvent java.awt.image イメージ処理関係 ImageFilter ImageObserver

java.io ファイル入出力関係 RandomAcessFile BufferedReader java.lang 型・スレッド関係 Thread Integer String

java.util 日付などユーティリティ関係 Date Calender Random javax.swing Swing コンポーネント関係 JFrame JPanel JButton javax.swing.event Swing コンポーネント 拡張イベント処理関係 DocumentEvent ListSelectionEvent API を利用するには,クラスを import 文でロードする。以下に書式を示す。 import パッケージ名.クラス名; // パッケージの指定クラスのみを利用したい場合 import パッケージ名.*; // パッケージのすべてのクラスを利用したい場合

(2)

System.out.print 先段まで使用してきた上記 System/Math/String クラスは基本パッケージと呼ばれ,import 文の 記述なしに提供されるクラス 2.2 BufferedReader クラスと例外処理 端末から文字列をプログラムに入力したい場合,java.io.BufferedReader クラスの readLine() メソッドを用いる方法がある。端末からの文字列入力操作では,端末よりキー入力が行われない 等の処理ができない状態が発生する可能性がある(例外処理)。このような処理を行わせる場合, 例外処理(throws IOException や try catch 文)の記述が必要となる(記述していない場合,コンパ イルエラーとなる)。 try catch 文の書式を下記に示す。 try{ 例外が発生するかもしれない処理 } catch(補足する例外が起こるクラス e){ 必ず実行する処理 }

(3)

2.3 スタックと Stack クラス

スタックとは,コンピュータで用いられる基本的なデータ構造の 1 つで,例としてデータを後入れ 先出し(LIFO: Last In First Out; あるいは FILO: First In Last Out)の構造で保持するものがあ る。スタックはpush/pop の 2 つの動作によりデータを操作できる。 その概念図とデータ操作の詳細について以下に示す。 Push 指定されたノードをスタックの先頭(トップ)に追加。 既存のノードはその下にそのまま置く。 Pop スタックの現在のトップのノードを外してそれを返す。 スタックは基本的かつ応用上重要なデータ構造のため,多くのプログラミング言語が標準ライブ ラリなどの形でサポートしている。Java の API にも java.util.Stack というクラスがある。

(4)

下記にStack クラスのコンストラクタと主要メソッドを示す。 コンストラクタ 説明 Stack() 空の Stack を作成します。 public Stack() 空の Stack を作成します。 型 メソッド 説明 boolean empty() スタックが空かどうかを判定します。 E peek() スタックの先頭にあるオブジェクトを取り出します。 E pop() スタックの先頭のオブジェクトを削除し, そのオブジェクトを関数の値として返します public E pop() スタックの先頭のオブジェクトを削除し, そのオブジェクトを関数の値として返します。 戻り値: スタックの先頭にあるオブジェクト。 (Vector オブジェクトの最後の項目) 例外: EmptyStackException … スタックが空の場合 E push(E item) スタックの先頭にオブジェクトを入れます。

public E push(E item)

スタックの先頭にオブジェクトを入れます。 これは,次の内容とまったく同じ効果を持ちます。 addElement(item) パラメータ: item … スタックに入れるオブジェクト 戻り値: item 引数 関連項目: Vector.addElement(E) int search(Object o) このスタックにあるオブジェクトの位置を 1 から始まるインデ ックスで返します。

※ 上記の E の型のメソッドの呼び出しのため,Stack st = new Stack(); のようにコードの中で記述 し て コ ン パ イ ル し た と き に は 警 告 が 表 示 さ れ る 。 こ れ を 解 消 し た い 場 合 に は , 例 え ば Stack<String> st = new Stack<String>(); のように型指定で記述する(但し配列は不可)。

(5)

2.4 Stack クラスでのキャスト・文字列比較

Stack クラスで格納(push メソッド),取り出し(pop メソッド)ができるが,これらの動作で使用する String 型変数について説明する。基本型とほぼ同様に使用できるが,String クラスとして定義され ているため,その扱いに注意が必要となる。 例として,そのキャスト方法について,以下に説明する。 格納できる変数 スタックはObject クラスのものを格納できる. Object クラスはすべてのクラスに継承されているので, スタックにはすべてのクラスを格納することができる. String クラスは Object クラスを継承しているので, スタックに入れることができる. 取り出しした変数 スタックから取り出した場合,Object クラスとして扱われ, 使用するクラスへの変換(キャスト)が必要となる。 本実習で使用するキャストの例を下記に示す。 (valueOf メソッドを用いた例) 変換型 記述 String 型 String.valueOf(…) char 型 Character.valueOf(…)

(6)

また,よく使用する例として,String 型での比較(文字列比較)がある。基本データ型では演算子 による比較が可能であるが,String 型は基本データ型でないため,文字列比較を String 型変数 == ”文字列” で行うことができない(コンパイルエラーとならないため注意すること)。 そこで,文字列比較にはequals メソッドを使用することで比較が可能となる。 データ型 記述例 内容 基本データ型 (例: int 型) int x, y; if(x == y){ … } x と y が等しいなら String 型 String st1, st2; if(st1.equals(st2)) st1 と st2 の変数に格納された文字列が同じなら (equals メソッド) String st1, st2; if(st1 == st2){ … } 参照するオブジェクトst1 と st2 (オブジェクトそのもの)が等しいなら ※ この場合は文字列を比較しない

(7)

2.5 逆ポーランド記法を用いた文字列処理

2.5.1 逆ポーランド記法の基礎(1 桁の文字に対応する文字の処理)

一般的な電卓の式入力で用いられる 1 + 2 = という方法は中置記法(IN: Infix Notation)であ り,電卓の制御処理では後置記法(逆ポーランド記法 … RPN: Reverse Polish Notation)に置き 換えて処理が行われる(ちなみに前置記法がポーランド記法 … PN: Polish Notation)。これは, 演算処理において演算子の一つ前と二つ前の数値が演算対象となる構成のため,処理指定を行 いやすいためであり,ポーランド記法→逆ポーランド記法の手動での置き換え方法と,制御構造 例を検討する。 例: 「1 + 2」で示す中置記法は,後置記法では「1 2 +」となる。 記法 記述 備考 中置記法 1 + 2 演算子を操作対象の中心に記述する 後置記法 1 2 + 演算子を操作対象の後に記述する 前置記法 + 1 2 演算子を操作対象の前に記述する 中置記法(IN)で示す「1 + 2 * 3 + 4」を,手動で後置記法(RPN)に置き換える方法例には下記 がある(簡略的に検討するため,演算子は四則演算記号(+,-,*,/)のみで,括弧など他の記号 は含まない場合)。 手順 算術式置き換え ① 2 * 3 を X と置き換える 1 +X + 4 ② 1 + X を Y と置き換える Y + 4 ③ 後置記法に置き換える Y 4 + ④ 式Yの内容を後置記法に置き換える (1 + X → 1 X +) 1 X + 4 + ⑤ 式Xの内容を後置記法に置き換える (2 * 3 → 2 3 *) 1 2 3 * + 4 +

(8)

上記手順をプログラム処理で制御する場合,スタックを2 つ使う方法で処理を記述できる。以下 にアルゴリズム(算法,あるいは制御の手順)を示す。 ① スタックを 2 つ用意する (スタックA,スタック B) ② 中置記法の算術式を左から順に1 項ずつ読み込む (式を読み込み終わるまで繰り返す) 数字の場合: スタックA に push 数字以外(演算子)の場合: ⅰ) スタック B が空でない場合,以下をおこなう 下表の演算子優先順位により, 読み込まれた演算子と,スタックB の最上位要素の演算子の優先順位を比較 優先度 … スタック B の最上位要素の演算子優先順位 (優先度値が大きいほど優先される) 優先度値 演算子 2 * / 1 + - 0 上記以外 読み込まれた演算子の優先順位が高い場合: スタックB に push し,次のⅱへ進む 読み込まれた演算子の優先順位が低い場合: スタックB の演算子をスタック A に push し,比較処理に戻る (スタック1 が空になればⅱへ進み,空でない限りⅰを繰り返す) ⅱ) 読み込まれた演算子をスタック B に push ③ 算術式をすべて読み込み処理後,スタック A が空になるまでスタック B へ push

(9)
(10)

2.5.2 入力項判定処理 逆ポーランド記法置き換えにおいては,まず入力項が数字か演算子かを判定し,その優先順 位からスタックへの振り分け処理を行う。 判定基準は下記とする。 数字(number) 1~9 の 1 桁の数字,または小数点(.) 演算子(operator) 上記以外のすべての文字 2.5.3 複数桁に対応した入力項判定処理 簡易的な置き換え処理では,1 桁のみの項に対応しており,複数桁の項を 1 桁ずつに分けて処 理を行ってしまう。そのような問題を回避するため,複数桁を判定する処理の追加を行う。 複数桁の判定条件を下記として記述例を示す。 数字(number) 1~9 の 1 桁の数字,または小数点(.) 左記以外が入力されるまでを1 項として連結させる 演算子(operator) 上記以外のすべての文字 中置記法の算術式を左から順に1 項ずつ読み込む (式を読み込み終わるまで繰り返す) 数字の場合: バッファnum を” is number.”表示 数字以外(演算子)の場合: バッファnum を” is number.”表示 バッファnum を” is operator.”表示

(11)

2.6 逆ポーランド記法の演算処理 中置記法で記述された算術式を後置記法(逆ポーランド記法)に置き換える処理を行うプログラ ムを,スタックを用いて作成した。今回は逆ポーランド記法で記述された算術式を元に演算処理を 行わせる制御を追加する。 最初に,逆ポーランド記法(RPN)で記述された式を演算する手順について説明する。 例) 中置記法: 1 + 2 * 3 - 4 ↓ 後置記法(RPN): 1 2 3 * + 4 - ① 左から順番に項を取り出す 1 2 3 * + 4 - ② 数字以外の項(演算子)が取り出されたら, その前に取り出された2 項と演算を行う 1 2 3 * + 4 - 2 3 * = 2 * 3 = 6 【演算を行う場合】 左側の数字が演算の先頭項に なるように注意する。 ③ 演算した結果を取り出した 3 項の場所に 当てはめて,前の手順(①)に戻る 1 6 + 4 - ④ すべての項を取り出したら終了する 1 6 + 4 - 1 6 + = 1 + 6 = 7 7 4 - 7 4 - = 7 - 4 = 3 上記手順をプログラム処理で制御する場合,逆ポーランド記法での数式がスタック B に既に準 備されているとすると,アルゴリズムは下記となる。 ① スタック B が空でないか判定する ② スタック B を pop して,演算子(+ ,- ,*,/)であるか判定する 演算子でない場合: スタックA に push する 演算子の場合: スタックA を 2 回 pop して,2 つの double 型変数(d[1],d[0])に順に代入する ③ ①で該当した演算子を数式として計算し,結果をスタック A に push する ④ ①の処理を再度おこなう

(12)
(13)

2.7 括弧を含む文字列の処理方法 中置記法を後置(逆ポーランド)記法に手動で置き換える方法例には,下記がある。 例) 1 * ( 2 + 3 ) 手順 算術式置き換え ① 2 + 3 を Z と置き換える 1 * ( Z ) ② 括弧を外す 1 * Z ③ 後置記法に置き換える 1 Z * ④ 式Zの内容を後置記法に置き換える (2 + 3 → 2 3 +) 1 2 3 + * 上記手順をプログラム処理で制御する場合,2.5.1 節で示したスタックを 2 つ使う方法に,処理 を追加することで記述できる。 以下にアルゴリズムを示す(ここでは演算子 +,-,*,/ のみ括弧との比較に対応,なお複数桁 の数字にも対応)。

(14)

① スタックを 2 つ用意する (スタックA,スタック B) ② 中置記法の算術式を左から順に 1 項ずつ読み込む (式を読み込み終わるまで繰り返す) 数字の場合: バッファnum に追加する(数字の結合) 左括弧の場合: (その左括弧を)スタックB に push それ以外(演算子または右括弧)の場合: ⅰ) バッファ num が空欄でない(1 つ前に読み込まれた文字が数字である)場合, バッファnum をスタック A に push バッファnum を空欄にする ⅱ) スタック B が空でない,かつ,スタックB の最上位要素が左括弧以外の場合, 以下をおこなう 下表の演算子優先順位により, 読み込まれた演算子と,スタックB の最上位要素の演算子の優先順位を比較 優先度 … スタック B の最上位要素の演算子優先順位 (優先度値が大きいほど優先される) 優先度値 演算子 2 * / 1 + - 0 上記以外(括弧はここに含まれる) 読み込まれた演算子の優先順位が高い場合: スタックB に push し,次のⅲへ進む 読み込まれた演算子の優先順位が低い場合: スタックB の演算子をスタック A に push し,比較処理に戻る (スタックB が空になればⅲへ進み,空でない限りⅱを繰り返す) ⅲ) 読み込まれた文字により,以下をおこなう 右括弧の場合: スタックB から(最上位要素である)左括弧を取り出して相殺 それ以外(演算子)の場合: 読み込まれた演算子をスタックB に push ③ バッファ num が空欄でない(最後の項が数字であり num に取り残されている)場合: バッファnum をスタック A に push // バッファ num を空欄にする(これ以降バッファは利用しないのでこの操作は不要) ④ 算術式をすべて読み込み処理後,スタック A が空になるまでスタック B へ push

(15)
(16)

2.8 Math クラスの演算機能

これまで作成してきたプログラムでは,System クラス(java.lang.System)および String クラス (java.lang.String)を使用した。これらの java.lang の基本パッケージの中には,他にも Math クラス (java.lang.Math)など,多数用意されている。Math クラスは,指数関数,対数関数,平方根,およ び三角関数といった基本的な数値処理を実行するためのメソッドを含んでいる。

下記に代表的なフィールドとメソッドを示す。

フィールド 概要および記述

static double E 自然対数の底e に最も近い double 値 Math.E

static double PI 円周とその直径の比π に最も近い double 値 Math.PI

メソッド 概要および記述

static double random() 0 以上 1 未満の擬似乱数を生成し,double 値で返す Math.random()

static double sin(double a) 弧度法で指定した角度a の正弦(sin(a))を返す Math.sin(a)

※ 余弦(cos(a)),正接(tan(a))なども同様 static double exp(double a) 自然対数の底e の a 乗(ea)を返す

Math.exp(a)

static double log(double a) a の自然対数(log(a)=loge(a))を返す

Math.log(a)

static double log10(double a) a の常用対数(log10(a))を返す

Math.log10(a)

static double sqrt(double a) a の値を正しく丸めた正の平方根を返す Math.sqrt(a)

static double〔/float〕 abs(double〔/float〕 a) static int abs(int a)

a の絶対値(|a|)を返す Math.abs(a)

static double pow(double a, double b) a の b 乗(ab)を返す

Math.pow(a, b) static double〔/float〕 max(double〔/float〕 a, double〔/float〕 b)

static int max(int a, int b) static long max(long a, long b)

a,b の値のうち,大きい方を返す Math.max(a, b)

Updating...

参照

Updating...