AOJ1282 Bug Hunt

問題リンク Bug Hunt

• 概要

簡単なプログラム言語の構造がBNFで与えられる。このプログラムは配列の宣言文と代入文のみで構成される。
配列はアルファベット1文字の名前がついており、宣言の時に配列の大きさが指定される。配列内の初期値は未定義値である。
また、アルファベットの大文字小文字は区別されるので、配列aと配列Aは別のものである。
プログラム片が与えられるので次のいずれか2つのバグが発生する最初の行数を答えよ。バグが無いときは0とせよ。
1. 配列のインデックスの範囲外参照
2. 代入する値として未定義値が使われる
与えられるプログラムは以下のことが保証されている。
宣言していない配列が代入文内で使われることはない。
プログラムの文法が間違っていることはない。
プログラムは1000行以内である。
上2つ以外のバグが含まれることはない。
配列の大きさは0〜(2^31)-1である。
アルファベット、数字、=, [, ]以外の文字がプログラム中に含まれることはない。

• 解法

1行ずつ構文解析していきます。
配列のサイズが非常に大きくなるので実際にメモリを確保すると死にます。プログラムが1000行までしかないので実際に使用される可能性がある配列のインデックスは1000個です。なので、Mapで配列を表現します。
問題文中にモノホンのBNFが与えられるのでインチキなノリBNFは書く必要ないですね。

• ソース

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//Bug Hunt
public class AOJ1282 {

	int line, bug, INVALID = -1;
	Map<Character, R> array;
	
	char[] s;
	int id;
	char get(){
		return s[id++];
	}
	class R{
		int n;
		Map<Integer, Integer> val;
		public R(int n) {
			this.n = n;
			val = new HashMap<Integer, Integer>();
		}
		int get(int x){
			if(x<0||n<=x||!val.containsKey(x))return INVALID;
			return val.get(x);
		}
		int assign(int x, int v){
			if(x<0||n<=x||v==INVALID)return INVALID;
			val.put(x, v);
			return 1;
		}
	}
	
	void program(){
		char name = get();
		get();
		int e = exp();
		char ch = get();
		if(ch!='='){
			array.put(name, new R(e));
			return;
		}
		if(e==INVALID){
			bug = line; return;
		}
		
		int val = exp();
		int res = array.get(name).assign(e, val);
		if(res==INVALID)bug = line;
	}
	int exp(){
		char ch = get();
		if(Character.isDigit(ch)){
			int x = ch-'0';
			for(;;){
				ch = get();
				if(!Character.isDigit(ch))break;
				x = x*10+ch-'0';
			}
			return x;
		}
		char name = ch;
		get();
		int e = exp();
		get();
		return array.get(name).get(e);
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			String str = sc.next();
			if(".".equals(str))break;
			line = 1; bug = 0;
			array = new HashMap<Character, R>();
			for(;;){
				s = (str+"$").toCharArray();
				id = 0;
				if(bug==0)program();
				str = sc.next();
				if(".".equals(str))break;
				line++;
			}
			System.out.println(bug);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1282().run();
	}
}