AOJ 1155

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155&lang=jp

構文解析おもしろいじゃーん。

関数の返し値をpair ( (値),(どこまで解析したか) )にして、引数を(どこから解析するか)にすれば簡単に実装できます。
今回は
formula:=-formula|(formula*formula)|(formula+formula)|0|1|2|P|Q|R
となっていて、左再帰がないので本当にそのまま実装すればいいです。

string str;
int neg[3] = {2, 1, 0};
int mul[3][3] = {
	{0, 0, 0},
	{0, 1, 1},
	{0, 1, 2}
};
int add[3][3] = {
	{0, 1, 2},
	{1, 1, 2},
	{2, 2, 2}
};

int A[3];

pi formula(int at);
pi two(int at);

pi formula(int at) {
	if(str[at] == '-') {
		pi p = formula(at + 1);
		p.fst = neg[p.fst];
		return p;
	}
	else if(str[at] == '(') {
		pi p1 = formula(at + 1);
		pi p2 = formula(p1.sec + 1);
		if(str[p1.sec] == '*') {
			return pi(mul[p1.fst][p2.fst], p2.sec + 1);
		}
		else {
			return pi(add[p1.fst][p2.fst], p2.sec + 1);
		}
	}
	else if('0' <= str[at] && str[at] <= '2'){
		return pi(str[at] - '0', at + 1);
	}
	else {
		return pi(A[str[at] - 'P'], at + 1);
	}
}

void solve() {
	while(true) {
		cin >> str;
		if(str == ".") break;
		int cnt = 0;
		rep(i, 0, 3) {
			rep(j, 0, 3) {
				rep(k, 0, 3) {
					A[0] = i;
					A[1] = j;
					A[2] = k;
					if(formula(0).fst == 2) cnt++;
				}
			}
		}
		cout << cnt << "\n";
	}
}