首页 > 代码库 > UVA 1596 Bug Hunt （大模拟 栈）
UVA 1596 Bug Hunt （大模拟 栈）
题意：
输入并模拟执行一段程序，输出第一个bug所在的行。
每行程序有两种可能：
数组定义：
格式为arr[size]。
例如a[10]或者b[5]，可用下标分别是0～9和0～4。定义之后所有元素均为未初始化状态。
赋值语句：
格式为arr[index]=value。
或者arr[index] = arr[arr[index]]。
例如a[0]=3或者a[a[0]]=a[1]。
赋值语句和数组定义可能会出现两种bug：
下标index越界；
使用未初始化的变量（index和value都可 能出现这种情况。
程序不超过1000行，每行不超过80个字符且所有常数均为小于2 31的非负整数。
分析：
可以分为3种情况考虑：
首先考虑开以下两个map
声明语句：
对于①： 那么"a["与最后的"]"都是肯定存在的， 所以声明语句的a是肯定合法的，只需要判断...能不能转化为一个值num即可，如果可以转换为一个值就是语句就是合法的
arr_maxi[a] = num;
赋值语句：
对于②：需要赋值部分，判断条件
1.需要去找一下a有没有定义，
2.判断...能不能转化一个值num,
3.num有没大于a的最大下标,
对于③：值部分，判断条件
1.b有没有定义
2.“...”能不能转化为一个值num
3.b[num]有没有初始化
如果②③都满足了， 那么这句赋值语句就是合法的，插入 arr_value[pair(数组名,下标)] = 值
现在问题就是，如何判断...能不能转化为一个值
我的方法是使用栈，首先明确， 每条语句只有：大小写字母，[,]，数字，四种情况
那么可以开一个 字母栈 一个其他栈
然后遇到字母就将字母入字母栈 遇到其他就入其他栈（这里要注意将字符串的数字转化为int再入栈）。
入其他栈有一个类似括号匹配的过程，
如果碰到“]”,那么就一直出栈直到遇到“[’， 那么中间遇到的那个数字就是，数组名为字母栈顶，下标为这个数字的值， 如果这个值存在， 那么就将这个值入栈， 直到其他栈最后只剩下一个值，没有其他元素。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef pair<char, int> PCI; 4 map<PCI, int> arr_value; // 数组名和下标， 值 5 map<char, int> arr_maxi;//数组名 ， 最大下标 6 int F = 0; 7 int line; 8 void error() 9 { 10 if(!F) 11 { 12 F = 1; 13 cout << line << "\n"; 14 } 15 } 16 int read(const string& s, int type) 17 { 18 stack<int> name; 19 stack<int> index; 20 int k = 0, v = 0; 21 char a = 0; 22 if(type == 0)//等于号左边 23 { 24 if(!arr_maxi.count(s[0]))//未定义 25 { 26 return -1; 27 } 28 } 29 else if(type == 1)//要赋的值 30 { 31 if(!arr_maxi.count(s[0]))//未定义 32 { 33 return -1; 34 } 35 } 36 for(int i = 2; i <= s.size() - 1; i++)//求出括号内的东西 37 { 38 if(isalpha(s[i])) 39 { 40 name.push(s[i]); 41 } 42 else 43 { 44 if(isdigit(s[i])) 45 { 46 int j = i; 47 int sum = 0; 48 while(isdigit(s[j]))//将字符串转换为十进制数 49 { 50 51 sum *= 10; 52 sum += s[j] - ‘0‘; 53 j++; 54 } 55 i = j; 56 index.push(sum); 57 if(index.size() == 1) //此时只有数字 58 { 59 v = sum; 60 break; 61 } 62 } 63 else 64 { 65 if(s[i] == ‘[‘)//左括号 66 { 67 index.push(s[i]); 68 } 69 else //右括号 70 { 71 k = index.top(); 72 index.pop();//下标出栈 73 index.pop();//左括号出栈 74 a = name.top(); 75 name.pop(); //名字出栈 76 77 if(arr_value.count(make_pair(a,k)))//找到a[k] 78 { 79 if(index.empty())//只剩下这个数 80 { 81 v = arr_value[make_pair(a,k)]; 82 break; 83 } 84 else 85 { 86 index.push(arr_value[make_pair(a,k)]); 87 } 88 } 89 else//找不到a[k]的值 == 1.a没定义 2. a[k]没赋值 90 { 91 return -1; 92 } 93 } 94 } 95 } 96 } 97 if(type == 0) //等于号左边 98 { 99 if(v <= arr_maxi[s[0]]) //小于最大下标 100 { 101 return v; 102 } 103 else 104 { 105 return -3; 106 } 107 } 108 if(type == 1) //要赋的值， 109 { 110 if(!arr_value.count(make_pair(s[0],v))) 111 { 112 return -1; 113 } 114 else 115 { 116 return arr_value[make_pair(s[0],v)]; 117 } 118 } 119 if(type == 2)//声明语句 120 { 121 return v; 122 } 123 } 124 int main() 125 { 126 #if LOCAL 127 freopen("1.txt","r",stdin); 128 // freopen("2.txt","w",stdout); 129 #endif // LOCAL 130 131 ios::sync_with_stdio(false); 132 string s; 133 while(getline(cin,s) && s[0] != ‘.‘) 134 { 135 136 arr_value.clear(); 137 arr_maxi.clear(); 138 line = 1; 139 F = 0; 140 do 141 { 142 if(s.find(‘=‘)!= string :: npos)//赋值语句 143 { 144 string a,b; 145 a = s.substr(0,s.find(‘=‘)); 146 b = s.substr(s.find(‘=‘)+1); 147 int value ,flag = 0; 148 if(isdigit(b[0]))//如果第一个是数字，那么只有数字 149 { 150 flag = 1; 151 int sum = 0; 152 for(int i = 0; i < b.size(); i++) 153 { 154 sum *= 10; 155 sum += b[i] - ‘0‘; 156 } 157 value =http://www.mamicode.com/ sum; 158 } 159 else//第一个是字母 160 { 161 value= http://www.mamicode.com/read(b,1);//先读取要赋的值 162 } 163 if(value < 0)//错误 164 { 165 error(); 166 } 167 int index = read(a,0); 168 if (index < 0) 169 { 170 error(); 171 } 172 arr_value[make_pair(s[0],index)] = value; 173 174 } 175 else //声明语句 176 { 177 int v = read(s,2); 178 if (v < 0) 179 { 180 error(); 181 } 182 else 183 { 184 arr_maxi[s[0]] = v - 1; 185 } 186 } 187 line ++; 188 }while(getline(cin , s) && s[0] != ‘.‘); 189 if(!F)//读到最后都没发现错误 190 { 191 cout <<"0\n"; 192 } 193 } 194 }
UVA 1596 Bug Hunt （大模拟 栈）