蓝桥杯算法训练VIP-删除多余括号 （C语言代码）

解题思路:

        详见T1194。

参考代码:

#include<stdio.h>
#include<string.h>

int level[123] = { 0 };

// 返回值为是否去括号 - 左括号下标 - 右括号下标
int ScanString(char *s, int start, int end);

int main() {

	char s[256], sc[256];
	int stack[256], top = -1, i;

	// 细分运算符优先级，便于判断
	level['+'] = 10, level['-'] = 11, level['*'] = 20, level['/'] = 21;
	//level['^'] = 31;

	while (scanf("%s", s) != EOF && s[0] != '#') {

		strcpy(sc, s); // 复制s，在sc中标记已经扫描的字符

		for (i = 0; i < strlen(s); i++) {

			if (sc[i] == '(') { // 左括号依次压栈

				stack[++top] = i;
			}
			if (sc[i] == ')') { // 遇到右括号时，左括号弹栈

				if (ScanString(sc, stack[top--], i)) { // 扫描括号内字符

					s[stack[top + 1]] = s[i] = '#'; // 标记原字符串，去括号
				}
			}
		}
		for (i = 0; i < strlen(s); i++) {

			if (s[i] != '#') printf("%c", s[i]);
		}
		printf("\n");
	}
	return 0;
}
int ScanString(char *s, int start, int end) {

	// 若有多层多余括号如 ((1+2))，直接返回删除一层括号
	if (start != 0 && end != strlen(s) - 1 && s[start - 1] == '(' && s[end + 1] == ')') {

		return 1;
	}

	int i, lev = 0, f;

	// 对该层括号内运算符进行优先级判断
	for (i = start, f = 1; i <= end; i++) {

		if (s[i] == '#') continue;

		if (level[s[i]] && f) { // 若为第一个运算符

			lev = level[s[i]]; // 直接标记优先级
			f = 0;
		}
		else if (level[s[i]]) { // 若有多个运算符，取较低的优先级

			lev = lev < level[s[i]] ? lev : level[s[i]];
		}
		s[i] = '#'; // 对判断过的字符进行标记
	}
	if (f) return 1; // 若括号内没有运算符，如(1)，直接去掉该层括号

	// 若为第0个字符 或 前一个字符也为左括号 或 括号内优先级较左边高 或 括号内优先级与左边相等且为 + * (结合律)，则左边满足
	if (start == 0 || s[start - 1] == '(' || lev > level[s[start - 1]] || lev == level[s[start - 1]] && !(lev % 10)) {

		// 若为最后一个字符 或 后一个字符也为右括号 或 括号内优先级较右边高/相等(左结合性) 或 如(a*b)/c 、(a-b)+c 类，则右边满足
		if (end == strlen(s) - 1 || s[end + 1] == ')' || lev >= level[s[end + 1]] || lev / 10 == level[s[end + 1]] / 10) {

			return 1; // 删除该层括号
		}
	}
	return 0;
}