AOJ : 1282 - Bug Hunt

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1282
C言語チックな配列操作が入力される.
この入力を上から順番に実行していったとき, どこでバグが起きるかを出力する.
ただし, バグがない場合は, 0 を出力する.

アルゴリズム

構文解析でやるだけです.
がんばって書きましょう！

プログラム

int idx,len;
string s;
map<int,int> val[128];
int size[128];

int number(){
  string tmp = "";
  while(isdigit(s[idx])){
    tmp += s[idx];
    idx++;
  }
  return atoi(&tmp[0]);
}

int expression(){
  if(isdigit(s[idx])){
    return number();
  }

  char name = s[idx++];
  if(size[name] == -1) return -1;

  idx++;
  int exp = expression();
  idx++;
  if(exp==-1 || exp>=size[name] || val[name].find(exp)==val[name].end()) return -1;

  return val[name][exp];
}

bool assignment(){
  char name = s[idx++];
  if(size[name] == -1) return false;

  idx++;
  int exp = expression();
  idx++;
  if(exp==-1 || exp>=size[name]) return false;

  idx++;
  int exp2 = expression();
  if(exp2==-1) return false;

  val[name][exp] = exp2;

  return true;
}

bool declaration(){
  char name = s[idx++];

  idx++;
  int num = number();
  idx++;

  size[name] = num;

  return true;
}

bool program(){
  idx = 0;
  len = s.length();

  bool flg = false;
  for(int i=0;i<len;i++){
    if(s[i] == '='){
      flg = true;
      break;
    }
  }

  if(flg) return assignment();
  return declaration();
}

int main(void){
  while(1){
    bool bugFlg = false;

    for(int i=0;i<128;i++){
      val[i].clear();
      size[i] = -1;
    }

    for(int set=1;;set++){
      cin>>s;
      if(s == "."){
        if(set == 1) return 0;
        if(!bugFlg) cout<<0<<endl;
        break;
      }

      if(!bugFlg){
        if(!program()){
          bugFlg = true;
          cout<<set<<endl;
        }
      }
    }
  }

  return 0;
}