题目描述
当老师不容易，尤其是当小学的老师更难:现在的小朋友做作业喜欢滥用括号。
虽然不影响计算结果，但不够美观，容易出错，而且可读性差。但又不能一棒子打死，也许他们就是将来的“陈景润”呢！
为了减轻老师的工作，不至于他们工作到深夜，我们来写个程序把小朋友的作业做一下简单地处理，去掉那些多余的括号。
为了简化问题，所有式子里只存在小括号，运算符号包括+(加)、-(减)、*(乘)、/(除)、^(幂)。
注意：去掉多余的小括号不是指运算结果一样就可以。
比如：(1+2)^1 = 3。虽然把括号去掉1+2^1也等于3，但我们说这个括号不能去。
但如：1+(2+3) = 1+2+3只要是允许的，因为加法是满足交换律和结合律的。
输入格式
输入包括多组测试数据。
每组测试数据为一行算术表达式，只包括数字和运算符号，长度小于16。
输入以#行结束，该行不做处理。
输出格式
对应每组数据输入都有一行输出。
输出去掉多余的括号后的表达式。
样例输入
<span style="color:#333333"><span style="color:#333333">((((1))))+((((1)))) 1 1+1+1+1 ((1+2)+3)*4 (1+(2+3))*4 ((1*2)*3)*4 (1*(2*3))*4 ((1*2)*(3*4)) 1*((2*3)*4) 1*(2*(3*4)) ((1*2)*4)*3 (1*(2*4))*3 ((1*2)*(4*3)) 1*((2*4)*3) 1*(2*(4*3)) ((1+3)+2)*4 (1+(3+2))*4 ((1+3)*(2+4)) ((1*3)*2)*4 (1*(3*2))*4 ((1*3)*(2*4)) 1*((3*2)*4) 1*(3*(2*4)) ((1+3)*(4+2)) ((1*3)*4)*2 (1*(3*4))*2 ((1*3)*(4*2)) 1*((3*4)*2) 1*(3*(4*2)) ((1*4)*3)*2 (1*(4*3))*2 ((1*4)*(3*2)) 1*((4*3)*2) 1*(4*(3*2)) ((1*4)*2)*3 (1*(4*2))*3 ((1*4)*(2*3)) 1*((4*2)*3) 1*(4*(2*3)) ((2+1)+3)*4 (2+(1+3))*4 ((2*1)*3)*4 (2*(1*3))*4 ((2*1)*(3*4)) 2*((1*3)*4) 2*(1*(3*4)) ((2/1)*3)*4 ((2/1)*(3*4)) (2/(1/3))*4 2/(1/(3*4)) 2/((1/3)/4) ((2^1)*3)*4 ((2^1)*(3*4)) ((2*1)*4)*3 (2*(1*4))*3 ((2*1)*(4*3)) 2*((1*4)*3) 2*(1*(4*3)) ((2/1)*4)*3 ((2/1)*(4*3)) (2/(1/4))*3 2/(1/(4*3)) 2/((1/4)/3) ((2^1)*4)*3 ((2^1)*(4*3)) ((2+3)+1)*4 (2+(3+1))*4 ((2*3)*1)*4 (2*(3*1))*4 ((2*3)*(1*4)) 2*((3*1)*4) 2*(3*(1*4)) ((2*3)/1)*4 (2*(3/1))*4 2*((3/1)*4) ((2*3)/(1/4)) 2*(3/(1/4)) ((2*3)^1)*4 (2*(3^1))*4 2*((3^1)*4) ((2*3)*4)*1 (2*(3*4))*1 ((2*3)*(4*1)) 2*((3*4)*1) 2*(3*(4*1)) ((2*3)*4)/1 (2*(3*4))/1 ((2*3)*(4/1)) 2*((3*4)/1) 2*(3*(4/1)) ((2*3)*4)^1 (2*(3*4))^1 ((2*3)*(4^1)) 2*((3*4)^1) 2*(3*(4^1)) ((2^3)*(4-1)) ((2+4)*(3+1)) ((2*4)*3)*1 (2*(4*3))*1 ((2*4)*(3*1)) 2*((4*3)*1) 2*(4*(3*1)) ((2*4)*3)/1 (2*(4*3))/1 ((2*4)*(3/1)) 2*((4*3)/1) 2*(4*(3/1)) ((2*4)*3)^1 (2*(4*3))^1 ((2*4)*(3^1)) 2*((4*3)^1) 2*(4*(3^1)) ((2+4)*(1+3)) ((2*4)*1)*3 (2*(4*1))*3 ((2*4)*(1*3)) 2*((4*1)*3) 2*(4*(1*3)) ((2*4)/1)*3 (2*(4/1))*3 2*((4/1)*3) ((2*4)/(1/3)) 2*(4/(1/3)) ((2*4)^1)*3 (2*(4^1))*3 2*((4^1)*3) (2^(4-1))*3 ((3+2)+1)*4 (3+(2+1))*4 ((3*2)*1)*4 (3*(2*1))*4 ((3*2)*(1*4)) 3*((2*1)*4) 3*(2*(1*4)) ((3*2)/1)*4 (3*(2/1))*4 3*((2/1)*4) ((3*2)/(1/4)) 3*(2/(1/4)) ((3*2)^1)*4 (3*(2^1))*4 3*((2^1)*4) 3/(2^(1-4)) ((3*2)*4)*1 (3*(2*4))*1 ((3*2)*(4*1)) 3*((2*4)*1) 3*(2*(4*1)) ((3*2)*4)/1 (3*(2*4))/1 ((3*2)*(4/1)) 3*((2*4)/1) 3*(2*(4/1)) ((3*2)*4)^1 (3*(2*4))^1 ((3*2)*(4^1)) 3*((2*4)^1) 3*(2*(4^1)) 3*(2^(4-1)) ((3+1)+2)*4 (3+(1+2))*4 ((3+1)*(2+4)) ((3*1)*2)*4 (3*(1*2))*4 ((3*1)*(2*4)) 3*((1*2)*4) 3*(1*(2*4)) ((3/1)*2)*4 ((3/1)*(2*4)) (3/(1/2))*4 3/(1/(2*4)) 3/((1/2)/4) ((3^1)*2)*4 ((3^1)*(2*4)) ((3+1)*(4+2)) ((3*1)*4)*2 (3*(1*4))*2 ((3*1)*(4*2)) 3*((1*4)*2) 3*(1*(4*2)) ((3/1)*4)*2 ((3/1)*(4*2)) (3/(1/4))*2 3/(1/(4*2)) 3/((1/4)/2) ((3^1)*4)*2 ((3^1)*(4*2)) ((3*4)*1)*2 (3*(4*1))*2 ((3*4)*(1*2)) 3*((4*1)*2) 3*(4*(1*2)) ((3*4)/1)*2 (3*(4/1))*2 3*((4/1)*2) ((3*4)/(1/2)) 3*(4/(1/2)) ((3*4)^1)*2 (3*(4^1))*2 3*((4^1)*2) ((3*4)*2)*1 (3*(4*2))*1 ((3*4)*(2*1)) 3*((4*2)*1) 3*(4*(2*1)) ((3*4)*2)/1 (3*(4*2))/1 ((3*4)*(2/1)) 3*((4*2)/1) 3*(4*(2/1)) ((3*4)*2)^1 (3*(4*2))^1 ((3*4)*(2^1)) 3*((4*2)^1) 3*(4*(2^1)) ((4+2)*(3+1)) 4*((2+3)+1) 4*(2+(3+1)) ((4*2)*3)*1 (4*(2*3))*1 ((4*2)*(3*1)) 4*((2*3)*1) 4*(2*(3*1)) ((4*2)*3)/1 (4*(2*3))/1 ((4*2)*(3/1)) 4*((2*3)/1) 4*(2*(3/1)) ((4*2)*3)^1 (4*(2*3))^1 ((4*2)*(3^1)) 4*((2*3)^1) 4*(2*(3^1)) ((4+2)*(1+3)) 4*((2+1)+3) 4*(2+(1+3)) ((4*2)*1)*3 (4*(2*1))*3 ((4*2)*(1*3)) 4*((2*1)*3) 4*(2*(1*3)) ((4*2)/1)*3 (4*(2/1))*3 4*((2/1)*3) ((4*2)/(1/3)) 4*(2/(1/3)) ((4*2)^1)*3 (4*(2^1))*3 4*((2^1)*3) 4*((3+2)+1) 4*(3+(2+1)) ((4*3)*2)*1 (4*(3*2))*1 ((4*3)*(2*1)) 4*((3*2)*1) 4*(3*(2*1)) ((4*3)*2)/1 (4*(3*2))/1 ((4*3)*(2/1)) 4*((3*2)/1) 4*(3*(2/1)) ((4*3)*2)^1 (4*(3*2))^1 ((4*3)*(2^1)) 4*((3*2)^1) 4*(3*(2^1)) 4*((3+1)+2) 4*(3+(1+2)) ((4*3)*1)*2 (4*(3*1))*2 ((4*3)*(1*2)) 4*((3*1)*2) 4*(3*(1*2)) ((4*3)/1)*2 (4*(3/1))*2 4*((3/1)*2) ((4*3)/(1/2)) 4*(3/(1/2)) ((4*3)^1)*2 (4*(3^1))*2 4*((3^1)*2) 4*((1+3)+2) 4*(1+(3+2)) ((4*1)*3)*2 (4*(1*3))*2 ((4*1)*(3*2)) 4*((1*3)*2) 4*(1*(3*2)) ((4/1)*3)*2 ((4/1)*(3*2)) (4/(1/3))*2 4/(1/(3*2)) 4/((1/3)/2) ((4^1)*3)*2 ((4^1)*(3*2)) ((4-1)*(2^3)) 4*((1+2)+3) 4*(1+(2+3)) ((4*1)*2)*3 (4*(1*2))*3 ((4*1)*(2*3)) 4*((1*2)*3) 4*(1*(2*3)) ((4/1)*2)*3 ((4/1)*(2*3)) (4/(1/2))*3 4/(1/(2*3)) 4/((1/2)/3) ((4^1)*2)*3 ((4^1)*(2*3)) # </span></span>
样例输出
<span style="color:#333333"><span style="color:#333333">1+1 1 1+1+1+1 (1+2+3)*4 (1+2+3)*4 1*2*3*4 1*2*3*4 1*2*3*4 1*2*3*4 1*2*3*4 1*2*4*3 1*2*4*3 1*2*4*3 1*2*4*3 1*2*4*3 (1+3+2)*4 (1+3+2)*4 (1+3)*(2+4) 1*3*2*4 1*3*2*4 1*3*2*4 1*3*2*4 1*3*2*4 (1+3)*(4+2) 1*3*4*2 1*3*4*2 1*3*4*2 1*3*4*2 1*3*4*2 1*4*3*2 1*4*3*2 1*4*3*2 1*4*3*2 1*4*3*2 1*4*2*3 1*4*2*3 1*4*2*3 1*4*2*3 1*4*2*3 (2+1+3)*4 (2+1+3)*4 2*1*3*4 2*1*3*4 2*1*3*4 2*1*3*4 2*1*3*4 2/1*3*4 2/1*3*4 2/(1/3)*4 2/(1/(3*4)) 2/(1/3/4) 2^1*3*4 2^1*3*4 2*1*4*3 2*1*4*3 2*1*4*3 2*1*4*3 2*1*4*3 2/1*4*3 2/1*4*3 2/(1/4)*3 2/(1/(4*3)) 2/(1/4/3) 2^1*4*3 2^1*4*3 (2+3+1)*4 (2+3+1)*4 2*3*1*4 2*3*1*4 2*3*1*4 2*3*1*4 2*3*1*4 2*3/1*4 2*3/1*4 2*3/1*4 2*3/(1/4) 2*3/(1/4) (2*3)^1*4 2*3^1*4 2*3^1*4 2*3*4*1 2*3*4*1 2*3*4*1 2*3*4*1 2*3*4*1 2*3*4/1 2*3*4/1 2*3*4/1 2*3*4/1 2*3*4/1 (2*3*4)^1 (2*3*4)^1 2*3*4^1 2*(3*4)^1 2*3*4^1 2^3*(4-1) (2+4)*(3+1) 2*4*3*1 2*4*3*1 2*4*3*1 2*4*3*1 2*4*3*1 2*4*3/1 2*4*3/1 2*4*3/1 2*4*3/1 2*4*3/1 (2*4*3)^1 (2*4*3)^1 2*4*3^1 2*(4*3)^1 2*4*3^1 (2+4)*(1+3) 2*4*1*3 2*4*1*3 2*4*1*3 2*4*1*3 2*4*1*3 2*4/1*3 2*4/1*3 2*4/1*3 2*4/(1/3) 2*4/(1/3) (2*4)^1*3 2*4^1*3 2*4^1*3 2^(4-1)*3 (3+2+1)*4 (3+2+1)*4 3*2*1*4 3*2*1*4 3*2*1*4 3*2*1*4 3*2*1*4 3*2/1*4 3*2/1*4 3*2/1*4 3*2/(1/4) 3*2/(1/4) (3*2)^1*4 3*2^1*4 3*2^1*4 3/2^(1-4) 3*2*4*1 3*2*4*1 3*2*4*1 3*2*4*1 3*2*4*1 3*2*4/1 3*2*4/1 3*2*4/1 3*2*4/1 3*2*4/1 (3*2*4)^1 (3*2*4)^1 3*2*4^1 3*(2*4)^1 3*2*4^1 3*2^(4-1) (3+1+2)*4 (3+1+2)*4 (3+1)*(2+4) 3*1*2*4 3*1*2*4 3*1*2*4 3*1*2*4 3*1*2*4 3/1*2*4 3/1*2*4 3/(1/2)*4 3/(1/(2*4)) 3/(1/2/4) 3^1*2*4 3^1*2*4 (3+1)*(4+2) 3*1*4*2 3*1*4*2 3*1*4*2 3*1*4*2 3*1*4*2 3/1*4*2 3/1*4*2 3/(1/4)*2 3/(1/(4*2)) 3/(1/4/2) 3^1*4*2 3^1*4*2 3*4*1*2 3*4*1*2 3*4*1*2 3*4*1*2 3*4*1*2 3*4/1*2 3*4/1*2 3*4/1*2 3*4/(1/2) 3*4/(1/2) (3*4)^1*2 3*4^1*2 3*4^1*2 3*4*2*1 3*4*2*1 3*4*2*1 3*4*2*1 3*4*2*1 3*4*2/1 3*4*2/1 3*4*2/1 3*4*2/1 3*4*2/1 (3*4*2)^1 (3*4*2)^1 3*4*2^1 3*(4*2)^1 3*4*2^1 (4+2)*(3+1) 4*(2+3+1) 4*(2+3+1) 4*2*3*1 4*2*3*1 4*2*3*1 4*2*3*1 4*2*3*1 4*2*3/1 4*2*3/1 4*2*3/1 4*2*3/1 4*2*3/1 (4*2*3)^1 (4*2*3)^1 4*2*3^1 4*(2*3)^1 4*2*3^1 (4+2)*(1+3) 4*(2+1+3) 4*(2+1+3) 4*2*1*3 4*2*1*3 4*2*1*3 4*2*1*3 4*2*1*3 4*2/1*3 4*2/1*3 4*2/1*3 4*2/(1/3) 4*2/(1/3) (4*2)^1*3 4*2^1*3 4*2^1*3 4*(3+2+1) 4*(3+2+1) 4*3*2*1 4*3*2*1 4*3*2*1 4*3*2*1 4*3*2*1 4*3*2/1 4*3*2/1 4*3*2/1 4*3*2/1 4*3*2/1 (4*3*2)^1 (4*3*2)^1 4*3*2^1 4*(3*2)^1 4*3*2^1 4*(3+1+2) 4*(3+1+2) 4*3*1*2 4*3*1*2 4*3*1*2 4*3*1*2 4*3*1*2 4*3/1*2 4*3/1*2 4*3/1*2 4*3/(1/2) 4*3/(1/2) (4*3)^1*2 4*3^1*2 4*3^1*2 4*(1+3+2) 4*(1+3+2) 4*1*3*2 4*1*3*2 4*1*3*2 4*1*3*2 4*1*3*2 4/1*3*2 4/1*3*2 4/(1/3)*2 4/(1/(3*2)) 4/(1/3/2) 4^1*3*2 4^1*3*2 (4-1)*2^3 4*(1+2+3) 4*(1+2+3) 4*1*2*3 4*1*2*3 4*1*2*3 4*1*2*3 4*1*2*3 4/1*2*3 4/1*2*3 4/(1/2)*3 4/(1/(2*3)) 4/(1/2/3) 4^1*2*3 4^1*2*3</span></span>
对于这类输出结果较多的题目，我在网上学习到一种方法，可以通过cmd命令，比较结果和正确答案，具体步骤如下
1.打开一个名为"1.txt"的文件，并将结果写入该文件。在循环中，将结果写入文件。
使用is_open函数来检查文件是否成功打开，使用cerr流输出错误信息
#include <iostream> #include <fstream> int main() { std::ofstream mycout("文件地址/1.txt"); if (mycout.is_open()) { // 文件打开成功，执行写入操作 while (多组数据) { mycout << 你的结果; } mycout << std::endl; } else { // 文件打开失败，输出错误信息 std::cerr << "无法打开文件" << std::endl; } return 0; }
也可以直接抛异常
#include <iostream> #include <fstream> #include <stdexcept> int main() { std::ofstream mycout("文件地址/1.txt"); if (mycout.is_open()) { // 文件打开成功，执行写入操作 while (多组数据) { mycout << 你的结果; } mycout << std::endl; } else { // 文件打开失败，抛出异常 throw std::runtime_error("无法打开文件"); } return 0; }
2.将样例放入另一个文件中，用win+R，输入cmd命令
fc 文件1 文件2
3. 比较两个文件
如果有错误则显示：
如果无错误则显示：
接下来是解题思路
设置优先级
level['^']=6; level['/']=4; level['*']=3; level['-']=2; level['+']=1;
注：
●这里“-”的优先级要比“+”大
例如：
a+(b+c)可以去括号，但是a-(b+c)去括号后，括号的“+”要变“-”,如果不变答案将不同
●这里的“/”的优先级要比“*”大
例如：
a * (b * c)可以去括号，(a*b)/c去括号也不会影响结果，因为式子本来就是从左至右进行运算的，但是a/(b * c)去括号后结果可能不同
24/（3*2）=4
而从左至右计算 24/3*2=16
●level[^]为6，而不是5
这是因为a * (b * c)可以去括号，但存在一种特殊情况：a/(b/c)在程序中是可以去括号的，因为括号内外优先级一致，但实际上却不行，level[‘^’]之所以6是为了留出一个5来解决这个问题
去括号
我用一个bool tag[]数组，初始全true，判断一对括号应该除去时，两个位置都置false。
防止数组越界
为了防止数组越界，在分析过程中，只分析到倒数第二个字符，最后一个字符单独分析
代码如下：
●首先，设计一个栈，它用来存放左括号【的数组下标！】
●遍历这个式子（字符串），遇到左括号则入栈，遇到【右括号】：
●看看它的右边（右括号的右边），它可能是运算符，也可能又是一个右括号（但不会是数字）
●看看它对应的左括号（栈顶元素）的左边（括号前面），它可能是一个运算符，也可能左边越界了
●处理一下越界等特殊情况，你拿到了： 运算符1（式子）运算符2
●这个时候需要精准判断，只有在括号中的式子的全部符号【优先级】都比两个运算符【大于等于】的情况下括号才能去掉
（普遍情况）
//只有在括号中的式子的全部符号【优先级】都比两个运算符【大于等于】的情况下括号才能去掉
//括号前面是"/",lev要++，使lev从’4‘到‘5’
（特殊情况）
//（a*b）/c这是要去括号的,因为式子本来就是从左到右进行运算，但是c/(a*b)会影响结果
#include<cstdio> #include<cstring> #include<iostream> #include<stack> #include<map> using namespace std; int main() { string c; stack<int> s;//定义一个栈 map<char,int> level; while(cin>>c) { level['^']=6;level['/']=4;level['*']=3;level['-']=2;level['+']=1; if(c=="#") break; int len = c.length(); bool tag[len]; memset(tag,true,sizeof(tag)); for(int i=0; i<len-1; i++) { if(c[i]=='(') { s.push(i); } else if(c[i]==')') { bool ok = true; int lev1,lev2; //括号后面 lev1=lev2=0; //初始化最小 //lev1表示括号后面的运算符，lev2表示括号前面的运算符 int back_chu = 0; int all_cheng = 1; if(c[i+1]!=')') { //右括号后边是运算符 lev1 = level[c[i+1]]; //括号后面 if(c[i+1]=='/') back_chu=1; } if(s.top()!=0) { //括号前面有运算符 lev2 = level[c[s.top()-1]]; //括号前面 if(c[s.top()-1]=='/') lev2++; } for(int j=s.top()+1; j<=i-1; j++) {//遍历括号里面的内容 if(!isdigit(c[j]) && c[j]!='(' && c[j]!=')') {//如果c[j]是运算符 if(c[j]!='*') all_cheng = 0; if(level[c[j]]<lev1 || level[c[j]]<lev2) { //只有在括号中的式子的全部符号【优先级】都比两个运算符【大于等于】的情况下括号才能去掉 ok = false; if(lev2==6) level[c[j]]=6; //幂的情况 break; } } } if(ok || (back_chu && all_cheng)) { //（普遍情况） //只有在括号中的式子的全部符号【优先级】都比两个运算符【大于等于】的情况下括号才能去掉 //括号前面是"/",lev要++ //普遍情况靠比较lev大小判断 // 或（||） //（特殊情况） //（a*b）/c这是要去括号的,但是c/(a*b)会影响结果 tag[i] = tag[s.top()] = false; } s.pop(); } } if(c[len-1]==')' && c[s.top()]=='(') { //单独分析最后一个元素，他只可能是数字或者"）",这里是")" if(s.top()==0) { //类似((a+b）* (b+c)) tag[len-1] = tag[s.top()] = false; } else {//这里是数字，类似于4/(1/2)*3 int lev3 = level[c[s.top()-1]]; if(c[s.top()-1]=='/') lev3++;//类似a/(b/c)的特殊情况，上升为'5' bool ok = true; for(int j=s.top()+1; j<=len-2; j++) {//这是对括号里的内容进行遍历 //例如,4/(1/2)*3,3位置为len,"*"为len-1,")"为len-2 if(!isdigit(c[j]) && c[j]!='(' && c[j]!=')') {//和之前的处理相同 if(level[c[j]]<lev3) { ok = false; break; } } } if(ok) { tag[len-1] = tag[s.top()] = false;//去括号 } } s.pop(); } for(int i=0; i<len; i++) { if(tag[i]) cout<<c[i]; } cout<<endl; } return 0; }
