AOJ 1322 - ASCII Expression

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1322

概要

与えられた BNF に従った二次元で表現された n 個の数式を評価した値を modulo 2011 で答える．

制約

解法

二次元のパースということでかなり重い実装に見えるが，

の状態が追加されただけで普通に LL(1) なパースをすればいい．

通常は base の行だけを見て処理をし，fraction のときは top, bottom を base の上側と下側に分けて，それぞれの間で base を見つけ，再帰的にパースする．

x/y modulo 2011 はフェルマーの小定理から x * y^2009 で計算できる．

  1 #include <iostream>
  2 #include <vector>
  3 using namespace std;
  4 static const int M = 2011;
  5 
  6 int powmod(int a, int n)
  7 {
  8   if (n == 0) {
  9     return 1;
 10   } else if (n & 1) {
 11     return (a * powmod(a, n-1))%M;
 12   } else {
 13     const int e = powmod(a, n>>1);
 14     return (e * e)%M;
 15   }
 16 }
 17 
 18 struct parser
 19 {
 20   int i;
 21   vector<string> src;
 22   parser() : i(0), src() {}
 23 
 24   int width() const { return src[0].size(); }
 25   int height() const { return src.size(); }
 26   int find_base(int top, int bot)
 27   {
 28     for (; i < width(); i++) {
 29       for (int k = top; k < bot; k++) {
 30         if (src[k][i] != '.') {
 31           return k;
 32         }
 33       }
 34     }
 35     throw "find_base";
 36   }
 37 
 38   int parse(int top, int bot)
 39   {
 40     return expr(find_base(top, bot), top, bot);
 41   }
 42 
 43   int expr(int base, int top, int bot)
 44   {
 45     const string& line = src[base];
 46     int r = term(base, top, bot);
 47     while (i+2 < width() && line[i] == '.' && (line[i+1] == '+' || line[i+1] == '-') && line[i+2] == '.') {
 48       const char op = line[i+1];
 49       i += 3;
 50       const int t = term(base, top, bot);
 51       if (op == '+') {
 52         r = (r + t)%M;
 53       } else {
 54         r = ((r - t)%M + M)%M;
 55       }
 56     }
 57     return r;
 58   }
 59 
 60   int term(int base, int top, int bot)
 61   {
 62     const string& line = src[base];
 63     int r = factor(base, top, bot);
 64     while (i+2 < width() && line[i] == '.' && line[i+1] == '*' && line[i+2] == '.') {
 65       i += 3;
 66       const int t = factor(base, top, bot);
 67       r = (r * t)%M;
 68     }
 69     return r;
 70   }
 71 
 72   int factor(int base, int top, int bot)
 73   {
 74     const string& line = src[base];
 75     if (line[i] == '-') {
 76       if (line[i+1] == '.') {
 77         i += 2;
 78         const int r = factor(base, top, bot);
 79         return (-r + M)%M;
 80       } else {
 81         const int save = i;
 82         const int n = parse(top, base);
 83         i = save;
 84         const int d = parse(base+1, bot);
 85         i = save;
 86         while (i < width() && line[i] == '-') {
 87           ++i;
 88         }
 89         return (n * powmod(d, M-2))%M;
 90       }
 91     } else {
 92       return powexpr(base, top, bot);
 93     }
 94   }
 95 
 96   int powexpr(int base, int top, int bot)
 97   {
 98     int r = primary(base, top, bot);
 99     if (base-1 >= top && i < width() && isdigit(src[base-1][i])) {
100       const int n = src[base-1][i]-'0';
101       i++;
102       return powmod(r, n);
103     } else {
104       return r;
105     }
106   }
107 
108   int primary(int base, int top, int bot)
109   {
110     const string& line = src[base];
111     if (line[i] == '(' && line[i+1] == '.') {
112       i += 2;
113       const int r = expr(base, top, bot);
114       i += 2;
115       return r;
116     } else {
117       const int n = line[i]-'0';
118       i++;
119       return n;
120     }
121   }
122 };
123 
124 int main()
125 {
126   int N;
127   while (cin >> N && N != 0) {
128     parser p;
129     p.src.resize(N);
130     for (int i = 0; i < N; i++) {
131       cin >> p.src[i];
132     }
133     cout << p.parse(0, N) << endl;
134   }
135   return 0;
136 }
aoj/1322.cc