1 条题解

  • 0
    @ 2025-7-17 22:36:34
    #include <iostream>
    #include <cstring>
    #include <stack>
    #include <cstdio>
    using namespace std;
    
    char a[300];  // 存储处理后的表达式(去除空格)
    char b[300];  // 存储原始输入行(包含空格)
    int tag[300];  // 标记括号所属的配对组
    int flag[300];  // 标记括号是否为冗余括号
    int len;
    stack<int> s;
    
    // 查找与当前括号配对的另一个括号的位置
    int find(int num) {
    	for (int i = 0; i < len; ++i) {
    		if (tag[i] == num) {
    			return i;
    		}
    	}
    	return -1;
    }
    
    // 判断区间 [x, y] 内是否全为操作数(无运算符)
    int fun(int x, int y) {
    	for (int i = x; i <= y; ++i) {
    		if (a[i] == '+' || a[i] == '-') {
    			return 0;
    		}
    	}
    	return 1;
    }
    
    int main() {
    	int t;
    	scanf("%d", &t);
    	getchar();  // 读取换行符
    	
    	while (t--) {
    		memset(b, 0, sizeof(b));  // 初始化缓冲区
    		if (fgets(b, sizeof(b), stdin) == NULL) {  // 使用 fgets 安全读取行
    			break;
    		}
    		
    		// 去除原始输入中的空格,存入 a 数组
    		int pot = 0;
    		for (int tot = 0; b[tot] != '\0'; ++tot) {
    			if (b[tot] != ' ') {
    				a[pot++] = b[tot];
    			}
    		}
    		len = pot;  // 更新有效长度(去除空格后的长度)
    		
    		// 初始化栈和括号标记数组
    		while (!s.empty()) {
    			s.pop();
    		}
    		memset(tag, 0, sizeof(tag));
    		int cot = 0;
    		
    		// 为括号分配配对组标签
    		for (int i = 0; i < len; ++i) {
    			if (a[i] == '(') {
    				tag[i] = ++cot;
    				s.push(i);
    			} else if (a[i] == ')') {
    				if (!s.empty()) {
    					tag[i] = tag[s.top()];
    					s.pop();
    				} else {
    					tag[i] = 0;  // 处理不合法的括号(题目保证输入合法,此处理可省略)
    				}
    			} else {
    				tag[i] = 0;
    			}
    		}
    		
    		// 标记冗余括号
    		memset(flag, 0, sizeof(flag));
    		for (int i = 0; i < len; ++i) {
    			if (a[i] == '(') {
    				int group = tag[i];
    				int pair = find(group);  // 配对的右括号位置
    				
    				// 情况 1:括号在表达式开头,且内部非单一操作数
    				if (i == 0 && pair - i > 2 && !fun(i+1, pair-1)) {
    					flag[group] = 1;
    				}
    				// 情况 2:括号前是 '+',且内部非单一操作数
    				else if (i > 0 && a[i-1] == '+' && pair - i > 2 && !fun(i+1, pair-1)) {
    					flag[group] = 1;
    				}
    				// 情况 3:括号前是另一个左括号(嵌套括号冗余)
    				else if (i > 0 && a[i-1] == '(') {
    					flag[group] = 1;
    				}
    				// 情况 4:括号前是 '-',但内部是单一操作数(此时括号冗余)
    				else if (i > 0 && a[i-1] == '-' && fun(i+1, pair-1)) {
    					flag[group] = 1;
    				}
    			}
    		}
    		
    		// 输出去除冗余括号的表达式
    		for (int i = 0; i < len; ++i) {
    			if (a[i] == '(' || a[i] == ')') {
    				int group = tag[i];
    				if (flag[group] == 0) {  // 非冗余括号才输出
    					cout << a[i];
    				}
    			} else {
    				cout << a[i];
    			}
    		}
    		cout << endl;
    	}
    	return 0;
    }
    • 1

    信息

    ID
    691
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    8
    已通过
    1
    上传者