由题意，我们可以建立一个二叉树。
然后中序遍历二叉树，得到最终的结果。
在中序遍历二叉树的时候，我们判断当前子树的根节点与其子节点的符号之间的关系。
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> #include<vector> #include<stack> #define LL long long #define INF 1000000000 using namespace std; struct list {char x;int l;int r;int leap; } node[5001]; char str[10001]; int vnum; int dos(int x,int y)//把str字符串从x到y这一段转化成 { //一颗二叉树，并且返回这颗二叉树的根节点int i,j;if(x==y){node[vnum].l=-1;node[vnum].r=-1;node[vnum].x=str[x];node[vnum].leap=0;vnum++;return vnum-1;}int vis[1001];stack<int>st;while(!st.empty())st.pop();vector<int>vec;vec.clear();int ns,ss;for(i=x; i<=y; i++){if(str[i]=='('){int sts=1;for(j=i+1; j<=y; j++){if(str[j]=='(')sts++;if(str[j]==')')sts--;if(sts==0)break;}int pp=dos(i+1,j-1);vec.push_back(pp);node[pp].leap=0;i=j;}else{vec.push_back(vnum);node[vnum].l=-1;node[vnum].r=-1;node[vnum].leap=1;node[vnum].x=str[i];vnum++;}}int len=vec.size();int ks[1001];int knum;knum=0;for(i=0; i<len; i++){int pp=vec[i];if((node[pp].leap==1)&&(node[pp].x=='*'||node[pp].x=='/')){int xx=ks[knum-1];knum--;node[pp].l=xx;node[pp].r=vec[i+1];i++;}ks[knum++]=pp;}int pa;pa=ks[0];for(i=1; i<knum; i++){int pp=ks[i];node[pp].l=pa;node[pp].r=ks[i+1];pa=pp;i++;}return pa; } int need(int x,int y,int leap)//判断以x为根，以y为子节点，在中序遍历的时候是否需要加（） {if(node[x].x=='/'&&leap==1){if(node[y].x=='+'||node[y].x=='-'||node[y].x=='*'||node[y].x=='/')return 1;}if(node[x].x=='*'||node[x].x=='/'){if(node[y].x=='+'||node[y].x=='-')return 1;}if(node[x].x=='-'&&leap==1){if(node[y].x=='+'||node[y].x=='-')return 1;}return 0; } void print(int x)//输出以x为根节点的中序遍历结果 {if(node[x].l!=-1){int ll=node[x].l;if(need(x,ll,0)){putchar('(');print(ll);putchar(')');}else{print(ll);}}putchar(node[x].x);if(node[x].r!=-1){int ll=node[x].r;if(need(x,ll,1)){putchar('(');print(ll);putchar(')');}else{print(ll);}}} int main() {int _,i,j;scanf("%d",&_);for(j=1; j<=_; j++){vnum=0;scanf("%s",str);int len=strlen(str);int st=dos(0,len-1);print(st);cout<<endl;}return 0; }