問題概要

次のような「配列を宣言したり配列に値を代入したりする処理を表すプログラム」が与えられる。

a[2147483647]
a[0]=1
B[2]
B[a[0]]=2
a[B[a[0]]]=3
a[2147483646]=a[2]
.

a[2147483647] のように「=」を含まないものは、新たな配列を宣言している。この場合は a という名前のサイズ 2147483647 の配列を宣言している。
a[B[a[0]]]=3 のように「=」を含むものは代入を表している。プログラムからB[a[0]] = 2 なので、これは a[2] = 3 となる。つまり、配列 a の添字 2 の位置に値 3 を代入することを意味する。
プログラムの最後の行は "." である。
配列名として英小文字と英大文字は区別される。

より正確には、プログラムを表す文字列は次の BNF で与えられる。

与えられるプログラムのバグを見つけ、バグのある最初の行の番号を出力せよ。ただし、バグがない場合は 0 と出力せよ。ただし、基本的にプログラムに Syntax Error はなく、次のいずれかのバグのみが発生するものとみてよい。

配列外参照：サイズが $s$ である配列に対して、 $s$ 以上の添字を指定する場合
初期化エラー：値が決まっていない配列のインデックスアクセス a[i] について、その値を用いて他の配列にインデックスアクセスしたり、右辺からその値を代入したりする場合

制約

各プログラムは 1000 行以内である
配列名はすべて 1 文字の英小文字または英大文字である
登場する数値はすべて 0 以上 2147483647 以下である

考えたこと

次の 2 つの値を管理しながら構文解析した。

map<char, long long> siz; // siz[a] := 配列 a のサイズ
map<pair<char, int>, long long> ma; // ma[{a, i}] := a[i] の値

構文解析の際には、配列のカッコの入れ子構造を、一種のカッコ列だとみなして、stack を用いて構文解析した。

#include <bits/stdc++.h>
using namespace std;

vector<string> get_input() {
    vector<string> lines;
    string S;
    while (cin >> S) {
        if (S == ".") break;
        lines.push_back(S);
    }
    return lines;
}

int solve(const vector<string> &lines) {
    map<char, long long> siz;  // siz[a] := 配列 a のサイズ
    map<pair<char, int>, long long> ma;  // ma[{a, i}] := a[i] の値
    for (int l = 0; l < lines.size(); ++l) {
        // "S=T" の形を読み解く
        string S = "", T = "";
        bool uhen = false;
        for (int j = 0; j < lines[l].size(); ++j) {
            if (lines[l][j] == '=') uhen = true;
            else if (!uhen) S += lines[l][j];
            else T += lines[l][j];
        }
        
        // 宣言の場合
        if (T == "") {
            char name = S[0];
            long long val = 0;
            for (int i = 2; i + 1 < S.size(); ++i) {
                val = (val * 10) + (S[i] - '0');
            }
            siz[name] = val;
        } else {
            // 左辺を処理
            vector<char> st;
            char left_char;
            long long left_ind = 0;
            for (auto c : S) {
                if (c == '[') continue;
                else if (c == ']') {
                    while (!st.empty()) {
                        // check range
                        if (left_ind >= siz[st.back()]) return l+1;
                        
                        // check assignment
                        if (st.size() == 1) {
                            left_char = st[0];
                        }
                        else {
                            if (!ma.count({st.back(), left_ind})) return l+1;
                            left_ind = ma[{st.back(), left_ind}];
                        }
                        st.pop_back();
                    }
                }
                else if (isdigit(c)) {
                    left_ind = left_ind * 10 + (c - '0');
                }
                else {
                    st.push_back(c);
                }
            }
            
            // 右辺を処理
            long long right_val = 0;
            for (auto c : T) {
                if (c == '[') continue;
                else if (c == ']') {
                    while (!st.empty()) {
                        // check range
                        if (right_val >= siz[st.back()]) return l+1;
                        
                        // check assignment
                        if (!ma.count({st.back(), right_val})) return l+1;
                        right_val = ma[{st.back(), right_val}];
                        st.pop_back();
                    }
                }
                else if (isdigit(c)) {
                    right_val = right_val * 10 + (c - '0');
                }
                else {
                    st.push_back(c);
                }
            }
            
            // 結果を処理
            ma[{left_char, left_ind}] = right_val;
        }
    }
    return 0;
}

int main() {
    vector<string> lines;
    while (!(lines = get_input()).empty()) {
        cout << solve(lines) << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 1282 Bug Hunt (ICPC アジア 2007 H) (450 点)

問題概要

制約

考えたこと