#include #include #include #include #include #include bool isNormal(char c){ return isalpha(c); } bool isSpace(char c){return c == ' ';} bool isNumber(char c){ return isdigit(c); } bool isSpecial(char c){ return !isSpace(c) && !isNormal(c); } const int state_space = 0; const int state_normal = 1; const int state_special = 2; const int state_number = 3; int stateOf(char c){ if(isSpace(c)){return state_space;} if(isNumber(c)){return state_number;} return isNormal(c)? state_normal: state_special; } std::string specials[] = { "+", "-", "^", "(", ")" }; int elemOfSpecials = sizeof(specials) / sizeof(specials[0]); static void addToken(const std::string & s, int start, int end, std::vector & tokens){ if(isNormal(s[start]) || isNumber(s[start])){ tokens.push_back(s.substr(start, end - start)); return; } int begin = start; while(begin < end){ std::string sub; for(int i = 0; ; i++){ if(i + begin == end){ for(int j = begin; j < end; j++){ std::string t; t += s[j]; tokens.push_back(t); } return; } sub += s[begin + i]; std::string * itr = std::find(specials, specials + elemOfSpecials, sub); if(itr != specials + elemOfSpecials){ tokens.push_back(sub); begin = begin + i + 1; break; } } } } std::vector tokenize(const std::string & s){ std::vector tokens; int state = state_space; int begin = 0; for(int i = 0; i < s.size(); i++){ if(state != stateOf(s[i])){ if(state != state_space){ addToken(s, begin, i, tokens); } begin = i; }else if(state == state_normal){ addToken(s, begin, begin + 1, tokens); begin++; } state = stateOf(s[i]); } if(state != state_space){ addToken(s, begin, s.size(), tokens); } return tokens; } struct Term{ int coeff; std::string factor; Term(const std::string & s){ factor = s; coeff = 1; } Term(const std::string & s, int c){ factor = s; coeff = c; } Term operator + (const Term & t) const{ Term ret = *this; ret.coeff += t.coeff; return ret; } Term operator - (const Term & t) const { Term ret = *this; ret.coeff -= t.coeff; return ret; } Term operator * (const Term & t) const { Term ret = *this; ret.coeff *= t.coeff; ret.factor += t.factor; std::sort(ret.factor.begin(), ret.factor.end()); return ret; } bool operator < (const Term & t) const { return factor < t.factor; } bool operator == (const Term & t) const { return factor == t.factor && coeff == t.coeff; } }; struct State{ std::vector terms; State(){ } State(const std::string & variable, int power){ std::string name; for(int i = 0; i < power; i++){ name += variable; } terms.push_back(Term(name)); } State(int immediate){ if(immediate != 0){ terms.push_back(Term("", immediate)); } } State operator + (const State & s) const { State ret; int i = 0, j = 0; while(true){ if(i == terms.size()){ for(; j < s.terms.size(); j++){ ret.terms.push_back(s.terms[j]); } return ret; } if(j == s.terms.size()){ for(; i < terms.size(); i++){ ret.terms.push_back(terms[i]); } return ret; } if(terms[i].factor == s.terms[j].factor){ Term t = terms[i++] + s.terms[j++]; if(t.coeff != 0){ ret.terms.push_back(t); } }else if(terms[i].factor < s.terms[j].factor){ ret.terms.push_back(terms[i++]); }else /*terms[i].factor> s.terms[j].factor */{ ret.terms.push_back(s.terms[j++]); } } } State operator * (const State & s) const { State temp; for(int i = 0; i < terms.size(); i++){ for(int j = 0; j < s.terms.size(); j++){ temp.terms.push_back(terms[i] * s.terms[j]); } } std::sort(temp.terms.begin(), temp.terms.end()); State ret; for(int i = 0; i < temp.terms.size();){ int j; Term t = temp.terms[i]; int coeff = 0; for(j = i + 1; j < temp.terms.size() && temp.terms[j].factor == temp.terms[i].factor; j++){ t.coeff += temp.terms[j].coeff; } i = j; if(t.coeff != 0){ ret.terms.push_back(t); } } return ret; } bool operator == (const State & s) const { if(terms.size() != s.terms.size()){ return false; } for(int i = 0; i < terms.size(); i++){ if(terms[i] != s.terms[i]){return false;} } return true; } }; std::ostream & operator << (std::ostream & o, const State & s){ if(s.terms.size() == 0){return o << "0";} o << s.terms[0].coeff << s.terms[0].factor; for(int i = 1; i < s.terms.size(); i++){ o << " + " << s.terms[i].coeff << s.terms[i].factor; } return o; } State expression(const std::vector & tokens, int start, int * end); State factor(const std::vector & tokens, int start, int * end){ int i; if(tokens[start] == "("){ State s = expression(tokens, start + 1, &i); if(tokens[i] != ")"){throw std::string("mismatch paren");} *end = i + 1; return s; }else if(isdigit(tokens[start][0])){ State s(atoi(tokens[start].c_str())); *end = start + 1; return s; }else if(isalpha(tokens[start][0])){ int power = 1; *end = start + 1; if(start + 1 < tokens.size() && tokens[start + 1] == "^"){ power = atoi(tokens[start + 2].c_str()); *end = *end + 2; } State s = State(tokens[start], power); return s; }else{ throw std::string("factor error"); } } State term(const std::vector & tokens, int start, int *end){ int i; State s = factor(tokens, start, &i); while(i < tokens.size() && (isalnum(tokens[i][0]) || tokens[i] == "(")){ s = s * factor(tokens, i, &i); } *end = i; return s; } State expression(const std::vector & tokens, int start, int * end){ int i; State s = term(tokens, start, &i); while(i < tokens.size()){ if(tokens[i] == "+"){ State t = term(tokens, i + 1, &i); //std::cout << s << " + " << t << " = " << s + t << std::endl; s = s + t; }else if(tokens[i] == "-"){ State t = term(tokens, i + 1, &i); for(int i = 0; i < t.terms.size(); i++){ t.terms[i].coeff *= -1; } s = s + t; }else{ break; } } *end = i; return s; } int main(){ while(true){ int n = 0; State answer; while(true){ std::string line; int t; std::getline(std::cin, line); if(line == "."){break;} try{ State s = expression(tokenize(line), 0, &t); //std::cout << "s = " << s << std::endl; if(n == 0){ answer = s; }else{ std::cout << (s == answer ? "yes": "no") << std::endl; } n++; }catch(const std::string & s){ std::cout << s << std::endl; } } if(n == 0){break;} std::cout << "." << std::endl; } return 0; }