Detailed explanation of expression (csp-j 2021 expr) topic

First move the topic from Luogu

Title Description

Small C Keen on learning mathematical logic . one day , He found a special logical expression . In this logical expression , All operands are variables , And their values can only be  0  or  1, The operation is carried out from left to right . If there are parentheses in the expression , Evaluate the value of the subexpression in parentheses first . Special , This expression has and only has the following operations ：

1. And operation ：a & b. If and only if  a  and  b  The values are  1  when , The value of this expression is  1. In other cases, the value of the expression is  0.
2. Or operations ：a | b. If and only if  a  and  b  The values are  0  when , The value of this expression is  0. In other cases, the value of the expression is  1.
3. Reverse operation ：!a. If and only if  a  The value of is  0  when , The value of this expression is  1. In other cases, the value of the expression is  0.

Small C Want to know , Given a logical expression and the initial value of each operand , When you reverse the value of an operand , What is the value of the original expression .

To simplify the processing of expressions , We have the following agreement ：

The expression will take Postfix expression Input by .

The definition of suffix expression is as follows ：

1. If  E  Is an operand , be  E  The suffix expression is itself .
2. If  E  yes E1​ op E2​  Expression of form , among op  Is any binary operator , And the priority is no higher than E1​ 、E2​  Operators outside brackets , be  E  The suffix of is E1 E2 op, among E1  E2  Respectively E1​、E2​  Postfix of .
3. If  E  yes E1​  Expression of form , be E1​  The suffix of  E  Postfix of .

At the same time, for the convenience of , Entering ：

1. And operators （&）、 Or operator （|）、 Negation operator （！） About There is a space , but There is no space at the end of the expression .
2. Operands consist of lowercase letters  x  Spliced with a positive integer , A positive integer represents the subscript of this variable . for example ：x10, Indicates that the subscript is  10 The variable of x10​. Data assurance Each variable appears exactly once in the expression .

Input format

The first line contains a string  s, Represents the expression described above .
The second line contains a positive integer  n, Represents the number of variables in the expression . The subscript of the variable in the expression is  1,2,⋯,n.
The third line contains  n  It's an integer , The first  i  An integer represents a variable xi​  Initial value of .
The fourth line contains a positive integer  q, Number of questions .
Next  q  That's ok , One positive integer per line , Subscript indicating the variable to be negated . Be careful , The revision of each inquiry is temporary , That is, the modification in the previous inquiry will not affect the subsequent inquiry .
The data ensures that the input expression is legal . The initial value of the variable is  0  or  1.

Output format

Output a total of  q  That's ok , Each row of a  0  or  1, Represents the value of the expression under the query .

I/o sample

Input #1 Copy

x1 x2 & x3 |
3
1 0 1
3
1
2
3

Output #1 Copy

1
1
0


This problem is really a little difficult , I passed the examination directly , Looking back, I found that it was still skillful

Answer key

For data storage , I'll take the form

First, define a structure ：

struct node{
    char op;
    int value;
    int dp[2];
    vector<node*>son;
    node(){
        dp[0]=0;
        dp[1]=0;
        value=0;
        op='F';                //F It means that there is no , Leaf nodes can be marked 
        vector<node*>son();   // initialization , It's ok if you don't add it 
    }
};

dp Arrays are explained below ,value Store the value of the node subtree , One vector Array represents its child nodes , Easy to find , The number of child nodes depends on the symbol of the node , by ！ There is only one ; But for & or | Time is two . Leaf nodes are stored values , There is no sign , Instead, there is no value in the initial state of the leaf node , But there are symbols .

You can use stack Container to handle suffix expressions

Build a date Array to record the subscript x Of node type , And stack Connect

We define various data in the form of pointers , Because we can allocate memory dynamically , Reduce the consumption . But more importantly , In this way, we can establish various data structures and establish connections , While a certain value changes , Other types of their corresponding pointers also change .

There are two ways to deal with the core algorithm of this problem

The first one is

        Is the value to be changed every time you enter , Then traverse the whole tree , Give an answer . But obviously, when there are many queries , This method will definitely time out .

The second kind

        Just before entering the value to be changed , Let's type the watch ：

