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"; } }