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

Size: px

Start display at page:

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

たつぞうぜんじゅう
5 years ago
Views:

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-1

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

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 というクラスがある 2-3

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>(); のように型指定で記述する ( 但し配列は不可 ) 2-4

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

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

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

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

9 上図の最後 (6) では ( スタック B に push された結果 ) は, スタックの底から見れば逆ポーランド記法とちょうど逆の並びになっている ( この状態であれば, 上から順に pop して取り出せる ) 2-9

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

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

12 この処理を行う場合の, スタックの操作イメージ ( 演算処理の流れ ) を下記に示す 2-12

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

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

15 上図の最後 (6) では ( スタック B に push された結果 ) は, スタックの底から見れば逆ポーランド記法とちょうど逆の並びになっている ( この状態であれば, 上から順に pop して取り出せる ) 2-15

16 2.8 Math クラスの演算機能これまで作成してきたプログラムでは,System クラス (java.lang.system) および String クラス (java.lang.string) を使用したこれらの java.lang の基本パッケージの中には, 他にも Math クラス (java.lang.math) など, 多数用意されている Math クラスは, 指数関数, 対数関数, 平方根, および三角関数といった基本的な数値処理を実行するためのメソッドを含んでいる下記に代表的なフィールドとメソッドを示すフィールド static double E static double PI 概要および記述自然対数の底 e に最も近い double 値 Math.E 円周とその直径の比 π に最も近い double 値 Math.PI メソッド static double random() static double sin(double a) static double exp(double a) static double log(double a) static double log10(double a) static double sqrt(double a) static double /float abs(double /float a) static int abs(int a) static double pow(double a, double 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) 概要および記述 0 以上 1 未満の擬似乱数を生成し,double 値で返す Math.random() 弧度法で指定した角度 a の正弦 (sin(a)) を返す Math.sin(a) 余弦 (cos(a)), 正接 (tan(a)) なども同様自然対数の底 e の a 乗 (e a ) を返す Math.exp(a) a の自然対数 (log(a)=log e (a)) を返す Math.log(a) a の常用対数 (log 10 (a)) を返す Math.log10(a) a の値を正しく丸めた正の平方根を返す Math.sqrt(a) a の絶対値 ( a ) を返す Math.abs(a) a の b 乗 (a b ) を返す Math.pow(a, b) a,b の値のうち, 大きい方を返す Math.max(a, b) 小さい方を返す場合 (min(a, b)) も同様 2-16

Microsoft Word - CompA-Ex doc

Microsoft Word - CompA-Ex doc コンパイラ演習参考資料 2008/09/23 担当 : 佐々木晃算術式の処理と逆ポーランド記法 ( 第一回スライド 29 ページ ) (1) 実数値 (double の値 ) を格納するスタックを実装せよ ( 配列やリストを使うとよい ) (2) 逆ポーランド記法によって実数値の算術演算を行う計算機のプログラムを作成せよ演算子や被演算子の各要素同士は空白で区切られるものとする (a) 四則演算のみなお

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

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