【 課題 】字句解析・構文木
課題.1 -41 * 53 + (5 + 91) / (23 - (7 + 11)) などのような整数の加減乗除を記述した文字列から 数値や演算子を取り出し、木構造を生成する。 課題.2 上記課題.1で生成された木構造からデータを取り出し、 木構造の表示を行った上で計算結果を表示する。 出力例 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 種のみ、優先順位は 「()」 > 「* /」 > 「+ -」。 同じ順位のものが連続する場合は左、もしくは右から評価する。 (どちらからでも良いが、作成したプログラム中ではどちらかに統一すること)
// 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; } }