Andrew Stankevich’s Contest #3解题报告 » ZOJ2367

ZOJ2367
ZOJ2367.cpp


#include <map>
#include <stack>
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int SIGMA = 10 + 26;

#ifndef ONLINE_JUDGE
#  define errf(...) do { fprintf(stderr, "%d:\t", __LINE__); fprintf(stderr, __VA_ARGS__); } while (false)
#else
#  define errf(...) do { } while (false)
#endif

inline int c2i(char c) {
	if (isdigit(c)) {
		return c - '0';
	} else if (islower(c)) {
		return c - 'a' + 10;
	} else {
		return -1;
	}
}

struct Trie {
	Trie* const pp;
	const char ch;
	int tag;
	Trie* p[SIGMA];

	Trie(Trie* pp, int ch) : pp(pp), ch(ch), tag(-1) {
		fill(p, p + SIGMA, (Trie*)NULL);
	}

	~Trie() {
		for (int i = 0; i < SIGMA; ++i) {
			delete p[i];
		}
	}

	Trie* insert(char* s) {
		Trie* p = this;
		for (int i = c2i(*s); i != -1; i = c2i(*++s)) {
			if (p->p[i] == NULL) {
				p->p[i] = new Trie(p, *s);
			}
			p = p->p[i];
		}
		return p;
	}

	Trie* find(char* s) {
		Trie* p = this;
		for (int i = c2i(*s); p && i != -1; i = c2i(*++s)) {
			p = p->p[i];
		}
		return p;
	}
};

template<typename Pred>
static void skip(char*& s, Pred f) {
	while (f(*s)) {
		++s;
	}
}

inline int _div(int b, int a) {
	int sign = (((b > 0) ^ (a > 0)) == 0) ? 1 : -1;
	return abs(b) / abs(a) * sign;
}

inline int _mod(int b, int a) {
	int sign = (((b > 0) ^ (a > 0)) == 0) ? 1 : -1;
	return abs(b) % abs(a) * sign;
}

inline int _pow(int b, int a) {
	int ret = 1;
	while (a > 0) {
		if (a & 1) {
			ret *= b;
		}
		a >>= 1;
		b = b * b;
	}
	return ret;
}

struct PC_Cool {
	int size;
	Trie* trie;
	vector<int> a;
	vector<Trie*> b;

	PC_Cool() {
		size = 0;
		trie = new Trie(NULL, '\0');
	}

	~PC_Cool() {
		delete trie;
	}

	int _root(int i) {
		return i == a[i] ? i : a[i] = _root(a[i]);
	}

	int _insert(char s[]) {
		Trie* p = trie->insert(s);
		if (p->tag == -1) {
			p->tag = size;
			a.push_back(size);
			b.push_back(p);
			++size;
		}
		return p->tag;
	}

	void define(char s[]) {
		skip(s, isspace);
		errf(s);
		int op1 = _insert(s);
		skip(s, isalnum);
		skip(s, isspace);
		errf(s);
		int op2 = _insert(s);
		// skip(s, isalnum);
		if (a[op1] == op1) {
			// An attempt to redefine some variable or constant is ignored.
			op2 = _root(op2);
			if (op2 != op1) {
				// An attempt to make a definition that leads to circular dependence is also ignored.
				a[op1] = op2;
				errf("%d->%d\n", op1, op2);
			}
		}
	}

	static void _op(stack<int>& operands, stack<char>& operators) {
		int a = operands.top();
		operands.pop();
		int b = operands.top();
		operands.pop();
		char c = operators.top();
		operators.pop();
		int d;
		switch (c) {
			case '+': d = b + a; break;
			case '-': d = b - a; break;
			case '*': d = b * a; break;
			case '/': d = _div(b, a); break;
			case '%': d = _mod(b, a); break;
			case '^': d = _pow(b, a); break;
		}
		errf("%d %c %d = %d\n", b, c, a, d);
		operands.push(d);
	}

