http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1646
题意 ： 话说我根本没读题，，，因为实在是太长了，我去看了输入输出才知道题讲的什么，大意是说给你一串运算式，里边包含了很多的多余的括号，让你去掉那些多余的括号，但是不能改变原来的式子中字母和运算符的位置。
思路 ：比赛的时候根本没做出来，当时并没有什么思路，一开始是单纯的以为模拟，但是想了想又不太是，所以没敢去做，这个题最重要的就是找到运算符的优先级，然后才能进行操作，所以可以先去掉所有的括号，然后再在合适的位置往上填括号即可。
先将题目中的中缀式转化成后缀表达式，这样就可以去掉所有的括号，而且也没有改变他的运算结果，然后再将后缀表达式转化成中缀式，在转化的过程下注意在该在的位置填上括号即可。
先说一下中缀式转化成后缀式的方法：用一个post数组来存要转化成的后缀式，再用一个栈来临时存运算符，然后将中缀式从头开始往后循环即可
1. 如果是数字直接存入数组即可。
2. 如果是左括号则直接入栈，如果是右括号，则不进栈，并且将左括号上边的那些运算符全部出栈并且按出栈顺序存到post数组中，然后左括号出栈，舍弃。
3. 如果是“+”或“-”，要将栈中左括号上方所有的运算符出栈并按出栈顺序存到post数组中，如果没有左括号，就全部出栈存到数组中，然后将新的加减号存到栈里。
4. 如果是“*或“/”，则判断栈顶是否为“*”“/”，如果是则其出栈，然后将新的乘除号入栈，如果不是则直接将新的乘除号入栈。
再说一下后缀式转中缀式，这个我不会，看了网上大神写的，看了一下觉得很不错。就是通过动态合并的方式进行的，例如，a Y b ，a，b作为表达式，Y是运算符，如果是a b Y的话，就可以将这两个表达式合并成a Y b了，然后再判断一下左表达式是否需要添加括号，当左表达式里有运算符+或-时并且Y是“*”"/"的时候左表达式需要加括号，而右表达式不光是这种情况，还有就是Y是“-”而右表达式中有+的时候，或者是Y是“/”而右表达式中有乘号的时候需要加括号，只要判断一下即可。
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stack> using namespace std ; char str[],post[] ;
int pre(char c)
{
int s = (c == '+' || c == '-') ? : ;
return s ;
}
void parse() {
// 因为表达式不定长，并且需要动态合并表达式，所以如果为每个表达式分配
// 定长空间，则浪费应该很严重。所以所有的表达式都存储在result这片空间上
// result可以理解为表达式栈。start[i]表示第i个表达式的起始下标,end[i]
// 表示结束下标，使用半开半闭区间，即第i个表达式长度为end[i]-start[i]。
// preStack为优先级栈，preStack[i]表示第i个表达式的优先级。
// cnt为当前产生的表达式个数。
char result[];
int len = strlen(post) ;
int start[];
int end[], preStack[];
int i, cnt = , preLeft, preRight, p, k, t;
start[] = end[] = ;
for(i = ; i < len; i++) {
if(isalpha(post[i])) {
++cnt;
start[cnt] = end[cnt-] + ;
result[start[cnt]] = post[i];
end[cnt] = start[cnt] + ;
preStack[cnt] = ;
} else {
p = pre(post[i]);
preLeft = preStack[cnt-];
preRight = preStack[cnt];
// 为左表达式加括号
if(preLeft < p) {
result[start[cnt-] - ] = '(';
start[cnt-] -= ;
result[end[cnt-]] = ')';
end[cnt-] += ;
}
// 为右表达式加括号
if(preRight < p || (preRight == p && (post[i] == '-' || post[i] == '/')))
{
result[start[cnt] - ] = '(';
start[cnt] -= ;
result[end[cnt]] = ')';
end[cnt] += ;
}
// 合并两个表达式
result[end[cnt-]] = post[i];
end[cnt-] += ;
for(k = end[cnt-], t = start[cnt]; t < end[cnt]; k++, t++)
result[k] = result[t];
end[cnt-] = k;
cnt -= ;
preStack[cnt] = p;
}
}
for(i = ; i <= cnt; i++) {
result[end[i]] = ;
printf("%s", result + start[i]);
}
printf("\n");
} void in()
{
int len = strlen(str) ;
int top = ;
stack<char>Q ;
for(int i = ; i < len ; i++)
{
switch(str[i])
{
case '+' :
case '-' :
while(!Q.empty() && Q.top() != '(')
{
post[top++] = Q.top() ;
Q.pop() ;
}
Q.push(str[i]) ;
break ;
case '(' :
Q.push(str[i]) ;
break ;
case ')' :
while(Q.top() != '(')
{
post[top++] = Q.top() ;
Q.pop() ;
}
Q.pop() ;
break ;
case '*' :
case '/' :
if(!Q.empty() && (Q.top() == '*' || Q.top() == '/'))
{
post[top++] = Q.top() ;
Q.pop() ;
}
Q.push(str[i]) ;
break ;
default:
post[top++] = str[i] ;
break ;
}
}
while(!Q.empty())
{
post[top++] = Q.top() ;
Q.pop() ;
}
post[top] = '\0' ;
}
int main()
{
int n ;
scanf("%d",&n) ;
while(n--)
{
scanf("%s",str) ;
in() ;
parse() ;
}
return ;
}