P8815-CSP-J-2022-3-LogicExpression邏輯表達(dá)式
#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;
}