P8815-CSP-J-2022-3-LogicExpression逻辑表达式
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXV=1e6;
struct node{
char v;
int l,r;
};
vector<node> g(MAXV);
int build_tree(string sl){
int last=1;
stack<int> st;
for(int i=0;i<sl.size();i++){
if(sl[i]=='0'||sl[i]=='1'){
g[last].v=sl[i];
st.push(last);
last++;
}
if(sl[i]=='&'||sl[i]=='|'){
int o2=st.top();
st.pop();
int o1=st.top();
st.pop();
g[last].l=o1;
g[last].r=o2;
g[last].v=sl[i];
st.push(last);
last++;
}
}
return st.top();
}
int dfs(int root, int& a, int& b){
if(g[root].l==0&&g[root].r==0){//leaf
return g[root].v-'0';
}
int left=dfs(g[root].l,a,b);
int ret=-1;
if(g[root].v=='&'){
if(left==0){
a++;
ret=0;
}else{
ret=dfs(g[root].r,a,b);
}
}else{
if(g[root].v=='|'){
if(left==1){
b++;
ret=1;
}else{
ret=dfs(g[root].r,a,b);
}
}
}
return ret;
}
string m2l(string s){
string res;
stack<char> st;
for(int i=0;i<s.size();i++){
char c=s[i];
switch(c){
case '0':
case '1':
res+=c;
break;
case '(':
st.push(c);
break;
case ')':
while(st.top()!='('){
res+=st.top();
st.pop();
}
st.pop();
break;
case '&':
while(st.size()>0&&st.top()!='|'&&st.top()!='('){
res+=st.top();
st.pop();
}
st.push('&');
break;
case '|':
while(st.size()>0&&st.top()!='('){
res+=st.top();
st.pop();
}
st.push('|');
break;
default:
cout<<"error1\n";
}
}
while(st.size()>0){
res+=st.top();
st.pop();
}
return res;
}
int main(){
string s,sl;
cin>>s;
sl=m2l(s);
int root=build_tree(sl);
int a=0,b=0;
cout<<dfs(root,a,b)<<endl;
cout<<a<<" "<<b<<endl;
return 0;
}
