SRM 213 DIV1 Hard TCMinMin

問題 Editorial

問題

簡単な言語のプログラムが与えられる。そのプログラムの関数・変数の型を決定しろ

解答

まずがんばって構文解析する。
型の決定はUnion-findでやった。

コメント

構文解析苦手だなあ。無理に全部を1-passでやろうとして変なふうにしてたりするし…
もっと適当に素早くやりたい。動けばいいんだから。
時間がさすがにかかりすぎ。こういうの1時間以内で解けるコーダーになれたらいいなー！

コード

汚い＆長い

#include <string>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <cctype>
#include <cassert>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
using namespace std;
typedef vector<string> vs; 

typedef string::const_iterator IT;
IT end_iter;
bool isEnd(IT i) { return i == end_iter; }

void expect(IT& i, const string& s) {
	IT j = s.begin();
	while(j != s.end()) {
		assert(*i == *j);
		++ i, ++ j;
	}
}

enum Type {
	Int,
	String,
	Unknown
};

struct Var {
	string name; Type type;
	Var(string v, Type t): name(v), type(t) {}
};

bool takeChar(IT i, char c) {
	return !isEnd(i) && *i == c;
}
bool takeCharF(IT i, int(*f)(int)) {
	return !isEnd(i) && f(*i);
}
bool takeString(IT i, string s) {
	IT j = s.begin();
	while(!isEnd(i) && j != s.end() && *i == *j) {
		++i, ++j;
	}
	return j == s.end();
}

string var(IT& i) {
	string v;
	while(takeCharF(i, islower)) v += *i, ++i;
	return v;
}

Type type(IT& i) {
	if(takeChar(i, 'i')) {
		expect(i, "int");
		return Int;
	}else {
		expect(i, "string");
		return String;
	}
}

Type optimalType(IT& i) {
	if(takeChar(i, ':')) {
		expect(i, ":");
		return type(i);
	}else return Unknown;
}

Var param(IT& i) {
	string v = var(i);
	Type t = optimalType(i);
	return Var(v, t);
}

vector<Var> params(IT& i) {
	vector<Var> r;
	bool first = true;
	while(1) {
		if(takeChar(i, ')')) {
			return r;
		}
		if(!first) expect(i, ",");
		first = false;
		r.pb(param(i));
	}
}

IT nextLine(vs::const_iterator& ii) {
	IT i = ii->begin(); end_iter = ii->end();
	++ ii;
	return i;
}

Var value(IT& i) {
	if(takeChar(i, '"')) {
		++i; while(*i != '"') ++i; ++i;
		return Var("#", String);
	}else if(takeCharF(i, isdigit)) {
		while(takeCharF(i, isdigit)) ++i;
		return Var("#", Int);
	}else if(takeCharF(i, islower)) {
		return Var(var(i), Unknown);
	}else assert(false);
}

int isOp(int c) {
	return c == '+' || c == '-' || c == '*' || c == '/';
}

struct UnionFind {
	vector<int> data;
	UnionFind(int size_) : data(size_, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};

struct TCMinMin {
	map<pair<string,string>,int> vars;
	vector<pair<string,vector<string> > > funDecls;
	UnionFind uf;
	static const int IntConst = 2999;
	static const int StringConst = 2998;
	TCMinMin(): uf(3000) {}

	string funArgName(int k) {
		return "$" + string(1, (char)('0'+k));
	}
	int varIdx(string locateFun, string varName) {
		pair<string,string> p = mp(locateFun, varName);
		if(!vars.count(p)) {
			vars[p] = vars.size();
			if(varName == "") {
				rep(k, 50) {
					vars[mp(locateFun, funArgName(k))] = vars.size();
				}
			}
		}
		return vars[p];
	}

