传送门 好的乱搞题一道。 先用栈处理出每个左或右括号对应的另一个右或左括号的下标。 然后求每个运算符的优先级。 具体是这样的： （1）定义一个临时变量j，表示当前位置的优先级，然后遍历表达式，初始j为1。 （2）进入一个括号j加2。（即遇到左括号） （3）+和-的优先级直接赋j。 （4）*和/的优先级赋j+1。 （5）退出一个括号j减2。（即遇到右括号） 当然我们要特判掉((sth))的情况，只要加2就ok辣。 预处理所有的优先级之后，就可以去括号了。 从1开始dfs。（当然为了方便处理，我们在原串两边加上一对括号。1号位置是那个左括号。） 每次dfs，先遍历串，处理之后的括号，保证正确性，同时还可以得到右括号的位置。 然后获取这两个括号左右位置的运算符的优先级，取最大的。 看括号内部是否有+或-号，这个不是直接看字符串，而是用优先级的大小关系判断。 如果有，那么不能去掉当前括号，返回。 如果没有，那么可以去掉，然后变号。 变号时，如果前面是减号，那么+变-，-变+。 如果前面是除号，那么变/，/变。 码量略大。
#include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 305 using namespace std; int n,a[N],le[N],ri[N],sta[N],top,T; char s[N]; int dfs(int l){ int r; for (r=l+1;s[r]!=')';r++) if (s[r]=='(') r=dfs(r); int k=max(a[l-1],a[r+1]),pos; for (pos=l+1;pos<r;pos++) if (a[pos]==k+1) break; if (pos<r) return r; s[l]=s[r]='$'; int cnt=0; if (s[l-1]=='-') for (int i=l+1;i<r;i++){ if (s[i]=='(') cnt++; else if (s[i]==')') cnt--; if (!cnt) if (s[i]=='-') s[i]='+'; else if (s[i]=='+') s[i]='-'; } if (s[l-1]=='/') for (int i=l+1;i<r;i++){ if (s[i]=='(') cnt++; else if (s[i]==')') cnt--; if (!cnt) if (s[i]=='*') s[i]='/'; else if (s[i]=='/') s[i]='*'; } return r; } void solve(){ memset(a,0,sizeof(a)); scanf("%s",s+2); n=strlen(s+2); s[1]='('; s[n+2]=')'; top=0; for (int i=1;i<=n;i++) if (s[i]=='(') sta[++top]=i; else if (s[i]==')'){ ri[sta[top]]=i; le[i]=sta[top]; top--; } a[0]=a[n+1]=1; for (int i=1,j=1;i<=n;i++) if (s[i]=='('&&(s[i-1]!='('||s[ri[i]+1]!=')')) j+=2; else if (s[i]==')'&&(s[i+1]!=')'||s[le[i]-1]!='(')) j-=2; else if (s[i]=='+'||s[i]=='-') a[i]=j; else if (s[i]=='*'||s[i]=='/') a[i]=j+1; dfs(1); for (int i=2;i<=n+1;i++) if (s[i]!='$') putchar(s[i]); puts(""); } int main(){ scanf("%d",&T); while (T--) solve(); }