去括号 （C语言代码）

解题思路:

    1、判断括号是否多余，即判断括号去除后运算顺序是否改变，亦即判断括号内外的运算符优先级，基本思路即括号内运算符优先级较高则可去括号；

    2、去括号，用特殊符号标记多余的括号。

    这里我用栈结构将左括号依次压栈，遇到右括号依次弹栈，由内而外逐层判断多余的括号。

注意事项:

    运算符优先级：^(幂) > /(除) *(乘) > -(减) +(加)；

    由于 - (/) 特殊性(第4点)，设置为：^(幂) > /(除) > *(乘) > -(减) > +(加) ，以便于判断。

    特殊情况较多，要逐个考虑：

    1、多层多余括号，如((((1+2))))、((((1))))，可直接去掉多层括号；

    2、单层多余括号，如(1)，可直接去掉该层括号；

    3、加法、乘法的结合律，如 1+(2+3) 或 1*(2*3)，括号内外运算符优先级相同，但也可去括号；

    4、括号左边符号为 - (/)，则去括号后括号内的 + (*) 会变号，故也不满足去括号，由优先级可直接判断；

    5、第4点带来的括号右边的额外判断，如 (1*2)/3 或 (1-2)+3，(原本优先级相同)，故满足去括号。

参考代码:

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

int level[95] = { 0 };

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

int main() {

	char s[50], sc[50];
	int stack[50], 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;
		}

		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;
}