#include #include #include #include #include #include #include #include #include typedef map expr_t; void disp(expr_t); int strtoint(string s) { istringstream in(s); int n; in >> n; return n; } expr_t expr_NUM(int n) { expr_t expr; expr[""] = n; return expr; } expr_t expr_TERM(char c, int exp) { expr_t expr; expr[string(exp, c)] = 1; return expr; } string normalize(string s) { sort(s.begin(), s.end()); return s; } expr_t operator +(expr_t x, expr_t y) { expr_t::iterator p = y.begin(); while(p != y.end()) { x.insert(make_pair(p->first, 0)); x[p->first] += p->second; p++; } return x; } expr_t operator -(expr_t x, expr_t y) { expr_t::iterator p = y.begin(); while(p != y.end()) { x.insert(make_pair(p->first, 0)); x[p->first] -= p->second; p++; } return x; } expr_t operator *(expr_t x, expr_t y) { expr_t z; expr_t::iterator p, q; for(p = x.begin(); p != x.end(); p++) { for(q = y.begin(); q != y.end(); q++) { z[normalize(p->first + q->first)] = p->second * q->second; } } disp(x); disp(y); disp(z); return z; } expr_t normalize2(expr_t x) { expr_t y; expr_t::iterator p = x.begin(); while(p != x.end()) { if(p->second != 0) { y.insert(*p); } p++; } return y; } void disp(expr_t x) { expr_t::iterator p = x.begin(); while(p != x.end()) { if(p->second != 0) { cout << p->first << " " << p->second << endl; } p++; } } expr_t generate(queue &tokens) { stack expr_stack; stack subtract; expr_t expr = expr_NUM(1); while(!tokens.empty()) { string tok = tokens.front(); tokens.pop(); if(tok == "+" || tok == "-") { expr_stack.push(expr); subtract.push(tok == "-"); expr = expr_NUM(1); } else if(tok == "(") { expr = expr * generate(tokens); } else if(tok == ")") { break; } else if(tok[0] >= 'a' && tok[0] <= 'z') { if(!tokens.empty()) { if(tokens.front() == "^") { tokens.pop(); expr = expr * expr_TERM(tok[0], strtoint(tokens.front())); tokens.pop(); } } else { expr = expr * expr_TERM(tok[0], 1); } } else { expr = expr * expr_NUM(strtoint(tok)); } } while(!expr_stack.empty()) { if(subtract.top()) { expr = normalize2(expr_stack.top() - expr); } else { expr = normalize2(expr_stack.top() + expr); } expr_stack.pop(); subtract.pop(); } return expr; } void parse(queue &tokens, string line) { while(!tokens.empty()) tokens.pop(); int p, q = 0; for(p = 0; p < line.length(); p++) { if(!isdigit(line[p])) { if(p != q) { tokens.push(line.substr(q, p - q)); } if(line[p] != ' ') { tokens.push(string(1, line[p])); } q = p + 1; } } if(q != line.length()) { tokens.push(line.substr(q, line.length() - q)); } } int main(void) { ifstream in("expressions.txt"); string line; queue tokens; while(getline(in, line)) { if(line == ".") break; parse(tokens, line); expr_t f = generate(tokens); while(getline(in, line)) { if(line == ".") break; parse(tokens, line); expr_t g = generate(tokens); cout << ((f == g) ? "yes" : "no") << endl; } cout << "." << endl; } return 0; }