首页 > 代码库 > UVALive 4882 Parenthesis 删除不必要的括号 模拟题

UVALive 4882 Parenthesis 删除不必要的括号 模拟题

题目链接:点击打开链接

题意:给定一个合法的序列,删掉所有不必要的括号。


#include <cstdio>
#include <cstring>

const int MAX_N = 10007;

char a[MAX_N];
int stack[MAX_N], top;
bool mark[MAX_N], stacknow[MAX_N];

int main() {
	while (1 == scanf("%s", a)) {
		int len = (int) strlen(a);
		top = 0;
		memset(mark, false, sizeof mark);
		for (int i = 0; i < len; ++i) {
			if (a[i] == '(') {
				stack[top++] = i;
				stacknow[top - 1] = false;
			} else if (a[i] == '+') {
				if (top) {
					stacknow[top - 1] = true;
				}
			} else if(a[i] == ')') {
				if ((stacknow[top - 1] && (stack[top - 1] - 1 >= 0 && a[stack[top - 1] - 1] != '+' && a[stack[top - 1] - 1] != '(' ||
				i + 1 < len && a[i + 1] != '+' && a[i + 1] != ')')) == 0) {
					if (stack[top - 1] - 1 >= 0 && a[stack[top - 1] - 1] == '(' && i + 1 < len && a[i + 1] == ')') 
						stacknow[top - 2] = stacknow[top - 1];
					mark[stack[top - 1]] = mark[i] = true;
				 }
			 	--top;
			}
		}
		for (int i = 0; i < len; ++i) {
			if (!mark[i]) putchar(a[i]);
	 	}
	 	puts("");
	}
	return 0;
}


UVALive 4882 Parenthesis 删除不必要的括号 模拟题