习题5-9 找bug (Bug Hunt，ACM/ICPC Tokyo 2007，UVa1596）

本文主要是介绍习题5-9 找bug (Bug Hunt，ACM/ICPC Tokyo 2007，UVa1596），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-1596
分类：STL综合
备注：中级模拟
前言：说是题目要我找输入的bug，实际找的却是我自己的bug…细数一下我犯过的错误：①一开始没想好怎么写函数，传入参数调来调去乱套了，最后还是删了重来终于让思路更清晰了；②遗漏条件，某个部分忽略了题目条件；③自己犯蠢，我居然在算下标的时候从低位到高位遍历，但是用的方法却是高位加到低位，因为这个憨批操作debug了好久！

思路

用了两个map，一个map<数组名,范围>记录出现过的数组和其下标范围，还有一个map<pair<数组名，下标>,值>记录某个数组在某个下标所有的值。
最关键的还是求数组元素的嵌套，主要是以每个最左边的’[‘和最右边的’]'作为头和尾，st和tail，用递归函数求括号中的值，进入函数后遍历st+1到tail-1，一旦发现其中有中括号则递归进入更深一层函数，直到没有括号出现直接得到下标的数值然后返回。具体看下面代码实现。
在找值的过程中判断了题目条件，但是外面的一些操作也得记得判断。

代码如下：

#include<cstdio>
#include<string>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<string, ll>PII;
string line;
int ans;
map <string, ll> var;
map<PII, ll>value;
ll V(string line, int st, int tail)//st为最左边的'['的下标,tail为最右边的']'的下标
{ll xb = 0;for (int i = st + 1; i < tail; i++)//在st和tail之间还有中括号if (line[i] == '['){string variable = line.substr(st + 1, i - st - 1);for (int j = tail - 1;; j--)if (line[j] == ']'){xb = V(line, i, j);break;}if (!var.count(variable) || var[variable] <= xb)return -1;//未初始化或者数组下标越界if (!value.count(PII(variable, xb)))return -1;//未赋值却要用值return value[PII(variable, xb)];}for (int i = st + 1; i < tail; i++)//在这里我傻逼了xb = 10 * xb + line[i] - '0';return xb;//中间无中括号直接返回值
}
void find_bug(string line, int row)
{int pst = 0;while (line[pst] != '[')pst++;string variable = line.substr(0, pst);ll xb = 0;int pos = line.find('=', 0);if (pos == string::npos){xb = V(line, pst, line.length() - 1);if (xb == -1) { ans = row; return; }var[variable] = xb;//初始化数组(不赋值)}else//赋值操作{xb = V(line, pst, pos - 1);//找到左值下标if (xb == -1 || !var.count(variable) || xb >= var[variable]) { ans = row; return; }ll price = V(line, pos, line.length());//'='和末尾元素右边一个位置也可以看作一组'[',']'if (price == -1) { ans = row; return; }value[PII(variable, xb)] = price;}
}
int main(void)
{int row = 0, cnt = 0;while (getline(cin, line)){++row;if (line[0] == '.'){cnt++;if (cnt == 2)return 0;printf("%d\n", ans);row = ans = 0;var.clear();value.clear();continue;}cnt = 0;if (!ans)find_bug(line, row);}return 0;
}