Gym

题意：给一个包含括号的字符串，要你把所有能去掉的括号都去掉，然后再把原字符串输出

思路：首先对括号进行配对，配对完之和，对括号进行排序（按照左右两括号的距离差进行排序），之后再进行判断

有几种情况

1.对于括号前面和后母没有符号的，那么说明这个括号是一定可以去掉的

2.对于括号前面是加号括号后面没有乘除的话，也是可以去掉的

3.对于减号的话，如果可以去掉括号，记得加减变号

4.对于乘除，得看里面有没有+-，有的话，说明这个括号是不能去掉的，不能去掉的时候，记得进行标记，目的是下次扫描可以跳过这个括号

除法和减法可以变号

代码写得有点乱

  1 //locy
  2 
  3 #include <algorithm>
  4 #include <stdio.h>
  5 #include <string.h>
  6 #include <stack>
  7 using namespace std;
  8 
  9 char str[1010];
 10 struct Brackets{
 11     int x,y;
 12     int dis;
 13 }brackets[500];
 14 bool change[1005];
 15 stack<int>s;
 16 
 17 bool cmp(const Brackets &a,const Brackets &b)
 18 {
 19     return a.dis<b.dis;
 20 }
 21 
 22 int main()
 23 {
 24     freopen("brackets.in","r",stdin);
 25     freopen("brackets.out","w",stdout);
 26     //freopen("in.txt","r",stdin);
 27     scanf("%s",str+1);
 28     int len = strlen(str+1);
 29     int k = 0;
 30     for(int i = 1 ; i <= len ; i++ )
 31     {
 32         if(str[i] == '(')
 33             brackets[k].x = i,s.push(k++);
 34         else if(str[i] == ')')
 35             brackets[s.top()].y = i,s.pop();
 36     }
 37     for(int i = 0;i<k;i++)
 38         brackets[i].dis = brackets[i].y-brackets[i].x;
 39     sort(brackets,brackets+k,cmp);
 40     for(int i = 0;i<k;i++)
 41     {
 42         int flag = -1;
 43         switch(str[brackets[i].x-1])
 44         {
 45             case '+':
 46                 flag = 0;
 47                 break;
 48             case '-':
 49                 flag = 1;
 50                 break;
 51             case '*':
 52                 flag = 2;
 53                 break;
 54             case '/':
 55                 flag = 3;
 56                 break;
 57             default:
 58                 break;
 59         }
 60         bool flag2 = (str[brackets[i].y+1]=='*'||str[brackets[i].y+1]=='/')?
 61             true:false;
 62         if(flag<=0&&!flag2)  //加法以及没符号
 63                change[brackets[i].x] = change[brackets[i].y] = true;
 64         else if(flag==1&&!flag2)  //减法
 65         {
 66             change[brackets[i].x] = change[brackets[i].y] = true;
 67             bool tmp = false;
 68             for(int j = brackets[i].x;j<=brackets[i].y;j++)
 69             {
 70                 if(!change[j])     //切记这个，因为没去掉的括号里面的是不需要管的
 71                 {
 72                     if(str[j]=='+')
 73                         str[j]='-';
 74                     else
 75                         if(str[j]=='-')
 76                         str[j] = '+';
 77                 }
 78             }
 79         }else //乘除判断
 80         {
 81             int tmp = false;
 82             for(int j = brackets[i].x; j < brackets[i].y ; j++ )
 83                 if(!change[j]&&(str[j]=='+'||str[j]=='-'))
 84                         tmp = true;
 85             if(!tmp)
 86             {
 87                 for(int j = brackets[i].x;j<=brackets[i].y;j++)
 88                 {
 89                     if(flag == 3&&str[j]=='*'&&!change[j])
 90                         str[j] ='/';
 91                     else if(flag==3&&str[j]=='/'&&!change[j])
 92                         str[j]='*';
 93                 }
 94                 change[brackets[i].x] = change[brackets[i].y] = true;
 95             }
 96             else for(int j = brackets[i].x+1;j<brackets[i].y;j++)
 97                 if(str[j]!=')'&&str[j]!='(')
 98                     change[j] = true;
 99 
100         }
101     }
102     //输出
103     for(int i = 1;i<=len;i++)
104         if(str[i]=='('||str[i]==')')
105         {
106             if(!change[i])
107                 printf("%c",str[i]);
108         }
109         else printf("%c",str[i]);
110         printf("
");
111     return 0;
112 }

相关推荐