AOJ2365 Memory Leak

問題リンク Memory Leak

• 解法

構文解析+シミュレーションです。
Javaでは型がクラスの変数は全て参照なのでそれを流用することにして解きました。
確保した領域クラスRを作ります。メンバーにはメモリ量を持っています。
大きさ26のRの配列rを作り、変数A〜Zが現在指している領域を格納します。
もし、変数iとjが同じ領域を指していたならばr[i]とr[j]には同じRへの参照が入っているはずなのでr[i]==r[j]が成り立っているはずです。
変数がNULLを指していたり、未定義領域を指している場合は、Rのメンバが負になっています。-1ならNULL、-2なら未定義領域を指していることにしています。
問題文中のメモリマネージャに相当するクラスManagerを作りました。malloc(), free(), clone()の処理をそのまま実装しています。また、Managerには、メモリ割り当てに使ったメモリ量allocを持っています。malloc(), clone()が呼ばれると増え（メモリが足りていれば）、free()が呼ばれると減ります。最終的に、allocから、配列rの各変数が指している領域のメモリ量の合計の差が答えとなります。複数の変数が同じ場所を指しているのをチェックする方法は上述した通りです。
free()が行われた場合、その場所を指していた変数は全て未定義領域を指すようにしないとダメなことに注意してください。

• ソース

import java.util.Scanner;

//Memory Leak
public class AOJ2365 {

	final int NULL = -1, NOT = -2;
	
	class R{
		int mem;
		public R(int mem) {
			this.mem = mem;
		}
	}
	
	class Manager{
		boolean error;
		int maxSize, alloc;
		public Manager(int maxSize) {
			this.maxSize = maxSize;
			alloc = 0;
			error = false;
		}
		R malloc(int s){
			if(maxSize<s+alloc)return new R(NULL);
			alloc+=s;
			return new R(s);
		}
		R clone(R r){
			if(r.mem==NOT){
				error = true;
				return new R(NULL);
			}
			if(r.mem==NULL)return new R(NULL);
			if(maxSize<r.mem+alloc)return new R(NULL);
			alloc+=r.mem;
			return new R(r.mem);
		}
		void free(R r){
			if(r.mem==NOT){
				error = true; return;
			}
			if(r.mem==NULL)return;
			alloc-=r.mem;
		}
	}
	
	R[] r;
	Manager manager;
	char[] s;
	int idx;
	char get(){
		return s[idx++];
	}
	
	void line(){
		if(get()=='f'){
			get();
			R e = exp();
			if(0<=e.mem)for(int i=0;i<26;i++)if(r[i]==e)r[i]=new R(NOT);
			manager.free(e);
			get();
		}
		else{
			idx--;
			exp();
		}
	}
	
	R exp(){
		char ch = get();
		if(ch=='('){
			R r = exp();
			get();
			return r;
		}
		if(ch=='m'){
			get();
			int x = 0;
			char c = get();
			do{
				x = x*10 + c-'0';
				c = get();
			}while(Character.isDigit(c));
			return manager.malloc(x);
		}
		if(ch=='c'){
			get();
			R r = manager.clone(exp());
			get();
			return r;
		}
		char nx = get();
		if(nx=='U'){
			get(); get();
			return new R(NULL);
		}
		if(nx=='='){
			R e = exp();
			if(e.mem<0)return r[ch-'A'] = new R(e.mem);
			return r[ch-'A'] = e;
		}
		idx--;
		return r[ch-'A'];
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		r = new R[26];
		for(int i=0;i<26;i++)r[i]=new R(NOT);
		manager = new Manager(sc.nextInt());
		while(sc.hasNext()){
			idx = 0;
			s = (sc.next().replace("malloc", "m").replace("free", "f").replace("clone", "c")+"$").toCharArray();
			line();
		}
		if(manager.error)System.out.println("Error");
		else{
			int u = 0;
			for(int i=0;i<26;i++){
				boolean ok = true;
				for(int j=0;j<i;j++)if(r[i]==r[j])ok = false;
				if(ok&&0<=r[i].mem)u+=r[i].mem;
			}
			System.out.println(manager.alloc-u);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2365().run();
	}
}