	void typing(int idx, Type type) {
		if(type == Int) uf.unionSet(idx, IntConst);
		else if(type == String) uf.unionSet(idx, StringConst);
	}
	void typingVarDecl(string locateFun, Var v) {
		typing(varIdx(locateFun, v.name), v.type);
	}
	void typingVal(int idx, string locateFun, Var v) {
		if(v.name == "#") typing(idx, v.type);
		else typingVar(idx, varIdx(locateFun, v.name));
	}
	void typingVar(int idx1, int idx2) {
		uf.unionSet(idx1, idx2);
	}

	string getType(string locateFun, string varName) {
		int idx = varIdx(locateFun, varName);
		if(uf.findSet(idx, IntConst)) return "int";
		else if(uf.findSet(idx, StringConst)) return "string";
		else return "!Unknown!";
	}

	vector <string> deduceTypes(vector <string> program) {

		vs::const_iterator ii = program.begin();
		while(ii != program.end()) {
			IT i = nextLine(ii);
			expect(i, "function ");
			string currentFun = var(i);
			varIdx(currentFun, "");
			funDecls.pb(mp(currentFun, vs()));

			expect(i, "(");
			vector<Var> pars = params(i);
			rep(k, pars.size()) {
				vars[mp(currentFun, pars[k].name)] = vars[mp(currentFun, funArgName(k))];
				typingVarDecl(currentFun, pars[k]);
				funDecls.back().second.pb(pars[k].name);
			}
			expect(i, ")");
			Type funType = optimalType(i);
			typingVarDecl(currentFun, Var("", funType));
			i = nextLine(ii);
			while(1) {
				if(takeString(i, "return ")) {
					expect(i, "return ");
					Var retVal = value(i);
					typingVal(varIdx(currentFun, ""), currentFun, retVal);
					break;
				}
				string v = var(i);
				if(takeChar(i, ':')) {
					expect(i, ":");
					Type t = type(i);
					typingVarDecl(currentFun, Var(v, t));
				}else if(takeChar(i, '=')) {
					expect(i, "=");
					Var val1 = value(i);
					if(takeChar(i, '(')) {
						string callFun = val1.name;
						typingVar(varIdx(currentFun, v), varIdx(callFun, ""));
						expect(i, "(");
						vector<Var> args = params(i);
						rep(k, args.size()) {
							typingVar(varIdx(currentFun, args[k].name), varIdx(callFun, funArgName(k)));
						}
						expect(i, ")");
					}else if(takeCharF(i, isOp)) {
						char op = *i; ++i;
						string var2 = var(i);
						if(op == '*' || op == '/') {
							typingVarDecl(currentFun, Var(val1.name, Int));
							typingVarDecl(currentFun, Var(var2     , Int));
						}
						typingVar(varIdx(currentFun, v), varIdx(currentFun, val1.name));
						typingVar(varIdx(currentFun, v), varIdx(currentFun, var2     ));
					}else {
						typingVal(varIdx(currentFun, v), currentFun, val1);
					}
				}else assert(false);
				i = nextLine(ii);
			}
		}

		if(uf.findSet(IntConst, StringConst)) {
			cout << "!!! Type Error !!!" << endl;
		}

		vector<string> r;
		rep(i, funDecls.size()) {
			set<string> paramVars, localVars;
			string s = "function ";
			string funName = funDecls[i].first;
			s += funName; s += '(';
			rep(j, funDecls[i].second.size()) {
				string paramName = funDecls[i].second[j];
				if(j != 0) s += ',';
				s += paramName; s += ':'; s += getType(funName, paramName);
				paramVars.insert(paramName);
			}
			s += ')'; s += ':'; s += getType(funName, "");
			r.pb(s);
			each(j, vars) if(j->first.first == funName) {
				const string& t = j->first.second;
				if(t.size() && t[0] != '$' && !paramVars.count(t)) localVars.insert(t);
			}
			each(j, localVars) {
				s = "";
				s += *j; s += ':'; s += getType(funName, *j);
				r.pb(s);
			}
		}
		return r;
	}
};