比赛 |
CSP2022普及组 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
逻辑表达式 |
最终得分 |
100 |
用户昵称 |
CCF_NOI |
运行时间 |
0.105 s |
代码语言 |
C++ |
内存使用 |
9.55 MiB |
提交时间 |
2022-10-29 16:39:39 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=1000000+5;
bool opt[130][130];
int n,len=0;
char s[N],ex[N];
int st[N],tp=0;
int pos[N],w[N];
void init(){
opt['&']['&']=1;opt['&']['|']=0;opt['&']['(']=0;
opt['|']['&']=1;opt['|']['|']=1;opt['|']['(']=0;
return ;
}
int main(){
freopen ("csp2022pj_expr.in","r",stdin);
freopen ("csp2022pj_expr.out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
init();
for (int i=1;i<=n;i++){
if (isdigit(s[i]))ex[++len]=s[i];
else{
if (s[i]=='(')st[++tp]=s[i];
else if (s[i]==')'){
while(tp>=0&&st[tp]!='('){
ex[++len]=st[tp--];
}
tp--;
}
else{
while(tp>=0&&opt[s[i]][st[tp]]){
ex[++len]=st[tp--];
}
st[++tp]=s[i];
}
}
}
while(tp>=0){
ex[++len]=st[tp--];
}
for (int i=1;i<=len;i++){
if (isdigit(ex[i]))st[++tp]=i;
else{
pos[st[tp-1]]=i;
tp-=2;
st[++tp]=i;
}
}
tp=0;
int ans1=0,ans2=0;
for (int i=1;i<=len;i++){
if (isdigit(ex[i]))st[++tp]=i,w[i]=ex[i]-'0';
else{
int now=0;
if (ex[i]=='&')now=w[st[tp]]&w[st[tp-1]];
else now=w[st[tp]]|w[st[tp-1]];
tp-=2;
st[++tp]=i;w[i]=now;
}
while(true){
if (w[i]==1&&ex[pos[i]]=='|'){
ans2++;i=pos[i];w[i]=1;
}
else if (w[i]==0&&ex[pos[i]]=='&'){
ans1++;i=pos[i];w[i]=0;
}
else break;
}
}
printf("%d\n%d %d\n",w[len],ans1,ans2);
return 0;
}