構文解析(Syntactic Analysis)

()ありの四則演算するだけのやつ
トップダウン構文解析で解く。
BNFで書くと
::= |
::= |
::= '(' ')' |
::= '+' | '-'
::= '*' | '/'
左再帰を取り除くと
::=
::= | ε
::=
::= | ε
::= '(' ')' |
::= '+' | '-'
::= '*' | '/'
末尾再帰はループで書ける
::= { }
::= { }
::= '(' ')' |
::= '+' | '-'
::= '*' | '/'
{}は0回以上の繰り返し
※使用しない文字のデリミタ(終端文字)を入れとく(=とか)。
それが嫌ならleft.str[pos], str[left.pos]とアクセスしているところでレンジ内かどうかを確認する。

public static class Result{
	int value, pos;
	Result(int value, int pos){this.value = value; this.pos = pos;}
}
public static Result equation(char[] str, int pos){
	Result left = factor(str, pos);
	while(str[left.pos] == '+' || str[left.pos] == '-'){
		Result right = factor(str, left.pos+1);
		if(str[left.pos] == '+') left.value += right.value;
		else left.value -= right.value;
		left.pos = right.pos;
	}
	return left;
}
private static Result factor(char[] str, int pos){
	Result left = term(str, pos);
	while(str[left.pos] == '*' || str[left.pos] == '/'){
		Result right = term(str, left.pos+1);
		if(str[left.pos] == '*') left.value *= right.value;
		else left.value /= right.value;
		left.pos = right.pos;
	}
	return left;
}
private static Result term(char[] str, int pos){
	if(str[pos] == '('){
		Result res = equation(str, pos+1);
		assert str[res.pos] == ')';
		res.pos += 1; //skip ')'
		return res;
	}else{
		int value = 0;
		while(Character.isDigit(str[pos]))
			value = value * 10 + (str[pos++] - '0');
		return new Result(value, pos);
	}
}