Javaの簡単な計算機(式記法変換編)

この記事では二分木を使って中置記法から後置記法へ変換する手順を書きます

ここが一番厄介で考慮することは
計算の優先順位である()をどう扱うかの一点に尽きます

とりあえずコードを

int height = 0;  //かっこの深さの変数
int opPlace = 0;  //演算子の位置を格納する変数

//式の最初と最後を格納する変数
char start;
char finish;

//一時的な変数
char tnp;
String temp;

//空白を読み飛ばすためのトークン
StringTokenizer token;
token = new StringTokenizer(str," ");

//空白を読み飛ばして式を詰める
while(token.hasMoreTokens()){
        temp = token.nextToken();
	formula += temp;
}
        
//式の最初と最後を確認
start = formula.charAt(0);
finish = formula.charAt(formula.length()-1);

//最初と最後でかっこが閉じていれば排除する
int count = 0;
for(int i=0;i<formula.length();i++){
        tnp = formula.charAt(i);
	if(tnp=='('){
		height++;
	}else if(tnp==')'){
		height--;
	}
        if(height==0){
                count++;
        }
}

if(start=='(' && finish==')' && count==1){
        formula = formula.substring(1,formula.length()-1);
}
        
//かっこの外側にある演算子の場所を獲得
for(int i=0;i<formula.length();i++){
        tnp = formula.charAt(i);
	if(tnp=='('){
		height++;
	}else if(tnp==')'){
		height--;
	}else if((tnp=='+' ||
		    tnp=='-' ||
		    tnp=='*' ||
		    tnp=='/') && height==0){
		opPlace = i;
		break;
	}
}

//演算子がなければ数値と考えノードを閉じる
if(opPlace==0){
	left = null;
	right = null;
	return;
}

//演算子の左側を再帰的に呼び出す
temp = formula.substring(0,opPlace);
left = new Node(temp);
left.createTree();

//演算子の右側を再帰的に呼び出す
temp = formula.substring(opPlace+1);
right = new Node(temp);
right.createTree();

//演算子をノードに入れる
str = formula.substring(opPlace,opPlace+1);
}

はい、正直書くのめんどくさいし説明はコメントを見てくださいと言いたいですが...

流れを説明しますと
1.一番外側に()があればそれを外す // (～式～)　の感じ
2.かっこの外側にある演算子の右左で式を分けてその演算子をノードに入れる
3.2で分けた左右の式でそれぞれ再帰を回す
4.演算子がなくなれば(数値のみ)それをノードに入れて終了

流れ1のところでかっこの深さを数えるところで式の整合性を検査しています
このかっこを外すところがとても厄介なのですが説明するのがとても難しい(書くことが多すぎて)ので各自書いてみるときにでも考えてください. 一部はコード中コメントを読めばわかります

上のコードで二分木を作成したのであとは後順走査をするだけです

String traceTree(){
        String s="";
	String t="";
	if(left != null) s += left.traceTree()+" ";
	if(right != null) t += right.traceTree()+" ";
	return s + t + str;
}

さてこれでstackマシン編で分けた仕事の2,3,4,5までの(ここでは仕事2)を書いてきたわけですが, あとはMainに仕事をMainに並べるだけです. なのでMainは割愛とさせていただきます(仕事1の入力はどこでも使うから頑張って).

理念も何もない見苦しいコードを載せてもうしわけないです. 少しでも参考になれば幸いです. ここまで読んでくれた方お疲れさまでしたこれにて「Javaの簡単な計算機」は終わりとなります.

ね、簡単でしょ？