AOJ 1314 - Matrix Calculator

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

概要

n 個の与えられた行列に関する代入式を評価した結果を出力する．

制約

解法

がんばって実装するだけ．

matrix が単に数字のみからなっていれば楽だが，問題文中の例にある [[1 2 3;4 5 6] [7 8;9 10] [11;12];13 14 15 16 17 18] のように，row の要素として任意の expr をとることができ，それを適切に展開しなければならない．

自分はまずすべての値を行列で表現し，row を vector<matrix> で受け取り，row-seq を一旦 vector<vector<matrix> > で受け取った後， 最終的な行列のサイズを計算してから展開するようにした．

  1 #include <iostream>
  2 #include <vector>
  3 #include <map>
  4 #include <cassert>
  5 using namespace std;
  6 
  7 struct mod
  8 {
  9   int operator()(int n) const
 10   {
 11     static const int m = 32768;
 12     return (n%m+m)%m;
 13   }
 14 };
 15 static const mod M = mod();
 16 
 17 struct matrix
 18 {
 19   vector<vector<int> > v;
 20   matrix() {}
 21   matrix(int r, int c) : v(r, vector<int>(c, 0)) {}
 22 
 23   int row() const { return v.size(); }
 24   int column() const { return v[0].size(); }
 25   bool scalar() const { return row() == 1 && column() == 1; }
 26   matrix transpose() const
 27   {
 28     matrix m(column(), row());
 29     for (int i = 0; i < row(); i++) {
 30       for (int j = 0; j < column(); j++) {
 31         m.v[j][i] = v[i][j];
 32       }
 33     }
 34     return m;
 35   }
 36   matrix& operator+=(const matrix& m)
 37   {
 38     assert(row() == m.row() && column() == m.column());
 39     for (int i = 0; i < row(); i++) {
 40       for (int j = 0; j < column(); j++) {
 41         v[i][j] = M(v[i][j] + m.v[i][j]);
 42       }
 43     }
 44     return *this;
 45   }
 46   matrix& operator-=(const matrix& m)
 47   {
 48     assert(row() == m.row() && column() == m.column());
 49     for (int i = 0; i < row(); i++) {
 50       for (int j = 0; j < column(); j++) {
 51         v[i][j] = M(v[i][j] - m.v[i][j]);
 52       }
 53     }
 54     return *this;
 55   }
 56   matrix& negate()
 57   {
 58     for (int i = 0; i < row(); i++) {
 59       for (int j = 0; j < column(); j++) {
 60         v[i][j] = M(-v[i][j]);
 61       }
 62     }
 63     return *this;
 64   }
 65 };
 66 
 67 matrix operator*(const matrix& m1, const matrix& m2)
 68 {
 69   if (m1.scalar()) {
 70     const int c = m1.v[0][0];
 71     matrix m(m2);
 72     for (int i = 0; i < m2.row(); i++) {
 73       for (int j = 0; j < m2.column(); j++) {
 74         m.v[i][j] = M(m.v[i][j] * c);
 75       }
 76     }
 77     return m;
 78   } else if (m2.scalar()) {
 79     return m2 * m1;
 80   } else {
 81     assert(m1.column() == m2.row());
 82     matrix m(m1.row(), m2.column());
 83     for (int i = 0; i < m1.row(); i++) {
 84       for (int j = 0; j < m2.column(); j++) {
 85         for (int k = 0; k < m1.column(); k++) {
 86           m.v[i][j] = M(m.v[i][j] + m1.v[i][k]*m2.v[k][j]);
 87         }
 88       }
 89     }
 90     return m;
 91   }
 92 }
 93 
 94 ostream& operator<<(ostream& os, const matrix& m)
 95 {
 96   for (int i = 0; i < m.row(); i++) {
 97     for (int j = 0; j < m.column(); j++) {
 98       if (j != 0) {
 99         os << ' ';
100       }
101       os << m.v[i][j];
102     }
103     os << endl;
104   }
105   return os;
106 }
107 
108 typedef string::const_iterator Iterator;
109 map<char, matrix> env;
110 
111 matrix number(Iterator& it, const Iterator& last)
112 {
113   int n = 0;
114   while (it != last && isdigit(*it)) {
115     n = 10*n + *it-'0';
116     ++it;
117   }
118   matrix m(1, 1);
119   m.v[0][0] = n;
120   return m;
121 }
122 
123 matrix expr(Iterator& it, const Iterator& last);
124 
125 vector<matrix> row(Iterator& it, const Iterator& last)
126 {
127   vector<matrix> v(1, expr(it, last));
128   while (*it == ' ') {
129     ++it;
130     v.push_back(expr(it, last));
131   }
132   return v;
133 }
134 
135 matrix rowseq(Iterator& it, const Iterator& last)
136 {
137   vector<matrix> rr = row(it, last);
138   vector<vector<matrix> > v(1, rr);
139   int r = rr[0].row();
140   int c = 0;
141   for (vector<matrix>::const_iterator jt = rr.begin(); jt != rr.end(); ++jt) {
142     c += jt->column();
143   }
144   while (*it == ';') {
145     ++it;
146     rr = row(it, last);
147     r += rr[0].row();
148     v.push_back(rr);
149   }
150   matrix m(r, c);
151   int i = 0;
152   for (vector<vector<matrix> >::const_iterator jt = v.begin(); jt != v.end(); ++jt) {
153     int j = 0;
154     for (vector<matrix>::const_iterator kt = jt->begin(); kt != jt->end(); ++kt) {
155       for (int k = 0; k < kt->row(); k++) {
156         for (int l = 0; l < kt->column(); l++) {
157           m.v[i+k][j+l] = kt->v[k][l];
158         }
159       }
160       j += kt->column();
161     }
162     i += jt->front().row();
163   }
164   return m;
165 }
166 
167 matrix primary(Iterator& it, const Iterator& last)
168 {
169   matrix m;
170   if (*it == '[') {
171     ++it;
172     m = rowseq(it, last);
173     assert(*it == ']');
174     ++it;
175   } else if (*it == '(') {
176     ++it;
177     m = expr(it, last);
178     assert(*it == ')');
179     ++it;
180   } else if (isupper(*it)) {
181     const char var = *it;
182     ++it;
183     assert(env.count(var) != 0);
184     m = env[var];
185   } else if (isdigit(*it)) {
186     m = number(it, last);
187   } else {
188     throw "primary parse error";
189   }
190 
191   while (it != last) {
192     if (*it == '(') {
193       // indexed-primary
194       ++it;
195       const matrix m1 = expr(it, last);
196       assert(m1.row() == 1);
197       assert(*it == ',');
198       ++it;
199       const matrix m2 = expr(it, last);
200       assert(m2.row() == 1);
201       assert(*it == ')');
202       ++it;
203       matrix r(m1.column(), m2.column());
204       for (int i = 0; i < m1.column(); i++) {
205         for (int j = 0; j < m2.column(); j++) {
206           r.v[i][j] = m.v[m1.v[0][i]-1][m2.v[0][j]-1];
207         }
208       }
209       m = r;
210     } else if (*it == '\'') {
211       // transposed-primary
212       ++it;
213       m = m.transpose();
214     } else {
215       break;
216     }
217   }
218   return m;
219 }
220 
221 matrix factor(Iterator& it, const Iterator& last)
222 {
223   if (*it == '-') {
224     ++it;
225     return factor(it, last).negate();
226   } else {
227     return primary(it, last);
228   }
229 }
230 
231 matrix term(Iterator& it, const Iterator& last)
232 {
233   matrix m = factor(it, last);
234   while (it != last && *it == '*') {
235     ++it;
236     m = m * factor(it, last);
237   }
238   return m;
239 }
240 
241 matrix expr(Iterator& it, const Iterator& last)
242 {
243   matrix m = term(it, last);
244   while (it != last && (*it == '+' || *it == '-')) {
245     const char op = *it;
246     ++it;
247     if (op == '+') {
248       m += term(it, last);
249     } else {
250       m -= term(it, last);
251     }
252   }
253   return m;
254 }
255 
256 matrix assignment(Iterator& it, const Iterator& last)
257 {
258   assert(isupper(*it));
259   const char var = *it;
260   ++it;
261   assert(*it == '=');
262   ++it;
263   const matrix m = expr(it, last);
264   assert(*it == '.');
265   ++it;
266   assert(it == last);
267   return env[var] = m;
268 }
269 
270 matrix eval(const string& s)
271 {
272   Iterator it = s.begin(), last = s.end();
273   return assignment(it, last);
274 }
275 
276 int main()
277 {
278   int N;
279   while (cin >> N && N != 0) {
280     env.clear();
281     cin.ignore();
282     for (int i = 0; i < N; i++) {
283       string s;
284       getline(cin, s);
285       const matrix m = eval(s);
286       cout << m;
287     }
288     cout << "-----" << endl;
289   }
290   return 0;
291 }
aoj/1314.cc