字句解析・構文木

【　課題　】字句解析・構文木

	課題．１
	-41 * 53 + (5 + 91) / (23 - (7 + 11))
	などのような整数の加減乗除を記述した文字列から
	数値や演算子を取り出し、木構造を生成する。
	
	課題．２
	上記課題．１で生成された木構造からデータを取り出し、
	木構造の表示を行った上で計算結果を表示する。
	出力例
	calc: -41 * 53 + (5 + 91) / (23 - (7 + 11))
	L[L[L[0]R[41]-]R[53]*]R[L[L[5]R[91]+]R[L[23]R[L[7]R[11]+]-]/]+
	result: -2154
	
	備考
	データの入力は標準入力から一行のみとする。
	便宜上数値は 32bit 符号付整数のみを扱う。
	割り算で商が整数で表せない場合は商の少数以下を切り捨てる。
	木構造は二分木を用い、ノードに演算子、左項をノードの左の子ノード
	右項をノードの右の子ノードとして表現する。項が数値の場合は葉になる
	
	演算子は + - * / の 4 種のみ、優先順位は 「()」 > 「* /」 > 「+ -」。
	同じ順位のものが連続する場合は左、もしくは右から評価する。
	(どちらからでも良いが、作成したプログラム中ではどちらかに統一すること)
	

宿題スレPart54 >>11 (まだバグ・改良の余地あり) †

	
	// Calc.java
	
	import java.io.*;
	
	class Calc{
		static public void main(String[] args){
			CalcTree calctree = new CalcTree();
		}
	}
	
	class Tree{
		char op;
		int data;
		Tree left, right;
	}
	
	class CalcTree{
		final char op_nil = 0;
		final char op_spc = ' ';
		final char op_tab = 9;
		final char op_add = '+';
		final char op_sub = '-';
		final char op_mul = '*';
		final char op_div = '/';
	
		CalcTree(){
			Tree tree;
			int result;
			String str;
			InputStream is = System.in;
			BufferedReader br = new BufferedReader(new InputStreamReader(is));
	
			try{
				System.out.print("calc: ");
				str = br.readLine();
	
				tree = maketree(str, 0);
				viewtree(tree);
				System.out.println("");
	
				System.out.print("result: ");
				result = 0;
				if(tree == null){
					System.out.print("- no tree. - ");
				}else{
					result = calc(tree);
				}
				System.out.println(result);
			}catch(IOException ioe){
				ioe.printStackTrace();
			}
		}
	
		int calc(Tree root){
			int lhs, rhs;
	
			if((root.left == null) && (root.right == null)){
				return root.data;
			}else{
				lhs = calc(root.left);
				rhs = calc(root.right);
				if(root.op == op_add){
					return lhs + rhs;
				}else if(root.op == op_sub){
					return lhs - rhs;
				}else if(root.op == op_mul){
					return lhs * rhs;
				}else if(root.op == op_div){
					return lhs / rhs;
				}else{
					System.out.println("Unexpected function. [" + root.op + "]");
				}
			}
			return 0;
		}
	
		Tree viewtree(Tree root){
			if((root.left == null) && (root.right == null)){
				System.out.print("(" + root.data + ")");
			}else{
				System.out.print("L[");
				viewtree(root.left);
				System.out.print("]");
				System.out.print("R[");
				viewtree(root.right);
				System.out.print("]");
				System.out.print(root.op);
			}
			return root;
		}
	
		Tree growth(char op, int data, Tree lhs, Tree rhs){
			Tree t;
	
			if(lhs == null){
				t = new Tree();
				if(t == null){
					System.out.println("no memory");
					return null;
				}
				lhs = t;
				lhs.op = op_nil;
				lhs.data = data;
				lhs.left = null;
				lhs.right = null;
			}
	
			t = new Tree();
			if(t == null){
				System.out.println("no memory");
				return null;
			}
			t.op = op;
			t.data = 0;
			t.left = lhs;
			t.right = rhs;
	
			return t;
		}
	
		Tree maketree(String str, int p){
			Tree t, s;
			int b, d;
			char c;
	
			t = null;
			d = 0;
	
			for(b = p; b < str.length(); b++){
				c = str.charAt(b);
				if((c >= '0') && (c <= '9')){
					d = c - '0' + d * 10;
				}else if((c == op_add) || (c == op_sub) || (c == op_mul) || (c == op_div)){
					t = growth(c, d, t, maketree(str, b + 1));
					d = 0;
					break;
				}else if((c == op_spc) || (c == op_tab)){
				}else{
					System.out.println("Illegal function. [" + c + "]");
					break;
				}
			}
	
			s = new Tree();
			if(s == null){
				System.out.println("no memory");
				return null;
			}
			s.op = op_nil;
			s.data = d;
			s.left = null;
			s.right = null;
			t = growth('+', 0, t, s);
	
			return t;
		}
	}