AOJ 1282. Bug Hunt

,

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

反省

        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;
}