POJ 1539 - Evaluating Simple C Expressions

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

概要

からなる式が与えられるので、それの計算結果と計算後の各変数の値を答える。 変数 a, b, ..., z はそれぞれ 1, 2, ..., 26 で初期化されているとする。

制約

解法

やるだけ。 インクリメント・デクリメントをまず除去して普通の式にしてから計算した。 加算・減算しかないので、特に LL(1) する必要も無い。

  1 #include <iostream>
  2 #include <vector>
  3 #include <map>
  4 #include <algorithm>
  5 #include <cctype>
  6 using namespace std;
  7 
  8 struct calc
  9 {
 10   map<char,int> env;
 11   vector<char> preinc, predec, postinc, postdec;
 12   void pre(string& s)
 13   {
 14     for (string::iterator it = s.begin(); it != s.end() && it+1 != s.end() && it+2 != s.end(); ++it) {
 15       if (*it == '+' && *(it+1) == '+' && isalpha(*(it+2))) {
 16         preinc.push_back(*(it+2));
 17         it = s.erase(it);
 18         it = s.erase(it);
 19       } else if (*it == '-' && *(it+1) == '-' && isalpha(*(it+2))) {
 20         predec.push_back(*(it+2));
 21         it = s.erase(it);
 22         it = s.erase(it);
 23       }
 24     }
 25     for (string::iterator it = s.begin(); it != s.end() && it+1 != s.end() && it+2 != s.end();) {
 26       if (isalpha(*it) && *(it+1) == '+' && *(it+2) == '+') {
 27         postinc.push_back(*it);
 28         ++it;
 29         it = s.erase(it);
 30         it = s.erase(it);
 31       } else if (isalpha(*it) && *(it+1) == '-' && *(it+2) == '-') {
 32         postdec.push_back(*it);
 33         ++it;
 34         it = s.erase(it);
 35         it = s.erase(it);
 36       } else {
 37         ++it;
 38       }
 39     }
 40   }
 41 
 42   int f(const string& s)
 43   {
 44     for (vector<char>::const_iterator it = preinc.begin(); it != preinc.end(); ++it) {
 45       get(*it);
 46       ++env[*it];
 47     }
 48     for (vector<char>::const_iterator it = predec.begin(); it != predec.end(); ++it) {
 49       get(*it);
 50       --env[*it];
 51     }
 52     int n = 0;
 53     char o = '+';
 54     for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
 55       if (isalpha(*it)) {
 56         if (o == '+') {
 57           n += get(*it);
 58         } else if (o == '-') {
 59           n -= get(*it);
 60         } else {
 61           throw "err";
 62         }
 63       } else {
 64         o = *it;
 65       }
 66     }
 67     for (vector<char>::const_iterator it = postinc.begin(); it != postinc.end(); ++it) {
 68       ++env[*it];
 69     }
 70     for (vector<char>::const_iterator it = postdec.begin(); it != postdec.end(); ++it) {
 71       --env[*it];
 72     }
 73     return n;
 74   }
 75 
 76   bool has(char c) const { return env.count(c); }
 77   int get(char c)
 78   {
 79     if (!has(c)) {
 80       env[c] = c-'a'+1;
 81     }
 82     return env[c];
 83   }
 84 };
 85 
 86 int main()
 87 {
 88   for (string line; getline(cin, line);) {
 89     cout << "Expression: " << line << endl;
 90     line.erase(remove(line.begin(), line.end(), ' '), line.end());
 91     calc c;
 92     c.pre(line);
 93     int ans = c.f(line);
 94     cout << "    value = " << ans << endl;
 95     for (char i = 'a'; i <= 'z'; i++) {
 96       if (c.has(i)) {
 97         cout << "    " << i << " = " << c.get(i) << endl;
 98       }
 99     }
100   }
101   return 0;
102 }
poj/1539.cc