题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=423
Sample Input
3
(A-B + C) - (A+(B - C)) - (C-(D- E) )
((A)-( (B)))
A-(B+C)
Sample Output
A-B+C-(A+B-C)-(C-(D-E))
A-B
A-(B+C)
题目大意：给出加减代数表达式，仅由变量（大写字母表示），圆括号，加号 '+', 减号'-'组成，要求去掉多余的括号，但是不能改变表达式中的加号和减号，也就是说如果括号外面是减号，那就不能去掉
分析：
对于每对括号标号，满足以下任意一个条件的就可以去掉，
1.最外面的括号
2.前面不是 减号 的括号
3.前面是减号，但左右括号之间仅有变量，而没有 加减号 的括号。
第一反应是用栈做，但是STL的stack用在本题不方便,因为本题要遍历栈的元素，所以要自己写栈。
代码如下：
# include<cstdio>
# include<iostream>
# include<cstring>
# define MAX
using namespace std;
char str[MAX]; //输入
char st[MAX]; //自定义栈
int main(){
int T;
scanf("%d",&T);
getchar();
while(T--){
int i,j;
gets(str);
int len=strlen(str);
st[]=' '; //如果第一个字符是'('，将情况1变成了情况2，少讨论
int tail=; //尾指针
for(i=; i<len; i++){
if(str[i]==')'){
bool flag = true; //默认为括号里边不包含其他的'+'或'-'
for(j=tail-; j>=; j--){
if(st[j]=='('){
if(st[j-]!='-'||st[j-]=='-'&&flag)//括号前面不是减号 或者虽是减号但仅包含变量
st[j]=' ';//取消该左括号，并且不要右括号，即不处理它
else{
st[tail++]='Y'; //代表右括号
st[j]='X'; //代表左括号
}
break;
}
else{
if(st[j]=='+'||st[j]=='-')
flag = false;
}
}
}
else{
if(str[i]!=' ')
st[tail++]=str[i];
}
}
for(i=; i!=tail; i++){ //遍历栈元素
if(st[i] != ' '){
if(st[i] == 'X')
cout<< "(";
else if(st[i] == 'Y')
cout<< ")";
else
cout<<st[i];
}
}
cout<<endl;
}
return ;
}
附贴网上大部分人的思路：由于是模拟题，数据很小，直接暴力就好了。先扫描一次将空格去掉，再不断扫描，将（A）类型的括号去掉，直到不能去为止。再扫描一次，将所有括号用match数组匹配起来，若 s[i]==')' 那么 match[i]为与它匹配的'('所在的下标。再扫描一次，将'('前面不为负号的括号对全部标记mark[i]=1表示可以去掉。最后扫描一次，根据mark[i]数组将多余括号去掉~~~
#include<stdio.h>
#include<string.h>
char s[];
int mark[],match[],zhan[],num,opnum;
int main()
{
int m,i,j,l,temp; scanf("%d",&m);
getchar();
while(m--)
{
gets(s);
memset(mark,-,sizeof(mark));
memset(match,-,sizeof(match));
for(l=strlen(s),i=j=;i<l;i++)
{
if(s[i]==' ') continue;
s[j++]=s[i];
}
l=j,s[j]='\0',temp=;
while(temp)
{
for(temp=j=i=;i<l;i++)
{
if(s[i]=='('&&s[i+]==')')
s[j++]=s[i+],i=i+,temp=;
else s[j++]=s[i];
}
l=j,s[j]='\0';
}
for(num=i=;i<l;i++)
{
if(s[i]=='(') match[i]=i,zhan[num++]=i;
else if(s[i]==')') num--,match[i]=zhan[num];
}
for(i=,temp=;i<l;i++)
{
if(s[i]=='('&&temp==) mark[i]=;
else if(s[i]==')'&&mark[match[i]]==) mark[i]=;
if(s[i]=='-') temp=;
else temp=;
}
for(i=j=;i<l;i++)
{
if(s[i]=='('&&mark[i]==) continue;
else if(s[i]==')'&&mark[i]==) continue;
s[j++]=s[i];
}
s[j]='\0';
printf("%s\n",s);
} return ;
}