UVa1596 Bug Hunt

ajcxsu
ajcxsu 2018年05月25日
  • 25 次阅读

Problem

程序有赋值语句和声明语句
a[<value>]
a[<expression>]=<expression>/<value>
模拟程序,并找出两种BUG:

  • 越界
  • 调用了未声明的变量

Solution

填了个远古大坑。
STL全家福+完全乱搞

// Code by ajcxsu
// Problem: BUGHUNT

#include<bits/stdc++.h>
using namespace std;

int lim[500];
map<int, int> ma[500];

bool found;
typedef pair<char, int> mpair;
mpair analyze(string x) {
    vector<char> stk;
    string num;
    for(int i=0;i<x.size();i++) 
        if((x[i]>='a' && x[i]<='z') || (x[i]>='A' && x[i]<='Z')) stk.push_back(x[i]);
        else if(x[i]>='0' && x[i]<='9') num+=x[i]; 
    int nx=stoi(num);
    if(stk.size()==0) return mpair('*', nx);
    for(int i=stk.size()-1;i>0;i--) {
        if(nx<=lim[stk[i]] && ma[stk[i]].count(nx)) nx=ma[stk[i]][nx];
        else { 
            found=1;
            break;
        }
    }
    return mpair(stk[0], nx);
}

int main() {
    string cmd;
    while(1) {
        memset(lim,-1,sizeof(lim));
        for(int i=0;i<500;i++) ma[i].clear();
        found=0;
        cin>>cmd;
        if(cmd[0]=='.') break;
        int cnt=0;
        do {
            cnt++;
            string a, b;
            mpair ra, rb;
            bool ass=false;
            for(int i=0;i<cmd.size();i++)
                if(cmd[i]=='=') a=cmd.substr(0, i), b=cmd.substr(i+1, cmd.size()-i), ass=true;
            if(ass) {
                ra=analyze(a), rb=analyze(b);
                if(!found && lim[ra.first]>=ra.second && rb.first=='*') 
                    ma[ra.first][ra.second]=rb.second; 
                else if(!found && lim[rb.first]>=rb.second && ma[rb.first].count(rb.second) && lim[ra.first]>=ra.second)
                    ma[ra.first][ra.second]=ma[rb.first][rb.second];
                else found=1;
            }
            else ra=analyze(cmd), lim[ra.first]=ra.second-1;
            if(found) {
                while(cmd[0]!='.') cin>>cmd;
                cout<<cnt<<endl;
            }
            else cin>>cmd;
        } while(cmd[0]!='.'); 
        if(!found) cout<<0<<endl; 
    }

    return 0;
}

本文链接:https://acxblog.site/archives/sol-uva-1596.html
本文采用 CC BY-NC-SA 3.0 协议进行许可