AOJ 1322 ASCII Expression

問題

2次元で与えられた分数と累乗を含む式をmod2011で計算せよ。
詳しい文法はBNF記法で与えられる。

制約条件

式は20行以下
各行は80文字以下

方針

普通の構文解析っぽくやればいい。
分数の分子と分母は、--------の線の厳密に内側に入っているので結構やりやすい。

いつもの構文解析っぽく、今まで終わった文字数をグローバル変数のpとして持つと、
解析ができないので、関数の引数に(左, 上), (右, 下)の座標を持たせてやる。
引数を参照型にして、終わったところを伝播させる。

ソースコード

const int mod = 2011;
int pow(int n, int m){
	int res = 1;
	for(; m; m /= 2){
		if(m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}
int inv(int n){
	return pow(n, mod - 2);
}

int n;
string in[20];
int expr(int&, int&, int&, int&);


int f(int y, int x, int Y, int X){
	int res = -1;
	for(int i = y; i < Y; i++) if(in[i][x] != '.'){
		res = res == -1 ? i : -2;
	}
	return res;
}
int powexpr(int &y, int &x, int &Y, int &X){
	int p, res;
	while(x < X && (p = f(y, x, Y, X)) < 0) x++;
	if(in[p][x] == '('){
		x++;
		res = expr(y, x, Y, X);
		x++;
	}
	else{
		res = 0;
		while(x < X && isdigit(in[p][x])) res *= 10, res += in[p][x++] - '0';
	}
	if(x < X){
		p = f(y, x, Y, X);
		if(p >= 0){
			int e = 0;
			while(x < X && isdigit(in[p][x])) e *= 10, e += in[p][x++] - '0';
			res = pow(res, e);
		}
	}
	return res;
}
int factor(int &y, int &x, int &Y, int &X){
	int p;
	bool sign = 0;
	while(1){
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		if(x + 1 < X && in[p][x] == '-' && in[p][x + 1] == '.') sign ^= 1, x += 2;
		else break;
	}
	if(x + 1 < X && in[p][x] == '-' && in[p][x + 1] == '-'){
		int q = x;
		while(q < X && in[p][q] == '-') q++;
		
		int a = y, b = x + 1, c = p, d = q - 1;
		int num = expr(a, b, c, d);
		
		a = p + 1, b = x + 1, c = Y, d = q - 1;
		int den = expr(a, b, c, d);
		
		num = num * inv(den) % mod;
		x = q + 1;
		return sign ? (mod - num) % mod : num;
	}
	return ((sign ? -1 : 1) * powexpr(y, x, Y, X) % mod + mod) % mod;
}
int term(int &y, int &x, int &Y, int &X){
	int res = inf, p;
	while(1){
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		int a = factor(y, x, Y, X);
		res = res == inf ? a : (a * res) % mod;
		p = 0;
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		if(p < 0 || x >= X || in[p][x] != '*') break;
		x++;
	}
	return res;
}
int expr(int &y, int &x, int &Y, int &X){
	int res = 0, p, op = 0;
	while(1){
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		int a = term(y, x, Y, X);
		(res += op ? mod - a : a) %= mod;
		p = 0;
		while(x < X && (p = f(y, x, Y, X)) < 0) x++;
		if(p < 0 || x >= X || in[p][x] != '+' && in[p][x] != '-') break;
		op = in[p][x] == '-';
		x++;
	}
	return res;
}

int main(){
	while(cin >> n, n){
		rep(i, n) cin >> in[i];
		int y = 0, x = 0, Y = n, X = in[0].size();
		cout << expr(y, x, Y, X) << endl;
	}
	return 0;
}