このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
FILO(First In Last Out) あるいは LIFO(Last In First Out)とは、データ処理の順番として、一番最後 に来たものから順に遡って処理をするという意味です。 そして、これを実現するデータ構造をスタックと言います。 スタックにデータを入れることを pushと言い、データを取り出す ことを popと言います。 また、データを入れる位置と取り出す位置は常に同じ位置になりますが、そこ を指すポインタをスタックポインタと言います。 スタックも直線的にデータを並べれば実現できます。 容量の制限があってもよい場合は配列、容量の制限が無い方がいい場合は線形 リストを使って実現します。
スタックを配列で実装した例を示します。
class Stack<E> {
private E[] array;
private int stackpointer;
public Stack(int n){
@SuppressWarnings({"unchecked"})
array = (E[])(new Object[n]);
stackpointer = -1;
}
public void push(E obj){
array[++stackpointer] = obj;
}
public E pop(){
E obj = array[stackpointer];
array[stackpointer]=null; // ※1
stackpointer--;
return obj;
}
public boolean isEmpty(){
return stackpointer <0;
}
}
class Rei {
public static void main(String[] arg){
Stack<Integer> s = new Stack<Integer>(10);
s.push(1);
s.push(2);
System.out.println(s.pop());
s.push(3);
s.push(4);
while(!s.isEmpty()){
System.out.println(s.pop());
}
}
}
※1 で null を代入しているのは、テクニカルな話になります。 Java にはガベージコレクションという仕組が内蔵されています。 これは、使用していないオブジェクトを廃棄し、占有していたメモリーを再利 用可能にする仕組です。 ガベージコレクションは C や C++ には含まれていません。 そのため、 C や C++ ではオブジェクトの管理では廃棄まで行わなければなり ません。 C 言語では malloc 関数を使用してメモリーを取得したら、そのメモリーを free 関数で開放する必要があります。 C++ ではオブジェクトは new をしたら、 delete しなければなりません。 また、オブジェクトは delete されると、デストラクタと呼ばれ るメソッドが呼び出されます。 そのメソッドで、オブジェクト自身が内部で生成した他のオブジェクトを delete しなければなりません。 このように free や delete をしないと、プログラムが実行している間にメモ リーを不要に占有してしまうことになります。 これを メモリーリーク と呼びます。 メモリーリークはプログラムのコンパイルやテストで見付けづらい重大なプロ グラミングミスです。 そのため、プログラミングを行う際は、メモリーの管理には細心の注意をはら う必要があります。
一方、 Java ではどの変数からも参照されないようなオブジェクトは自動的に 消されます。 そのため、単純に考えれば Java ではメモリーリークは起きにくいと考えられ ます。 しかし、上記のスタックの例では注意をする必要があります。 スタックはデータを入れて、取り出す仕組です。そして一度取り出したデータ は二度と取り出しません。 配列でスタックを実装した場合、(1)データ A を push し、 (2) pop し、(3) そしてデータ B を push すると、データ A とデータ B は配列において同一 の添字の部分から参照されます。 これを仮りに array[k] とします。 このとき、素朴な手法ではメモリー管理に問題が生じます。 データA を pop する手順 (2) 以降で、データ A を使用し、データ A が不要 になったとします。 不要になるとは、データ A を pop する際に受け取った変数に別の参照が与え られたり、または変数を使用する関数が終了するなどスコープから外れるなど することです。 このとき通常はデータ A はガベージコレクションの対象になり、占有してい たメモリーは開放されます。
{
Object data = s.pop();
System.out.println(data);
...
} //← ガベージコレクションが起きるはず
ところが、上記の (2) の pop において、素朴に array[k] から値を取り出す ような pop のメソッドを実装したとします。
public E pop(){
return array[stackpointer--];
}
このような実装すると、次に push されるまで、 array[k] はデータ A を参 照しつづけることになります。 つまり、使用し、不要になった時点で本来はガベージコレクションにより廃棄さ れるはずのデータが廃棄されないことが発生します。 Java でのこのようなメモリーリークに対応するには、データが不要になる際に変 数に null を与えて参照を切ります。 するとデータの処理が終了し、全ての変数からの参照が無くなった時点でデー タが廃棄されます。
Java には java.util.Stack がありますが、これは古いクラスなため使用は推 奨されていません。 現在は java.util.Deque インターフェイスのサブクラスである ArrayDeque, LinkedBlockingDeque, LinkedList の利用が推奨されています。 この deque(デック) というのは先頭と最後に対して要素の追加、 取り出し、削除が行えるデータ型で 両端キューと呼ばれています。 そのため、スタックとして操作するには push, pop の代りに、それぞれ addFirst, removeFirst というメソッドを使います。
スタックは、式やプログラムの解釈と密接な関係がありとても重要です。 サブルーチンを呼び出す時などに利用されます。 一方、式の処理にも利用されています。
まずカッコの処理について考えてみます。 カッコの処理の基本として正しく閉じているか閉じてないかを判断することを 考えます。 カッコが一種類だけなら、スタックを使わずとも、整数変数を一つ用意して、 開きカッコで数を足し、閉じカッコで数を減らしていき、一回もマイナスにな らずに最後 0 で終るかどうか判断することで処理できます。
以下は、行毎に括弧の数えるプログラムです。 parseLine では行を java.io.StringReader に変換します。そして read で一 文字ずつ読んでいきます。 なお、 read では戻り値は int なので、比較する際には文字列では無く文字 として比較を行います。 文字が '(' ならカウンターを加算します。 一方文字が ')' ならカウンターを減算します。 そして、入力が終了した時点で、カウンターが一度も負にならず、 0 で終了 すれば括弧の対応が取れていることになります。 括弧の対応が取れてないとは、(1)行を読んでいる途中でカウンターが負になっ たか (2)行が終了してもカウンターが 0 にならなかったのいずれかになりま す。
さて、括弧の対応が取れていないというのは行が読み終わったとき以外にも、 行の途中でも判明します。 これは処理中のエラーとしてみなすことができるので、 Java の例外処理の 仕組を使うとプログラムがシンプルになります。 そこで、既存の例外クラスから似たような意味を表す例外を選び、使用する例 外クラスを新たに継承して作成します。 そして、処理中で不都合が生じた場合に例外を生成して throw します。 すると、不都合が起きたときの処理を一元処理できます。
import java.io.*;
class ParenthesisException extends IllegalArgumentException {
public ParenthesisException(String arg){
super(arg);
}
}
class Rei {
private static boolean parseLine(String line) throws IOException {
StringReader sr = new StringReader(line);
int input;
int counter=0;
boolean result = false;
try{
while((input = sr.read())!=-1){
switch(input){
case '(':
counter++;
break;
case ')':
counter--;
if(counter<0){
throw new ParenthesisException("few '('");
}
break;
}
}
if(counter!=0){
throw new ParenthesisException("many '('");
}
result = true;
}catch(ParenthesisException e){
result = false;
}finally{
sr.close();
}
return result;
}
public static void main(String[] arg) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in));
String line;
while((line = br.readLine())!=null){
if(parseLine(line)){
System.out.println("Ok");
}else{
System.out.println("NG");
}
}
}
}
このように単一の括弧の処理は括弧数を計算するだけで処理できます。 しかし、 HTML や XML のタグのように対応する開始タグと終了タグの種類が 多い場合どうすれば良いでしょうか? この場合、閉じカッコは一番近い開きカッコに対応するということを利用しま す。 スタックを用意し、開きカッコがあったらスタックに開き括弧を push し、閉 じカッコが出現したらスタックから開きカッコを pop して対応しているかを 調べます。 こうすると一番近い同士の開き括弧と閉じ括弧の対応を検査でき、また検査が 終わった括弧はスタックから取り除かれるので、取り除いた残りの部分でまた 検査を行うことができます。
なお、開きタグと閉じタグの文法は次のようになっています。
この文法を踏まえ、開きタグと閉じタグの対応を確認するプログラムを示しま す。スタックには要素名を指す文字のポインタを入れます。 なお、このプログラムでは要素名を解釈中かそうでないかで、処理を切替える ために、状態を保持するフラグという手法を使っています。
はじめに、タグの名前を順番に得るオブジェクトのクラスを作ります。 但し、正確にタグを抽出するのではなく、簡単のために '<' の後の英数字 または '/' の列を取り出すことを考えます。 '<' が無いうちは入力を読み飛ばします。そして、 '<' を見付けたら フラグ inside を切替えてタグ名を取得する処理にします。 タグ名が終了したら文字列として返します。 なお、入力ファイルが終了した場合、タグ名を収集していない状況であれば、 そのまま終了できますが、もしタグ名を収集している状況であれば終了せずに 収集しているタグ名を返す必要があります。 但し、再びタグ名を要求された場合は今度は終了する必要があります。 そのため、終了するか否かを決めるフラグ end を別に用意します。
import java.io.*;
class Parser {
Reader r;
public Parser(Reader r){
this.r = r;
end=false;
}
private static boolean end;
public String getTagName() throws IOException{
if(end){
return null;
}
int input;
boolean inside = false;
StringBuilder sb = new StringBuilder();
while((input = r.read())!=-1){
if(!inside){
if(input=='<'){
inside = true;
}
}else{
if(Character.isLetterOrDigit(input)||input=='/'){
sb.appendCodePoint(input);
}else{
return sb.toString();
}
}
}
end=true;
if(inside){
return sb.toString();
}
return null;
}
}
class Test {
public static void main(String[] arg) throws IOException {
Parser p = new Parser(new InputStreamReader(System.in));
String tag;
while((tag=p.getTagName())!=null){
System.out.println(tag);
}
}
}
次に、開きタグが来たら push(addFirst) し、閉じタグが来たら pop(removeFirst)して照合するプログラムを作ります。
import java.util.*;
class UnmatchTagException extends IllegalArgumentException {
public UnmatchTagException(String arg){
super(arg);
}
}
class Rei {
public static void main(String[] arg) throws IOException {
Parser p = new Parser(new InputStreamReader(System.in));
String tag;
LinkedList<String> stack = new LinkedList<String>();
try{
while((tag=p.getTagName())!=null){
if(tag.startsWith("/")){
if(!stack.removeFirst().equals(tag.substring(1))){
throw new UnmatchTagException(tag);
}
}else{
stack.addFirst(tag);
}
}
if(!stack.isEmpty()){
throw new UnmatchTagException(stack.removeFirst());
}
System.out.println("Ok");
}catch(UnmatchTagException e){
System.out.println("NG");
}
}
}
なお、実際の HTML や XML は全てのタグが閉じているわけではありません。 HTML、 XML とも DOCTYPE 宣言 <!DOCTYPE ... > という終了タ グのないタグを冒頭に置きますので、上記のプログラムでは不十分です。 さらに、 HTML では開始タグや終了タグを省略できます。一方 XML では基本的 に終了タグは省略できませんが、 <hr /> のように最後に / を付けて 開始タグと終了タグを兼用出来ます。 したがって、これらに対応しないチェックプログラムは実用的ではありません。 なお、XML への対応はそれなりに簡単にできますが、 HTML 対応はかなり複雑 になります。
次に、数式を考えます。 数式は数と演算子と呼ばれるものからできています。 +,-,*,/ など我々が使う演算子は、通常、その演算子をはさむ両方の値に対し て計算を行い、答を出します。 その際、どのような順番で計算しても良いわけではなく、各演算子には優先順 位があります。 また、数式はカッコを利用して演算の順序を指定できます。 例えば、 2*3+4*5 を考えた時、これは ((2*3)+(4*5))と同じ意味になります。 これは演算子の優先順位を考慮すれば冗長な表現ですが、一方で厳密に演算の 順序を定めていることになります。 このように厳密に演算順序をカッコにより定められた式は、各カッコの中の値 を順に計算していけば全体の式の値を計算することができます。
ここで、カッコつきの演算を抽象的に考えてみます。 演算子というのは両隣の値から一つの値を計算するものなので、これは二つの 引数を持つ関数と考えることができます。 つまり、 (2*3) は 2 と 3 が引数になるわけです。 いまのところカッコの中は数が 2 つと演算子がひとつという関係です。 そこで、演算子が真中にあるという書き方の他に、先頭に置くという方式と、 最後に置くと言う方式も考えられます。
このうち注目したいのは逆ポーランド記法です。 これは、演算子が閉じカッコの前にあります。 そのため、 演算子が現れたら、直前の二つの値に対して計算をして、カッコの中の値を求 めます。 演算子の直後でカッコが閉じるということは、カッコの内側から計算するには、 最も最初に計算しなければならない演算子から順番に現れることを意味します。 そのため、逆ポーランド記法では一番内側のカッコから自然に計算が出来ます。 さらに、演算子の直後に必ず閉じ括弧があるということを利用すると、逆ポーランド記 法では演算子の優先順位を決めなくても、カッコ無しの式で計算の順序に曖昧 さは生じません。 つまり 2 3 * 4 5 * + と書いても正しく計算が可能です。
さらに逆ポーランド記法に対しては、左から式を見ていき、演算子が現れたら一番近い二 つの値に対して計算を行えばいいので、スタックを利用すれば計算が出来ます。
逆ポーランド記法を(足し算だけ)計算するプログラムを以下に示します。
import java.util.*;
import java.io.*;
class Rei {
public static void main(String[] arg) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
while((line = br.readLine())!=null){
Scanner sc = new Scanner(line);
LinkedList<Integer> stack = new LinkedList<Integer>();
while(sc.hasNext()){
if(sc.hasNextInt()){
stack.addFirst(sc.nextInt());
}else if(sc.hasNext("=")){
System.out.println(stack.removeFirst());
break;
}else if(sc.hasNext("\\+")){
sc.next();
stack.addFirst(stack.removeFirst()+stack.removeFirst());
}
}
sc.close();
}
}
}
(){}[] が含まれる数式などに対して、括弧が正常に閉じられているかをチェッ クするプログラムを作成しなさい。
例12-4のプログラムを改造してかけ算も計算できるようにしなさい。 そして、 2 3 * 4 5 * + が正しく計算できるか確かめなさい。
1+2×3= と押すと 9 が出るような普通の電卓を作成しなさい。