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再入栈）。
入其他栈有一个类似括号匹配的过程，
如果碰到“]”,那么就一直出栈直到遇到“[’， 那么中间遇到的那个数字就是，数组名为字母栈顶，下标为这个数字的值， 如果这个值存在， 那么就将这个值入栈， 直到其他栈最后只剩下一个值，没有其他元素。
#include <bits/stdc++.h>
using namespace std;
typedef pair<char, int> PCI;
map<PCI, int> arr_value; // 数组名和下标， 值
map<char, int> arr_maxi;//数组名 ， 最大下标
int F = ;
int line;
void error()
{
if(!F)
{
F = ;
cout << line << "\n";
}
}
int read(const string& s, int type)
{
stack<int> name;
stack<int> index;
int k = , v = ;
char a = ;
if(type == )//等于号左边
{
if(!arr_maxi.count(s[]))//未定义
{
return -;
}
}
else if(type == )//要赋的值
{
if(!arr_maxi.count(s[]))//未定义
{
return -;
}
}
for(int i = ; i <= s.size() - ; i++)//求出括号内的东西
{
if(isalpha(s[i]))
{
name.push(s[i]);
}
else
{
if(isdigit(s[i]))
{
int j = i;
int sum = ;
while(isdigit(s[j]))//将字符串转换为十进制数
{ sum *= ;
sum += s[j] - '';
j++;
}
i = j;
index.push(sum);
if(index.size() == ) //此时只有数字
{
v = sum;
break;
}
}
else
{
if(s[i] == '[')//左括号
{
index.push(s[i]);
}
else //右括号
{
k = index.top();
index.pop();//下标出栈
index.pop();//左括号出栈
a = name.top();
name.pop(); //名字出栈 if(arr_value.count(make_pair(a,k)))//找到a[k]
{
if(index.empty())//只剩下这个数
{
v = arr_value[make_pair(a,k)];
break;
}
else
{
index.push(arr_value[make_pair(a,k)]);
}
}
else//找不到a[k]的值 == 1.a没定义 2. a[k]没赋值
{
return -;
}
}
}
}
}
if(type == ) //等于号左边
{
if(v <= arr_maxi[s[]]) //小于最大下标
{
return v;
}
else
{
return -;
}
}
if(type == ) //要赋的值，
{
if(!arr_value.count(make_pair(s[],v)))
{
return -;
}
else
{
return arr_value[make_pair(s[],v)];
}
}
if(type == )//声明语句
{
return v;
}
}
int main()
{
#if LOCAL
freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif // LOCAL ios::sync_with_stdio(false);
string s;
while(getline(cin,s) && s[] != '.')
{ arr_value.clear();
arr_maxi.clear();
line = ;
F = ;
do
{
if(s.find('=')!= string :: npos)//赋值语句
{
string a,b;
a = s.substr(,s.find('='));
b = s.substr(s.find('=')+);
int value ,flag = ;
if(isdigit(b[]))//如果第一个是数字，那么只有数字
{
flag = ;
int sum = ;
for(int i = ; i < b.size(); i++)
{
sum *= ;
sum += b[i] - '';
}
value = sum;
}
else//第一个是字母
{
value= read(b,);//先读取要赋的值
}
if(value < )//错误
{
error();
}
int index = read(a,);
if (index < )
{
error();
}
arr_value[make_pair(s[],index)] = value; }
else //声明语句
{
int v = read(s,);
if (v < )
{
error();
}
else
{
arr_maxi[s[]] = v - ;
}
}
line ++;
}while(getline(cin , s) && s[] != '.');
if(!F)//读到最后都没发现错误
{
cout <<"0\n";
}
}
}
最新文章
- Bzoj3450 Tyvj1952 Easy
- **SQL某一表中重复某一字段重复记录查询与处理
- jQuery-1.9.1源码分析系列（八） 属性操作
- js的事件的绑定
- mac下开发IOS代码管理
- cassandra-执行请求入口函数
- linux 下运行多个tomcat
- 最实用的APP界面设计知识，有温度的APP设计（转）
- Marbles启动信息
- db4o种纯对象数据库引擎
- 4542: [Hnoi2016]大数
- 事件冒泡、事件委托、jQuery元素节点操作、滚轮事件与函数节流
- php使用rc4加密算法
- SQLServer之修改UNIQUE约束
- Jquery.Datatable 控件后端分页实例 （后台使用ashx、aspx-webmethod）
- docker zabbix
- SQL varbinary varchar 互转
- 大疆无人机M100相关问题解决过程
- Python3 tkinter基础 Canvas create_rectangle 画虚边的矩形 create_oval 画椭圆形 圆形
- C++ operator new 重载(两个参数）