How to make a watch , First of all, we need to Dfs Traverse the entire tree from bottom to top , Find the default value of each node .

Let's define a function later Dfs_dp Traverse the entire tree from top to bottom , Find out the dp value .

dp[] Array means when the value of this node is x, The operation result of the whole tree is dp[x],dp Obviously, there are only two states , So we define it as int dp[2] That's enough .

From top to bottom , For the root node , Obviously when it's dp Value is the value of the whole tree .

For each child node , Let's consider two scenarios ：

1. The symbol corresponding to the parent node is ！ when , its dp The value is the opposite of its parent node dp value .

2. The symbol corresponding to the parent node is & or | when , First, find out when its value is x when , The result of corresponding symbolic operation with another child node of its parent node z, Then corresponding to its corresponding parent node dp[z] Value

The reason why this is faster is that we can get the value of all cases after traversing the tree , Compared with scheme 1 , We don't have to traverse many times .

Last , When inputting each node to be changed , We output the changed results dp value .

AC code is here

#include<cstdio>
#include<stack>
#include<vector>
#include<cstring>
using namespace std;
struct node{
    char op;
    int value;
    int dp[2];
    vector<node*>son;
    node(){
        dp[0]=0;
        dp[1]=0;
        value=0;
        op='F';
        vector<node*>son();
    }
};
stack<node*>fuel;                    
node* date[100000];
char str[100000];
int tot=0,quenum,que;
using namespace std;
int Dfs_solve(node* x){
    if(x->op=='F'){
        return 0;
    }
    for(int i=0;i<x->son.size();i++){
        Dfs_solve(x->son[i]);
    }
    if(x->op=='!'){
        x->value=(!x->son[0]->value);
    }
    else if(x->op=='&'){
        x->value=(x->son[0]->value & x->son[1]->value); 
    }
    else if(x->op=='|'){
        x->value=(x->son[0]->value | x->son[1]->value); 
    }
    return 0;
}
void Dfs_dp(node* x,node* father){
    if(father==NULL){
        x->dp[0]=0;
        x->dp[1]=1;
    }
    else{
        if(father->op=='!'){
            x->dp[0]=father->dp[1];
            x->dp[1]=father->dp[0]; 
        }
        else if(father->op=='&' || father->op=='|'){
            node *other;
            if(father->son[0]==x){
                other=father->son[1];
            }
            else{
                other=father->son[0];
            }
            
            if(father->op=='&'){
                x->dp[0]=father->dp[0];
                x->dp[1]=father->dp[other->value]; 
            }
            else{
                x->dp[1]=father->dp[1];
                x->dp[0]=father->dp[other->value];
            }
        }
    }
    for(int i=0;i<x->son.size();i++){
        Dfs_dp(x->son[i],x);
    }
    return;
}
int main(){
    while(scanf("%s",str)){
        if(str[0]=='x'){
            int num=0;
            for(int i=1;i<strlen(str);i++){
                num=(num<<3)+(num<<1)+(str[i]^48);
            }
            date[num]=new node;
            fuel.push(date[num]);
        }
        else if(str[0]=='&' || str[0]=='|'){
            node* a;
            node* b;
            node* c=new node;
            a=fuel.top();
            fuel.pop();
            b=fuel.top();
            fuel.pop();
            c->op=str[0];
            c->son.push_back(a);
            c->son.push_back(b);
            fuel.push(c);
        }
        else if(str[0]=='!'){
            node* a;
            node* b=new node;
            a=fuel.top();
            fuel.pop();
            b->son.push_back(a);
            b->op='!';
            fuel.push(b);
        }
        else{
            for(int i=0;i<strlen(str);i++){
                tot=(tot<<3)+(tot<<1)+(str[i]^48);
            }
            for(int i=1;i<=tot;i++){
                scanf("%d",&date[i]->value);
            }
            break;
        }
    }
    node* root=fuel.top();
    Dfs_solve(root);
    Dfs_dp(root,NULL);
    scanf("%d",&quenum);
    for(int i=0;i<quenum;i++){
        scanf("%d",&que);
        printf("%d\n",date[que]->dp[!date[que]->value]);
    }
    return 0;
}

END~~~

Writing is not easy to , If you don't understand anything, please comment , I will reply immediately .

Thank you for your support