UVA1596 Bug Hunt 找Bug 解题报告

题目链接

https://vjudge.net/problem/UVA-1596

题目大意

输入并模拟执行一段程序，输出第一个bug所在的行。每行程序有两种可能：

数组定义，格式为arr[size]。例如a[10]或者b[5]，可用下标分别是0～9和0～4。定义之后所有元素均为未初始化状态。
赋值语句，格式为arr[index]=value。例如a[0]=3或者a[a[0]]=a[1]。

赋值语句可能会出现两种bug：下标index越界；使用未初始化的变量（index和value都可能出现这种情况）。
程序不超过1000行，每行不超过80个字符且所有常数均为小于2^31的非负整数。

解题思路

因为存在嵌套，所以解析一个数组变量的值要用递归或者栈，用map维护数组名到数组信息结构体的映射，数组信息结构体应该包括数组的大小，以及该数组各个下标的值（用map< int, int >来记录）。具体实现细节见代码和注释。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define endl '\n';
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1e9 + 7;
struct Arra {               // 数组信息结构体int size;               // 该数组的大小map<int, int> value;    // 该数组各下标的值
};
map<string, Arra> ArrInfo;  // 数组名到数组信息结构体的映射
const string err = "!!!";// 声明、创建一个数组
void createArr(const string& s) {int pos = s.find('[');string arrName = s.substr(0, pos);int size = 0;for (int i = pos + 1; i < s.size() - 1; i++) {size = size * 10 + (s[i] - '0');}ArrInfo[arrName] = {size};
}/*得到一个数组对应下标位置的值，如果该值不存在则函数返回值返回-1（题目保证变量值不会有负数，所以可以用-1代表值不存在），arrName是一个引用变量，正常情况下返回数组变量名，在该变量名不存在的时候会捎带回一个"!!!"来表示数组名不存在，index也是引用变量，正常情况下返回数组下标（用于给等号左边的数组赋值），在数组的该下标位置未初始化值的时候捎带回-1
*/
int getValue(const string& s, string &arrName, int& index) {int pos = s.find('[');arrName = s.substr(0, pos);     // 分割出数组变量名if (!ArrInfo.count(arrName)) {  // 数组变量名不存在arrName = err;return -1;}index = 0;string tmps;int tmpi = 0;if (isdigit(s[pos + 1])) {  // []内是数字，直接得到数值for (int i = pos + 1; i < s.size(); i++) {if (s[i] == ']')break;tmpi = tmpi * 10 + (s[i] - '0');}index = tmpi;} else {    // []内是一个数组名，递归获取值index = getValue(s.substr(pos + 1), tmps, tmpi);}auto &value = ArrInfo[arrName].value;if (tmpi == -1 || index >= ArrInfo[arrName].size) {index = -1;return -1;}if (!value.count(index)) {return -1;}return value[index];
}void solve() {string line;while (cin >> line, line[0] != '.') {int cnt = 1;ArrInfo.clear();if (line.find('=') == -1) {   // 没有=，是数组初始化语句createArr(line);}string s;int ans = 0;while (cin >> s, s[0] != '.') {cnt++;if (ans != 0)continue;int pos = s.find('=');if (pos == -1) {createArr(s);continue;}string arrName1, arrName2;int index1, index2;getValue(s.substr(0, pos), arrName1, index1);if (arrName1 == err || index1 == -1) {ans = cnt;continue;}int a2 = 0;if (isdigit(s[pos + 1])) {for (int i = pos + 1; i < s.size(); i++) {a2 = a2 * 10 + (s[i] - '0');}} else {a2 = getValue(s.substr(pos + 1), arrName2, index2);}if (a2 == -1) {ans = cnt;continue;}ArrInfo[arrName1].value[index1] = a2;}cout << ans << endl;}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout << fixed;cout.precision(18);solve();return 0;
}