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

第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
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
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
下記に Stack クラスのコンストラクタと主要メソッドを示す。
コンストラクタ
Stack()
説明
空の Stack を作成します。
public Stack()
空の Stack を作成します。
型
boolean
E
E
メソッド
empty()
peek()
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
2.4 Stack クラスでのキャスト・文字列比較
Stack クラスで格納（push メソッド），取り出し（pop メソッド）ができるが，これらの動作で使用する
String 型変数について説明する。基本型とほぼ同様に使用できるが，String クラスとして定義され
ているため，その扱いに注意が必要となる。
例として，そのキャスト方法について，以下に説明する。
格納できる変数
スタックは Object クラスのものを格納できる．
Object クラスはすべてのクラスに継承されているので，
スタックにはすべてのクラスを格納することができる．
String クラスは Object クラスを継承しているので，
スタックに入れることができる．
取り出しした変数
スタックから取り出した場合，Object クラスとして扱われ，
使用するクラスへの変換（キャスト）が必要となる。
本実習で使用するキャストの例を下記に示す。
（valueOf メソッドを用いた例）
変換型
記述
String 型
String.valueOf(…)
char 型
Character.valueOf(…)
2-5
また，よく使用する例として，String 型での比較（文字列比較）がある。基本データ型では演算子
による比較が可能であるが，String 型は基本データ型でないため，文字列比較を
String 型変数 == ”文字列”
で行うことができない（コンパイルエラーとならないため注意すること）。
そこで，文字列比較には equals メソッドを使用することで比較が可能となる。
データ型
記述例
内容
基本データ型
int x, y;
x と y が等しいなら
（例： int 型）
if(x == y){
…
}
String 型
String st1, st2;
st1 と st2 の変数に格納された文字列が同じなら
if(st1.equals(st2))
（equals メソッド）
String st1, st2;
参照するオブジェクト st1 と st2
if(st1 == st2){
（オブジェクトそのもの）が等しいなら
…
※ この場合は文字列を比較しない
}
2-6
2.5 逆ポーランド記法を用いた文字列処理
2.5.1 逆ポーランド記法の基礎（1 桁の文字に対応する文字の処理）
一般的な電卓の式入力で用いられる 1 + 2 = という方法は中置記法（IN： Infix Notation）であ
り，電卓の制御処理では後置記法（逆ポーランド記法 … RPN： Reverse Polish Notation）に置き
換えて処理が行われる（ちなみに前置記法がポーランド記法 … PN： Polish Notation）。これは，
演算処理において演算子の一つ前と二つ前の数値が演算対象となる構成のため，処理指定を行
いやすいためであり，ポーランド記法→逆ポーランド記法の手動での置き換え方法と，制御構造
例を検討する。
例： 「1 + 2」で示す中置記法は，後置記法では「1 2 +」となる。
記法
中置記法
後置記法
前置記法
記述
1+2
12+
+12
備考
演算子を操作対象の中心に記述する
演算子を操作対象の後に記述する
演算子を操作対象の前に記述する
中置記法（IN）で示す「1 + 2 * 3 + 4」を，手動で後置記法（RPN）に置き換える方法例には下記
がある（簡略的に検討するため，演算子は四則演算記号（+，-，*，/）のみで，括弧など他の記号
は含まない場合）。
手順
算術式置き換え
① 2 * 3 を X と置き換える
1+X+4
② 1 + X を Y と置き換える
Y+4
③ 後置記法に置き換える
Y4+
④ 式 Y の内容を後置記法に置き換える
1X+4+
（1 + X → 1 X +）
⑤ 式 X の内容を後置記法に置き換える
（2 * 3 → 2 3 *）
2-7
123*+4+
上記手順をプログラム処理で制御する場合，スタックを 2 つ使う方法で処理を記述できる。以下
にアルゴリズム（算法，あるいは制御の手順）を示す。
① スタックを 2 つ用意する
（スタック A，スタック B）
② 中置記法の算術式を左から順に 1 項ずつ読み込む
（式を読み込み終わるまで繰り返す）
数字の場合：
スタック A に push
数字以外（演算子）の場合：
ⅰ) スタック B が空でない場合，以下をおこなう
下表の演算子優先順位により，
読み込まれた演算子と，スタック B の最上位要素の演算子の優先順位を比較
優先度 … スタック B の最上位要素の演算子優先順位
（優先度値が大きいほど優先される）
優先度値
演算子
2
*/
1
+-
0
上記以外
読み込まれた演算子の優先順位が高い場合：
スタック B に push し，次のⅱへ進む
読み込まれた演算子の優先順位が低い場合：
スタック B の演算子をスタック A に push し，比較処理に戻る
（スタック 1 が空になればⅱへ進み，空でない限りⅰを繰り返す）
ⅱ) 読み込まれた演算子をスタック B に push
③ 算術式をすべて読み込み処理後，スタック A が空になるまでスタック B へ push
2-8
※ 上図の最後（6）では（スタック B に push された結果）は，スタックの底から見れば逆ポーランド
記法とちょうど逆の並びになっている（この状態であれば，上から順に pop して取り出せる）。
2-9
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.”表示
2-10
2.6 逆ポーランド記法の演算処理
中置記法で記述された算術式を後置記法（逆ポーランド記法）に置き換える処理を行うプログラ
ムを，スタックを用いて作成した。今回は逆ポーランド記法で記述された算術式を元に演算処理を
行わせる制御を追加する。
最初に，逆ポーランド記法（RPN）で記述された式を演算する手順について説明する。
例）
中置記法： 1 + 2 * 3 - 4
↓
後置記法（RPN）： 1 2 3 * + 4 ① 左から順番に項を取り出す
123*+4-
② 数字以外の項（演算子）が取り出されたら，
123*+4-
その前に取り出された 2 項と演算を行う
23*=2*3=6
【演算を行う場合】
左側の数字が演算の先頭項に
なるように注意する。
③ 演算した結果を取り出した 3 項の場所に
16+4-
当てはめて，前の手順（①）に戻る
16+4-
④ すべての項を取り出したら終了する
16+=1+6=7
7474-=7-4=3
上記手順をプログラム処理で制御する場合，逆ポーランド記法での数式がスタック B に既に準
備されているとすると，アルゴリズムは下記となる。
① スタック B が空でないか判定する
② スタック B を pop して，演算子（+ ，- ，*，/）であるか判定する
演算子でない場合：
スタック A に push する
演算子の場合：
スタック A を 2 回 pop して，2 つの double 型変数（d[1]，d[0]）に順に代入する
③ ①で該当した演算子を数式として計算し，結果をスタック A に push する
④ ①の処理を再度おこなう
2-11
この処理を行う場合の，スタックの操作イメージ（演算処理の流れ）を下記に示す。
2-12
2.7 括弧を含む文字列の処理方法
中置記法を後置（逆ポーランド）記法に手動で置き換える方法例には，下記がある。
例）
1*(2+3)
手順
算術式置き換え
① 2 + 3 を Z と置き換える
1*(Z)
② 括弧を外す
1*Z
③ 後置記法に置き換える
1Z*
④ 式 Z の内容を後置記法に置き換える
123+*
（2 + 3 → 2 3 +）
上記手順をプログラム処理で制御する場合，2.5.1 節で示したスタックを 2 つ使う方法に，処理
を追加することで記述できる。
以下にアルゴリズムを示す（ここでは演算子 +，-，*，/ のみ括弧との比較に対応，なお複数桁
の数字にも対応）。
2-13
① スタックを 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
2-14
※ 上図の最後（6）では（スタック B に push された結果）は，スタックの底から見れば逆ポーランド
記法とちょうど逆の並びになっている（この状態であれば，上から順に pop して取り出せる）。
2-15
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)
a の絶対値（|a|）を返す
static int abs(int 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)
a，b の値のうち，大きい方を返す
static int max(int a, int b)
Math.max(a, b)
static long max(long a, long b)
※ 小さい方を返す場合（min(a, b)）も同様
2-16