【UVA-1596】Bug Hunt【紫书】

【UVA-1596】Bug Hunt【紫书】

问题链接:https://vjudge.net/problem/UVA-1596

Solution:

数组本身便可以看成一种映射,从序号(键)到数值(值)的映射,那么我们显然可以使用map来描述一个数组,同时我们还需要一个int类型的变量来描述它的长度(这样就不必每次都调用map.size()了),因此我们可以写一个结构体来为数组类型。题目要判断的bug其实只有:无效访问【越界或访问未声明的数组】、未初始化使用这两种,数组越界可以通过比较数组的大小来确定;我们使用vector来存放数组的数据,使用map来存储数组名称到vector中存储位置的映射,这样,对于未声明的数组,该数组名称一定不存在于这个map中;对于未初始化,该键一定不存在于对应的数组对象的map中。

考虑到中括号这个运算可以嵌套使用,并且每次嵌套都具有一定的形式不变性【每个中括号中不是形如xxxx[xxxx]这样的,就是形如xxxx这样的数了】,那么我们可以写一个递归函数,参数就是字符串和中括号的起始位置,返回中括号内的值,如果返回中途遇到了无效值,就返回-1表示无效。

#include <iostream>
#include <map>
#include <vector>
#include <cctype>
// #define DBG

using namespace std;

const int NIL = -1;
struct Array {
    map<int, int> dat;
    int size;
    bool isOverflow(int idx) { return idx >= size; }
    bool isAssigned(int idx) { return dat.find(idx) != dat.end(); }
};
vector<Array> data;
map<string, int> arraymap;

int getIndex(string &str, int pos) {
    pos++;
    if (isdigit(str[pos])) {
        int ret = 0;
        for (; pos < str.size() && str[pos] != ']'; pos++)
            ret = ret * 10 + str[pos] - '0';
        return ret;
    } else {
        string type = "";
        int ret = 0, get;
        for (; pos < str.size(); pos++) {
            if (str[pos] == '[') {
                get = getIndex(str, pos);
                if (get == NIL) return NIL;
                break;
            }
            type += str[pos];
        }
        if (arraymap.find(type) == arraymap.end()) return NIL;
        if (data[arraymap[type]].isOverflow(get)) return NIL;
        if (!data[arraymap[type]].isAssigned(get)) return NIL;
        return data[arraymap[type]].dat[get];
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string op;
    string var, var2;
    int val, val2;
    int i, cnt;
    bool flag;
    while (getline(cin, op) && op[0] != '.') {
        flag = true;
        data.clear();
        arraymap.clear();
        cnt = 1;
        do {
            if (op.find('=') != string::npos) {
                var = var2 = "";
                val = val2 = 0;
                for (i = 0; op[i] != '['; i++)
                    var += op[i];
                val = getIndex(op, i);
                if (val == NIL ||
                    arraymap.find(var) == arraymap.end() ||
                    data[arraymap[var]].isOverflow(val)) {
                    cout << cnt << "\n";
                    flag = false;
                    break;
                }
                for (; op[i] != '='; i++);
                for (i++; op[i] == ' '; i++);
                if (isdigit(op[i])) {
                    for (; i < op.size() && isdigit(op[i]); i++)
                        val2 = val2 * 10 + op[i] - '0';
                } else {
                    for (; i < op.size() && op[i] != '['; i++)
                        var2 += op[i];
                    val2 = getIndex(op, i);
                    if (val2 == NIL ||
                        arraymap.find(var2) == arraymap.end() ||
                        data[arraymap[var2]].isOverflow(val2) ||
                        !data[arraymap[var2]].isAssigned(val2)) {
                        cout << cnt << "\n";
                        flag = false;
                        break;
                    }
                    val2 = data[arraymap[var2]].dat[val2];
                }
                data[arraymap[var]].dat[val] = val2;
            } else {
                var = "";
                val = 0;
                for (i = 0; op[i] != '['; i++)
                    var += op[i];
                val = getIndex(op, i);
                if (val == NIL ||
                    arraymap.find(var) != arraymap.end()) {
                    cout << cnt << "\n";
                    flag = false;
                    break;
                }
                arraymap[var] = data.size();
                data.push_back(Array());
                data[arraymap[var]].size = val;
            }
            cnt++;
        } while (getline(cin, op) && op[0] != '.');
        if (flag)
            cout << 0 << "\n";
        else
            while (getline(cin, op) && op[0] != '.');
    }
    return 0;
}