AOJ 1233 Equals are Equals
問題
文字列からなる式が与えられる。
最初の式と、二つ目以降の式が等しいかをyesまたはnoで出力せよ。
制約条件
式の長さ≦80
係数はintの範囲に収まる
指数部は自然数
ソースコード
typedef map<vi, ll> E; E operator*(const E &a, const E &b){ E res; fr(i, a) fr(j, b){ vi v(26); rep(k, 26) v[k] = (i->first)[k] + (j->first)[k]; res[v] += i->second * j->second; } return res; } E expr(), term(), factor(), primary(); int p, len; string in, token; void next(){ token = ""; while(p < len && isspace(in[p])) p++; if(p < len){ if(isdigit(in[p])) while(isdigit(in[p])) token += in[p++]; else token += in[p++]; } } ll number(){ ll res = 0; rep(i, token.size()){ res *= 10, res += token[i] - '0'; } next(); return res; } E expr(){ E res; do{ bool plus = token != "-"; if(!res.empty()) next(); E t = term(); if(plus){ fr(i, t) res[i->first] += i->second; } else{ fr(i, t) res[i->first] -= i->second; } }while(token == "+" || token == "-"); return res; } E term(){ E res; vi v(26); res[v] = 1; do{ E f = factor(); res = res * f; }while(!token.empty() && token != "+" && token != "-" && token != ")"); return res; } E factor(){ E p = primary(); if(token != "^") return p; next(); ll n = number(); E res; res[vi(26)] = 1; rep(i, n) res = res * p; return res; } E primary(){ E res; if(isdigit(token[0])){ ll n = number(); res[vi(26)] = n; return res; } if(isalpha(token[0])){ vi v(26); v[token[0] - 'a'] = 1; res[v] = 1; next(); return res; } next(); res = expr(); next(); return res; } E parse(){ p = 0; len = in.size(); next(); E e = expr(), f; fr(i, e) if(i->second) f[i->first] = i->second; return f; } int main() { while(getline(cin, in), in != "."){ E e = parse(); while(getline(cin, in), in != ".") puts(e == parse() ? "yes" : "no"); puts("."); } return 0; }