手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

习题5_9 找bug(Bug Hunt, ACM/ICPC Tokyo 2007, UVa1596)

时间:2021/4/13 16:30:55|来源:|点击: 次

题目描述:

        输入并模拟执行一段程序,输出第一个bug所在的行。每行程序有两种可能:
        1.数组定义,格式为arr[size]。例如a[10]或者b[5],可用下标分别是 0 ~ 9 和 0 ~ 4 。定义之后所有元素均为未初始化状态。输入保证数组名是单个字母。
        2.赋值语句,格式为arr[index]=value。例如a[0]=3或者a[a[0]]=a[1]。

        赋值语句可能会出现两种bug:下标index越界;使用未初始化的变量(index和value都可能出现这种情况)
        程序不超过1000行,每行不超过80个字符且所有常数均为小于231的非负整数。
在这里插入图片描述
在这里插入图片描述在这里插入图片描述

AC代码:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
#include<map>
#include<vector>
using namespace std;

map<char, int> arr_range;              // 数组名,数组长度 
map<char, map<int, int> > arr_map;     // 数组名映射到数组
bool flag = true;                      // 目前代码是否出错,true为正确 
 
int find_num(const string& cmd) {
	int num, idx;
	if(!flag) return 0;
	if(isdigit(cmd[0])) {
		stringstream ss(cmd);
		ss >> num;
	} else if(isalpha(cmd[0]) && isdigit(cmd[2])) {
		stringstream ss(cmd.substr(2));
		ss >> idx;
		if(!arr_map[cmd[0]].count(idx) || arr_range[cmd[0]] <= idx) { flag = false; return 0; }
		num = (arr_map[cmd[0]])[idx];
	} else if(isalpha(cmd[0]) && isalpha(cmd[2])) {
		idx = find_num(cmd.substr(2));
		if(!arr_map[cmd[0]].count(idx) || arr_range[cmd[0]] <= idx) { flag = false; return 0; }
		num = (arr_map[cmd[0]])[idx];
	}
	return num;
}

int main() {
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	string s;
	while(cin >> s) {
		if(s == ".") break;
		flag = true;
		int line = 1;
		string cmd(s);
		arr_range.clear();
		arr_map.clear();
		while(cmd != ".") {
			if(strchr(cmd.c_str(), '=') == NULL) { //数组定义
				map<int, int> arr;                 //数组 
				arr_map[cmd[0]] = arr;
				stringstream ss(cmd.substr(2));
				int length;
				ss >> length;
				arr_range[cmd[0]] = length;
				//cout << length << "\n";
				line++;
			} else {                               //赋值语句
				char arr_name = cmd[0];
				int idx, value, interval;
				interval = strchr(cmd.c_str(), '=') - cmd.c_str();
				idx = find_num(cmd.substr(2, interval));
				value = find_num(cmd.substr(interval + 1));
				if(arr_range[cmd[0]] <= idx) flag = false;
				if(flag) {
					//cout << idx << " " << value << "\n";
					(arr_map[arr_name])[idx] = value;
					line++;
				}
			}
			cin >> cmd;
		}
		if(flag) cout << "0\n";
		else cout << line << "\n";
	}
	return 0;
}

Copyright © 2002-2019 某某自媒体运营 版权所有