这道题是去除多余的括号。 思路是： 首先中缀表达是转后缀表达式。 这样得出的字符串是完全不包含括号的。 再把后缀表达式转变成中缀表达式，这时只要求加上必要的括号，这样就能保证括号最少。
对于中缀转后缀，一个栈 op 来存放运算符，括号。
对于字符串s 从头开始扫描， 遇见操作数直接输出到另一个字符串t,用来存放转化后的后缀表达式。 遇见操作符，首先定义优先级 * / 优先级2 ,大于 优先级为 1的 + -, ( 左括号具有最高优先级 3 如果op 为空，或者 当前栈顶元素为 '('则直接把当前处理字符（操作符） 入栈。或者当前栈顶操作符优先级小于 要处理的字符所代表的优先级也入栈。
如果当前栈顶元素小于或等于（不大于） 当前处理字符（操作符）的优先级。 则出栈并追加到t的末尾，直到栈顶元素优先级小于当前处理字符优先级，或者栈为空 然后再把当前处理字符入栈。
如果当前处理字符是 ） 则把栈顶元素出栈追加到 t末尾 ，直到遇见 （ ,( 不追加。
处理完字符串s后 最后把栈中所有元素追加到t 。 t就是后缀表达式。
详细参考博客： http://blog.csdn.net/sgbfblog/article/details/8001651
代码：
int priority(char c){ if(c=='+'||c=='-') return 1; else if(c=='*'||c=='/') return 2; else if(c=='(') return 3; } string middle2Back(string s){ string t; t=""; char tmp; stack<char> op; int n=s.length(); for(int i=0;i<n;i++){ // if is the num then output if(s[i]>='a'&&s[i]<='z'){ t+=s[i]; }else if(s[i]=='('){ // if is ( then push stack op op.push(s[i]); }else if(s[i]==')'){ // if is ) then output op until meet ( but do not output ( just pop ( while(!op.empty()){ tmp=op.top(); if(tmp=='('){ op.pop(); break; } t+=tmp; op.pop(); } } else { // else while(!op.empty()){ tmp=op.top(); int p1=priority(tmp); int p2=priority(s[i]); // if s[i] 's priority greater than top of stack op then push s[i] or s[i] is ( if(p2>p1||tmp=='(') break; // else output the stack op unitl meet a greater or ( t+=tmp; op.pop(); } op.push(s[i]); } } // add the remain of stack op while(!op.empty()){ t+=op.top(); op.pop(); } return t; }对于后缀如何转中缀呢？ 首先同样定义优先级，， 对于后缀表达式， 定于操作数拥有最高优先级 3， * ，/ 优先级为2 +,- 优先级为1, 同样需要一个栈 stack 来存放结果 。 随着处理会得到一些复合表达式，同样的这些复合表达式也应有优先级，复合表达式的优先级定义为 ，和最后一个运算的操作符的优先级相同。举例，如果一个符合表达式最后一个 + ,- 那么优先级和 +，-相同，同样也可能是和 *,/ 的优先级相同。 我们会把遇到操作符后每一步的结果都作为一个栈元素，入栈，所以需要定义一个结构体，为了方便我们进行操作。
struct Expre{ string exp; int p; // priority }从头扫描 后缀表达式字符串 t 对于操作数直接入栈， 对于操作符，对于 操作符 +: 从stack 出栈 2个元素，直接用+ 连接，并入栈，表达式优先级和+号相同。 对于操作符 -： 从栈顶出栈两个元素， 最先出栈的那个 加上括号()，并和第二个出栈的元素用 - 拼接 后重新入栈。 表达式优先级为 -。 操作符 *: 从栈顶出栈两个元素，对于优先级小于*的表达式加上括号，并用* 拼接后重新入栈，表达式优先级同 *. 对于操作符/: 从栈顶出栈两个元素，最先出栈元素表达式的优先级小于或等于 /优先级时，加上括号。 第二个出栈的元素表达式优先级小于/的优先级时，加上括号， 并用 /拼接后入栈， 处理完子符串t后，输出栈顶元素表达式即得到，加上括号的后缀转中缀的表达式。 代码：
string back2Middle(string t){ stack<Expre> st; string a=""; string b=""; string x; Expre tmp; Expre ta,tb; int n=t.length(); int p1; for(int i=0;i<n;i++){ if(t[i]>='a'&&t[i]<='z'){ tmp.exp=t[i]; tmp.p=3; st.push(tmp); }else if(t[i]=='+'){ //if op is + then just concate b=st.top().exp; st.pop(); a=st.top().exp; st.pop(); tmp.exp=a+'+'+b; tmp.p=1; st.push(tmp); }else if(t[i]=='-'){ tb=st.top(); st.pop(); ta=st.top(); st.pop(); p1=priority('-'); // + - is the smallest so, no one lower than p1 // if the op is - then the second need add () if its priority <= - if(tb.p<=p1){ b='('+tb.exp+')'; }else b=tb.exp; // no need charge because not less than - a=ta.exp; tmp.exp=a+'-'+b; tmp.p=1; st.push(tmp); }else if(t[i]=='*'){ //only the priority less than * need add () tb=st.top(); st.pop(); ta=st.top(); st.pop(); p1=priority('*'); if(tb.p<p1){ b='('+tb.exp+')'; }else b=tb.exp; if(ta.p<p1){ a='('+ta.exp+')'; }else a=ta.exp; tmp.exp=a+'*'+b; tmp.p=2; st.push(tmp); }else if(t[i]=='/'){ tb=st.top(); st.pop(); ta=st.top(); st.pop(); p1=priority('*'); // like - if the op is / then the second less or equal p1 need add () if(tb.p<=p1){ b='('+tb.exp+')'; }else b=tb.exp; //but the first is less need add (0 if(ta.p<p1){ a='('+ta.exp+')'; }else a=ta.exp; tmp.exp=a+'/'+b; tmp.p=2; st.push(tmp); } } return st.top().exp; }ＡＣ 代码：
#include <iostream> #include<cstring> #include<cstdio> #include<string> #include<stack> #include<vector> #include<queue> #include<algorithm> using namespace std; struct Expre{ string exp=""; int p=0; }; int priority(char c){ if(c=='+'||c=='-') return 1; else if(c=='*'||c=='/') return 2; else if(c=='(') return 3; } string middle2Back(string s){ string t; t=""; char tmp; stack<char> op; int n=s.length(); for(int i=0;i<n;i++){ // if is the num then output if(s[i]>='a'&&s[i]<='z'){ t+=s[i]; }else if(s[i]=='('){ // if is ( then push stack op op.push(s[i]); }else if(s[i]==')'){ // if is ) then output op until meet ( but do not output ( just pop ( while(!op.empty()){ tmp=op.top(); if(tmp=='('){ op.pop(); break; } t+=tmp; op.pop(); } } else { // else while(!op.empty()){ tmp=op.top(); int p1=priority(tmp); int p2=priority(s[i]); // if s[i] 's priority greater than top of stack op then push s[i] or s[i] is ( if(p2>p1||tmp=='(') break; // else output the stack op unitl meet a greater or ( t+=tmp; op.pop(); } op.push(s[i]); } } // add the remain of stack op while(!op.empty()){ t+=op.top(); op.pop(); } return t; } string back2Middle(string t){ stack<Expre> st; string a=""; string b=""; string x; Expre tmp; Expre ta,tb; int n=t.length(); int p1; for(int i=0;i<n;i++){ if(t[i]>='a'&&t[i]<='z'){ tmp.exp=t[i]; tmp.p=3; st.push(tmp); }else if(t[i]=='+'){ //if op is + then just concate b=st.top().exp; st.pop(); a=st.top().exp; st.pop(); tmp.exp=a+'+'+b; tmp.p=1; st.push(tmp); }else if(t[i]=='-'){ tb=st.top(); st.pop(); ta=st.top(); st.pop(); p1=priority('-'); // + - is the smallest so, no one lower than p1 // if the op is - then the second need add () if its priority <= - if(tb.p<=p1){ b='('+tb.exp+')'; }else b=tb.exp; // no need charge because not less than - a=ta.exp; tmp.exp=a+'-'+b; tmp.p=1; st.push(tmp); }else if(t[i]=='*'){ //only the priority less than * need add () tb=st.top(); st.pop(); ta=st.top(); st.pop(); p1=priority('*'); if(tb.p<p1){ b='('+tb.exp+')'; }else b=tb.exp; if(ta.p<p1){ a='('+ta.exp+')'; }else a=ta.exp; tmp.exp=a+'*'+b; tmp.p=2; st.push(tmp); }else if(t[i]=='/'){ tb=st.top(); st.pop(); ta=st.top(); st.pop(); p1=priority('*'); // like - if the op is / then the second less or equal p1 need add () if(tb.p<=p1){ b='('+tb.exp+')'; }else b=tb.exp; //but the first is less need add (0 if(ta.p<p1){ a='('+ta.exp+')'; }else a=ta.exp; tmp.exp=a+'/'+b; tmp.p=2; st.push(tmp); } } return st.top().exp; } int main() { int n; scanf("%d",&n); string s; string t; string result; while(n--){ cin>>s; t=middle2Back(s); result=back2Middle(t); cout<<result<<endl; } return 0; }