AOJ 1282. Bug Hunt
反省
ll value = parse_and_eval_expr(first, last, env);
env.value[name][index] = value;
とすべきところを
env.value[name][index] = parse_and_eval_expr(first, last, env);
として死んだ。
solution
再帰下降構文解析を書くだけ。$O(N)$。
implementation
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <map>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
constexpr int array_name_size = 52;
struct env_t {
array<ll, array_name_size> size;
array<map<ll, ll>, array_name_size> value;
};
env_t initial_environment() {
env_t env = {};
whole(fill, env.size, -1);
return env;
}
int array_name_to_index(char c) {
if (islower(c)) return c - 'a';
if (isupper(c)) return c - 'A' + 26;
assert (false);
}
struct bug_found {};
ll parse_number(string::const_iterator & first, string::const_iterator last) {
assert (isdigit(*first));
ll n = 0;
while (isdigit(*first)) {
n = n * 10 + (*first - '0');
++ first;
}
return n;
}
ll parse_and_eval_expr(string::const_iterator & first, string::const_iterator last, env_t const & env) {
if (isdigit(*first)) {
return parse_number(first, last);
} else {
int name = array_name_to_index(*first);
++ first;
assert (*first == '[');
++ first;
ll index = parse_and_eval_expr(first, last, env);
assert (*first == ']');
++ first;
if (not (index < env.size[name])) throw (bug_found) {};
if (not env.value[name].count(index)) throw (bug_found) {};
return env.value[name].at(index);
}
}
pair<int, ll> parse_var(string::const_iterator & first, string::const_iterator last, env_t const & env) {
int name = array_name_to_index(*first);
++ first;
assert (*first == '[');
++ first;
ll number = parse_and_eval_expr(first, last, env);
assert (*first == ']');
++ first;
return { name, number };
}
void parse_and_exec_line(string const & code, env_t & env) {
string::const_iterator first = code.begin();
string::const_iterator const last = code.end();
if (whole(count, code, '=')) {
int name; ll index; tie(name, index) = parse_var(first, last, env);
assert (*first == '=');
++ first;
if (not (index < env.size[name])) throw (bug_found) {};
ll value = parse_and_eval_expr(first, last, env); // this binding is required
env.value[name][index] = value;
} else {
int name; ll size; tie(name, size) = parse_var(first, last, env);
assert (env.size[name] == -1);
env.size[name] = size;
}
assert (first == last);
}
int main() {
while (true) {
// input
vector<string> code;
while (true) {
string s; cin >> s;
if (s == ".") break;
code.push_back(s);
}
if (code.empty()) break;
// solve
int result = -1;
env_t env = initial_environment();
repeat (i, code.size()) {
try {
parse_and_exec_line(code[i], env);
} catch (bug_found e) {
result = i;
break;
}
}
// output
printf("%d\n", result + 1);
}
return 0;
}