演算法筆記 - Parser

Parser

目前以我能力所及只能提供題目。題目為熱心網友整理而得。

UVa 134 171 172 174 189 198 506 533 586 692 738 10151 10155 10267 10435 10454 10467

正整數四則運算，運算子無優先順序。

正整數四則運算，運算子無優先順序，有括號。

char s[100] = "(1 + 2) * ((3 - 4) / 5)";

int calc(int lv, char op, int rv)
{
	if (op == '+') return lv + rv;
	if (op == '-') return lv - rv;
	if (op == '*') return lv * rv;
	if (op == '/') return lv / rv;
	return 0;	// crash
}

// 找到對應的右括號
int balance(int L, int R)
{
	int c = 1;
	for (int k=L+1; k<=R; ++k) {
		if (s[k] == '(') c++;
		if (s[k] == ')') c--;
		if (c == 0) return k;
	}
	return -1;
}

bool isopera(char c)
{
	return c == '+' || c == '-' || c == '*' || c == '/';
}

// 尋找運算子的位置
int findopera(int L, int R)
{
	for (int k=L; k<=R; ++k)
		if (isopera(s[k]))
			return k;
	return -1;
}

// 擷取數值
int getnum(int L, int R)
{
	int n = 0;
	for (int k=L; k<=R; ++k)
		n = n * 10 + s[k] - '0';
	return n;
}

int f(int L, int R)
{
	if (s[L] == '(')
	{
		int op = balance(L, R) + 1;
		if (op > R) return f(L+1, op-2);
		return calc(f(L+1, op-2), s[op], f(op+1, R));
	}

int op = findopera(L, R);
	if (op != -1) return calc(f(L, op-1), s[op], f(op+1, R));
	return getnum(L, R);
}

int evaluate()
{
	int length = tight(s);
	return f(0, length-1);
}

整數係數，三元多次多項式。

UVa 126 172 695