本文主要是介绍B - Brackets Removal Gym - 101334B 模拟题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意:
去括号,如果括号前有减号,那么里面变号
如果前面有除号,里面也要变号
题解:
模拟,括号包含的数据越少越先处理,从里去括号到外面
大概的思路:
取出所有匹配括号对的序号
然后按照间距从小到大处理括号
注意的是下面这组样例:
a/(b*(c+d/g))
a-(d+c*(d-h))
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define MAXN 1010
char str[MAXN];
int visit[MAXN];struct position
{int l,r;int diff;
}a[MAXN];int cmp(const void *a,const void *b)
{position *x=(position *)a;position *y=(position *)b;return x->diff - y->diff;
}int judge(char ch)
{if(ch=='*'||ch=='/')return 1;return 0;
}int main()
{//freopen("in.txt","r",stdin);freopen("brackets.in","r",stdin);freopen("brackets.out","w",stdout);while(scanf("%s",str)!=EOF){int p=1,cnt=0;memset(a,-1,sizeof(a));memset(visit,0,sizeof(visit));int len=strlen(str);for(int i=0;i<len;i++){if(str[i]=='('){visit[i]=p++;a[cnt++].l=i;}else if(str[i]==')'){visit[i]=--p;for(int j=cnt-1;j>=0;j--){if(visit[a[j].l]==visit[i]&&a[j].r==-1)a[j].r=i,a[j].diff=a[j].r-a[j].l;}}}qsort(a,cnt,sizeof(a[0]),cmp);int left,right,flag;for(int i=0;i<cnt;i++){left=a[i].l;right=a[i].r;flag=1;for(int j=left+1;j<right;j++){if(visit[j]!=-3&&(str[j]=='-'||str[j]=='+')){flag=0;break;}}if(flag){visit[left]=visit[right]=-1;if(str[left-1]=='/'){for(int j=left+1;j<right;j++){if(visit[j]==-3)continue;if(str[j]=='*')str[j]='/';else if(str[j]=='/')str[j]='*';}}continue;}if(judge(str[left-1])==0&&judge(str[right+1])==0){visit[left]=visit[right]=-1;if(str[left-1]=='-'){for(int j=left+1;j<right;j++){if(visit[j]==-3)continue;if(str[j]=='-')str[j]='+';else if(str[j]=='+')str[j]='-';}}continue;}if(flag==0){for(int j=left+1;j<right;j++)if(visit[j]!=-1)visit[j]=-3;}}for(int i=0;i<len;i++){if(visit[i]!=-1)printf("%c",str[i]);}puts("");}return 0;
}
这篇关于B - Brackets Removal Gym - 101334B 模拟题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!