POJ 1686 - Lazy Math Instructor

http://poj.org/problem?id=1686

概要

• 一文字のアルファベットの変数 (case insensitive)
• 一文字の数値
• 括弧 (左右の対応は正しいと仮定してよい)
• 二項演算子 (優先順位はすべて同じで左結合とする)

からなる数式が2つ与えられるので、それらが数式として等しいかどうかを答える。

注意

• 数式中の任意の位置に空白またはタブ文字がありうる

解法

かけ算があるため、真面目に文字式として等しいかどうかチェックするのは大変なので、 適当な乱数を何度か代入してみて等しいかどうかをチェックして済ませる。

  1 #include <iostream>
  2 #include <algorithm>
  3 using namespace std;
  4 
  5 bool ws_p(char c) { return c == ' ' || c == '\t'; }
  6 bool digit_p(char c) { return '0' <= c && c <= '9'; }
  7 bool op_p(char c) { return c == '+' || c == '-' || c == '*'; }
  8 
  9 typedef string::const_iterator Iterator;
 10 
 11 struct expr
 12 {
 13   char c;
 14   int n;
 15   expr *l, *r;
 16   expr(int x) : c(0), n(x), l(0), r(0) {}
 17   expr(char x) : c(x), n(0), l(0), r(0) {}
 18   expr(char o, expr *a, expr *b) : c(o), n(0), l(a), r(b) {}
 19   ~expr() { delete l; delete r; }
 20   int eval(const int *env) const
 21   {
 22     switch (c) {
 23       case 0: return n;
 24       case '+': return l->eval(env) + r->eval(env);
 25       case '-': return l->eval(env) - r->eval(env);
 26       case '*': return l->eval(env) * r->eval(env);
 27       default:  return env[c-'a'];
 28     }
 29   }
 30 };
 31 
 32 expr *parse_expr(Iterator& it, const Iterator& last);
 33 
 34 expr *parse_term(Iterator& it, const Iterator& last)
 35 {
 36   if (*it == '(') {
 37     ++it;
 38     expr *e = parse_expr(it, last);
 39     if (*it != ')') {
 40       throw ")";
 41     }
 42     ++it;
 43     return e;
 44   } else if (digit_p(*it)) {
 45     expr *e = new expr(int(*it-'0'));
 46     ++it;
 47     return e;
 48   } else {
 49     expr *e = new expr(char(*it));
 50     ++it;
 51     return e;
 52   }
 53 }
 54 
 55 expr *parse_expr(Iterator& it, const Iterator& last)
 56 {
 57   expr *l = parse_term(it, last);
 58   while (it != last && op_p(*it)) {
 59     char op = *it;
 60     ++it;
 61     expr *r = parse_term(it, last);
 62     l = new expr(op, l, r);
 63   }
 64   return l;
 65 }
 66 
 67 struct xorshift
 68 {
 69   unsigned x, y, z, w;
 70   xorshift() : x(123456789), y(362436069), z(521288629), w(88675123) {}
 71   unsigned operator()()
 72   {
 73     unsigned t = x ^ (x << 11);
 74     x = y; y = z; z = w;
 75     return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))) % 100;
 76   }
 77 };
 78 
 79 bool same_p(expr *a, expr *b)
 80 {
 81   xorshift rng;
 82   for (int i = 0; i < 100; i++) {
 83     int env[26];
 84     for (int j = 0; j < 26; j++) {
 85       env[j] = rng();
 86     }
 87     if (a->eval(env) != b->eval(env)) {
 88       return false;
 89     }
 90   }
 91   return true;
 92 }
 93 
 94 int main()
 95 {
 96   int N;
 97   cin >> N;
 98   cin.ignore();
 99   while (N-- > 0) {
100     expr *e[2];
101     for (int i = 0; i < 2; i++) {
102       string s;
103       getline(cin, s);
104       s.erase(remove_if(s.begin(), s.end(), ws_p), s.end());
105       Iterator it = s.begin(), last = s.end();
106       e[i] = parse_expr(it, last);
107     }
108     cout << (same_p(e[0], e[1]) ? "YES" : "NO") << endl;
109     delete e[0];
110     delete e[1];
111   }
112   return 0;
113 }