POJ 3524 - Bug Hunt

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

概要

配列の宣言文と配列の代入文からなるプログラムが与えられるので，バグが発生する最初の行が何行目かを答え答える． バグが発生しないときは 0 と答える．

宣言文と代入文の構文は BNF で与えられている．

バグとは，

の2つである．

制約

解法

一行ずつ構文解析してチェックするだけ．

配列のサイズが最大で 2^31 - 1 となるので map で持つといい．

式を評価するとき，バグを見つけたら一気にトップレベルにまで帰ってきたいので，こういうときには例外を使うと楽に実装できると思う．

  1 #include <iostream>
  2 #include <vector>
  3 #include <map>
  4 using namespace std;
  5 typedef string::const_iterator Iterator;
  6 
  7 struct error {};
  8 struct parse_error {
  9   Iterator it;
 10   parse_error() {}
 11   parse_error(const Iterator& a) : it(a) {}
 12 };
 13 
 14 struct array
 15 {
 16   int capacity;
 17   map<int,int> vals;
 18 
 19   void assign(int idx, int val)
 20   {
 21     if (idx < 0 || capacity <= idx) {
 22       //cerr << "idx = " << idx << endl;
 23       throw error();
 24     }
 25     vals[idx] = val;
 26   }
 27 
 28   int get(int idx)
 29   {
 30     if (!vals.count(idx)) {
 31       throw error();
 32     }
 33     return vals[idx];
 34   }
 35 };
 36 
 37 int number(Iterator& it, const Iterator& last)
 38 {
 39   int n = 0;
 40   while (isdigit(*it) && it != last) {
 41     n = 10*n + *it-'0';
 42     ++it;
 43   }
 44   return n;
 45 }
 46 
 47 int expr(map<char,array>& env, Iterator& it, const Iterator& last)
 48 {
 49   Iterator save = it;
 50   int n = number(it, last);
 51   if (it != save) {
 52     return n;
 53   }
 54   char name = *it;
 55   ++it;
 56   if (*it != '[') {
 57     throw parse_error(it);
 58   }
 59   ++it;
 60   int v = expr(env, it, last);
 61   if (*it != ']') {
 62     throw parse_error(it);
 63   }
 64   ++it;
 65   if (!env.count(name)) {
 66     throw error();
 67   }
 68   return env[name].get(v);
 69 }
 70 
 71 void declare(map<char,array>& env, Iterator& it, const Iterator& last)
 72 {
 73   char name = *it;
 74   ++it;
 75   if (*it != '[') {
 76     throw parse_error(it);
 77   }
 78   ++it;
 79   int n = number(it, last);
 80   if (*it != ']') {
 81     throw parse_error(it);
 82   }
 83   ++it;
 84   if (it != last) {
 85     throw parse_error(it);
 86   }
 87   env[name].capacity = n;
 88 }
 89 
 90 void assignment(map<char,array>& env, Iterator& it, const Iterator& last)
 91 {
 92   char name = *it;
 93   ++it;
 94   if (*it != '[') {
 95     throw parse_error();
 96   }
 97   ++it;
 98   int n = expr(env, it, last);
 99   if (*it != ']') {
100     throw parse_error();
101   }
102   ++it;
103   if (*it != '=') {
104     throw parse_error();
105   }
106   ++it;
107   int v = expr(env, it, last);
108   env[name].assign(n, v);
109   if (it != last) {
110     throw parse_error();
111   }
112 }
113 
114 int eval(map<char,array>& env, Iterator& it, const Iterator& last)
115 {
116   Iterator save = it;
117   try {
118     declare(env, it, last);
119   } catch (const parse_error& err) {
120     it = save;
121     assignment(env, it, last);
122   }
123 }
124 
125 int main()
126 {
127   string line;
128   while (getline(cin, line) && line != ".") {
129     vector<string> ls(1, line);
130     while (getline(cin, line) && line != ".") {
131       ls.push_back(line);
132     }
133 
134     int n = 1;
135     try {
136       map<char, array> env;
137       for (vector<string>::const_iterator it(ls.begin()); it != ls.end(); ++it) {
138         Iterator jt = it->begin(), last = it->end();
139         eval(env, jt, last);
140         ++n;
141       }
142       cout << "0" << endl;
143     } catch (const error&) {
144       cout << n << endl;
145     }
146   }
147   return 0;
148 }
poj/3524.cc