ZOJ 1423 (Your)((Term)((Project))) （模拟+数据结构）

题目链接：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 ;

 }

巴特西

ZOJ 1423 (Your)((Term)((Project))) （模拟+数据结构）

最新文章

热门文章