AOJ 2255

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

優先順位が低い演算子から再帰していく感じでやればいいです。例えば演算子の優先順位が(),/,*,-,+だったら、

expr0::=expr0 + expr0 | expr1
expr1::=expr1 - expr1 | expr2
expr2::=expr2 * expr2 | expr3
expr3::=expr3 / expr3 | expr4
expr4::=(expr0) | num
のようにすればいいです。左再帰を解消すると、
expr0::=expr1 + expr0'
expr0'::=+ expr0 expr0' | empty
のようになって、LL(1)になるので簡単に実装できます。

int K;
string str;
string strs;
int signat[20];
char csign[4] = {'+', '-', '*', '/'};

pi expr(int type, int at);
pi num(int at);

pi expr(int type, int at) {
	if(type == K) {
		if(str[at] == '(') {
			pi p = expr(0, at + 1);
			p.sec++;
			return p;
		}
		else {
			pi p = num(at);
			return p;
		}
	}
	else {
		pi p1 = expr(type + 1, at);
		if(p1.sec < sz(str) && str[p1.sec] == char(type + 'a')) {
			pi p2 = expr(type + 1, p1.sec + 1);
			if(p1.fst == inf || p2.fst == inf) return pi(inf, p2.sec);
			if(strs[p1.sec] == '+') {
				return pi(p1.fst + p2.fst, p2.sec);
			}
			else if(strs[p1.sec] == '-') {
				return pi(p1.fst - p2.fst, p2.sec);
			}
			else if(strs[p1.sec] == '*') {
				return pi(p1.fst * p2.fst, p2.sec);
			}
			else {
				if(p2.fst == 0) return pi(inf, p2.sec);
				else return pi(p1.fst / p2.fst, p2.sec);
			}
		}
		else return p1;
	}
}

pi num(int at) {
	int res = 0;
	while('0' <= str[at] && str[at] <= '9') {
		res *= 10;
		res += (str[at] - '0');
		at++;
	}
	return pi(res, at);
}

void solve() {
	while(true) {
		cin >> str;
		strs = str;
		if(str == "#") break;
		K = 0;
		rep(i, 0, sz(str)) {
			rep(j, 0, 4) {
				if(str[i] == csign[j]) {
					signat[K++] = i;
				}
			}
		}
		vector<int> vec(K, 0);
		rep(i, 0, K) vec[i] = i;
		set<int> S;
		do {
			rep(i, 0, K) {
				str[signat[i]] = char('a' + vec[i]);
			}
			S.insert(expr(0, 0).fst);
		} while(next_permutation(all(vec)));
		if(S.count(inf)) cout << sz(S) - 1 << "\n";
		else cout << sz(S) << "\n";
	}
}