POJ 1472 - Instant Complexity

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

概要

BNF に従ったプログラムが渡されるので，それの計算量を答える．

制約

解法

普通に構文解析して多項式を足したり掛けたりするだけ．

  1 #include <iostream>
  2 #include <sstream>
  3 #include <vector>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 struct poly
  8 {
  9   int cs[15];
 10   poly() { fill_n(cs, 15, 0); }
 11   poly& operator+=(const poly& p)
 12   {
 13     for (int i = 0; i <= 10; i++) {
 14       cs[i] += p.cs[i];
 15     }
 16     return *this;
 17   }
 18   poly operator*(const poly& p) const
 19   {
 20     poly ans;
 21     for (int i = 0; i <= 10; i++) {
 22       for (int j = 0; i+j <= 10; j++) {
 23         ans.cs[i+j] += cs[i] * p.cs[j];
 24       }
 25     }
 26     return ans;
 27   }
 28 };
 29 ostream& operator<<(ostream& os, const poly& p)
 30 {
 31   bool first = true;
 32   for (int i = 10; i >= 0; i--) {
 33     if (p.cs[i] != 0) {
 34       if (!first) {
 35         os << '+';
 36       }
 37 
 38       if (p.cs[i] == 1 && i != 0) {
 39       } else {
 40         os << p.cs[i];
 41         if (i != 0) {
 42           os << "*";
 43         }
 44       }
 45 
 46       if (i != 0) {
 47         os << "n";
 48         if (i != 1) {
 49           os << "^" << i;
 50         }
 51       }
 52       first = false;
 53     }
 54   }
 55   if (first) {
 56     os << 0;
 57   }
 58   return os;
 59 }
 60 
 61 typedef vector<string>::const_iterator Iterator;
 62 int read(const string& s)
 63 {
 64   istringstream iss(s);
 65   int n;
 66   iss >> n;
 67   return n;
 68 }
 69 
 70 poly statements(Iterator& it);
 71 poly statement(Iterator& it)
 72 {
 73   if (*it == "OP") {
 74     ++it;
 75     poly p;
 76     p.cs[0] = read(*it);
 77     ++it;
 78     return p;
 79   } else if (*it == "LOOP") {
 80     ++it;
 81     const string s = *it;
 82     ++it;
 83     poly p;
 84     if (s == "n") {
 85       p.cs[1] = 1;
 86     } else {
 87       p.cs[0] = read(s);
 88     }
 89     const poly q = statements(it);
 90     if (*it != "END") { throw "statement-loop"; }
 91     ++it;
 92     const poly ans = p * q;
 93     return ans;
 94   } else {
 95     throw "statement";
 96   }
 97 }
 98 
 99 poly statements(Iterator& it)
100 {
101   poly p;
102   p.cs[0] = 0;
103   while (*it == "LOOP" || *it == "OP") {
104     p += statement(it);
105   }
106   return p;
107 }
108 
109 poly program(Iterator& it)
110 {
111   if (*it != "BEGIN") { throw "program-begin"; }
112   ++it;
113   const poly p = statements(it);
114   if (*it != "END") { throw "program-end"; }
115   ++it;
116   return p;
117 }
118 
119 int main()
120 {
121   int T;
122   cin >> T;
123   vector<string> tokens;
124   for (string tok; cin >> tok;) {
125     tokens.push_back(tok);
126   }
127   Iterator it = tokens.begin();
128   for (int Ti = 1; Ti <= T; Ti++) {
129     cout << "Program #" << Ti << endl;
130     const poly p = program(it);
131     cout << "Runtime = " << p << endl;
132     cout << endl;
133   }
134   return 0;
135 }
poj/1472.cc