【bzoj1561】[JSOI2009]去括号
2024-08-26 20:01:49
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define maxn 100001 using namespace std; char s[maxn];
bool w[maxn];
int S[maxn],n,top,tt,T; bool pd(int l,int r)
{
for (int i=l;i<=r;i++)
{
if (s[i]=='(' && !w[i])
tt++;
if (s[i]==')' && !w[i])
tt--;
if (!tt && (s[i]=='+' || s[i]=='-'))
return 0;
}
return 1;
} int main()
{
scanf("%d",&T);
while (T--)
{
memset(s,0,sizeof(s));
memset(w,0,sizeof(w));
memset(S,0,sizeof(S));
scanf("%s",s+1);
n=strlen(s+1);
for (int i=1,nn;i<=n;i++)
{
if (s[i]=='(')
S[++top]=i;
else if (s[i]==')')
{
nn=S[top--];
if (s[nn-1]=='/'||s[nn-1]=='*'||s[i+1]=='*'||s[i+1]=='/')
{
if (pd(nn+1,i-1))
{
w[nn]=w[i]=1;
if (s[nn-1]=='/')
{
for (int j=nn+1;j<i;j++)
{
if (s[j]=='(' && !w[j])
tt++;
if (s[j]==')' && !w[j])
tt--;
if (!tt)
{
if (s[j]=='*')
s[j]='/';
else if (s[j]=='/')
s[j]='*';
}
}
}
}
}
else
{
w[nn]=w[i]=1;
if (s[nn-1]=='-')
for (int j=nn+1;j<i;j++)
{
if (s[j]=='(' && !w[j])
tt++;
if (s[j]==')' && !w[j])
tt--;
if (!tt)
{
if (s[j]=='+')
s[j]='-';
else if (s[j]=='-')
s[j]='+';
}
}
}
}
}
for (int i=1;i<=n;i++)
if (!w[i])
printf("%c",s[i]);
printf("\n");
}
return 0;
}
最新文章
- [MAC] mac系统如何截图
- HDU(3790),最短路二级标准
- thinkjs——空对象判断
- linux包之procps之ps与top
- MFC DLL 资源模块句柄切换[转]
- centos git版本服务器配置
- SQL Server 影响dbcc checkdb的 8 种因素
- 如何joomla修改版权信息
- java.lang.ClassNotFoundException: org.I0Itec.zkclient.IZkStateListener异常解决
- UVA11020 Efficient Solutions
- Unity3d外包公司|UE4外包公司:谷歌首款Daydream VR设备上手
- Emmet.vim 教程
- ATM Mechine (概率DP)
- LINUX内核分析第八周总结:进程的切换和系统的一般执行过程
- openstack neutron中涉及的网络设备
- [C语言] 数据结构-预备知识跨函数使用内存
- Jenkins + GitLab 通过 Webhook 自动触发构建爬坑记录
- 在阿里云上无法使用mailx发送邮件的解决办法,验证可用。
- jquery bxslider幻灯片样式改造
- h5标签