	static bool _pr(char lhs, char rhs) {
		static pair<char, int> lpci[] = {
			make_pair('+', 8),
			make_pair('-', 8),
			make_pair('*', 5),
			make_pair('/', 5),
			make_pair('%', 5),
			make_pair('^', 4),
		};
		static pair<char, int> rpci[] = {
			make_pair('+', 9),
			make_pair('-', 9),
			make_pair('*', 6),
			make_pair('/', 6),
			make_pair('%', 6),
			make_pair('^', 3),
		};
		static map<char, int> lmci(lpci, lpci + sizeof(lpci) / sizeof(lpci[0]));
		static map<char, int> rmci(rpci, rpci + sizeof(rpci) / sizeof(rpci[0]));
		return lmci[lhs] < rmci[rhs];
	}

	int _find(char s[]) {
		static char buf[64];
		Trie* p = trie->find(s);
		if (p == NULL || p->tag == -1) {	// p->tag == -1 // Runtime Error on test 16
			char* t = s;
			skip(t, isalnum);
			copy(s, t, buf);
			buf[t - s] = '\0';
		} else {
			int l = 0;
			/*
			 * 居然能在某些环境过测试数据-_-b
			for (Trie* p = b[_root(p->tag)]; p->pp != NULL; p = pp->pp) {
				buf[l++] = p->ch;
			}
			 */
			for (Trie* pp = b[_root(p->tag)]; pp->pp != NULL; pp = pp->pp) {
				buf[l++] = pp->ch;
			}
			buf[l] = '\0';
			errf("%d[%s]\n", l, buf);
			reverse(buf, buf + l);
			errf("%d[%s]\n", l, buf);
		}
		errf("%s\n", buf);
		int ret = 0;
		for (int i = 0; buf[i] != '\0'; ++i) {
			if (isdigit(buf[i])) {
				ret *= 10;
				ret += buf[i] - '0';
			} else {
				// If some identifier is used in the expression that is not yet defined to be substituted by some integer constant, its value is set to zero.
				return 0;
			}
		}
		return ret;
	}

	int _eval(char*& s) {
		stack<int> operands;
		stack<char> operators;
		while (true) {
			// get_operand
			skip(s, isspace);
			errf(s);
			if (*s == '(') {
				++s;
				operands.push(_eval(s));
			} else {
				int sign = 1;
				while (*s == '+' || *s == '-') {
					// Unary minus and plus are allowed, their priority in this case is the highest.
					if (*s == '-') {
						sign = -sign;
					}
					++s;
					skip(s, isspace);
				}
				operands.push(sign * _find(s));
				skip(s, isalnum);
			}
			// get_operator
			skip(s, isspace);
			errf(s);
			if (*s == '\0' || *s == ')') {
				while (!operators.empty()) {
					_op(operands, operators);
				}
				++s;
				break;
			} else {
				while (!operators.empty() && _pr(operators.top(), *s)) {
					_op(operands, operators);
				}
				operators.push(*s);
				++s;
			}
			// process
		}
		return operands.top();
	}

	void print(char s[]) {
		errf(s);
		printf("%d\n", _eval(s));
	}

	void feed(char s[]) {
		if (s[0] == 'd') {
			// if (strncmp(s, "define", 6) == 0)
			define(s + 6);
		} else {
			// if (strncmp(s, "print", 5) == 0)
			print(s + 5);
		}
	}
};

int main() {
	int re;
	char buf[1024];

	scanf("%d", &re);
	fgets(buf, sizeof(buf), stdin);
	fgets(buf, sizeof(buf), stdin);
	for (int ri = 1; ri <= re; ++ri) {
		if (ri > 1) {
			puts("");
		}
		PC_Cool pc;
		while (fgets(buf, sizeof(buf), stdin) != NULL && buf[0] != '\n') {
			for (int i = 0; buf[i] != '\0'; ++i) {
				buf[i] = tolower(buf[i]);
			}
			pc.feed(buf);
		}
	}

	return 0;
}
//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name
//1828471 	2009-04-11 01:57:40 	Accepted 	2367 	C++ 	740 	13000 	watashi@Zodiac

//ID: 	Date'n'Time: 	Name: 	Task: 	.Ext: 	Status: 	Time: 	Memory:
//848138	10.04.09 21:55	watashi	215 	.CPP	Accepted	399 ms	13439 kb

//ID: 	Date'n'Time: 	Name: 	Task: 	.Ext: 	Status: 	Time: 	Memory:
//848139	10.04.09 21:58	watashi	215 	.CPP_VS	Accepted	249 ms	13211 kb
Leave a Reply