Question

Code to be written in C++:

Initially, you will be given symbols printed in a preorder traversal of a boolean expression tree. The internal nodes of the tree will contain one of the following operators: & (and), | (or), ^ (exclusive-or), or ! (not). The nodes containing the first three operators will have two children, while the nodes containing the ! operator will contain only a left child. The leaves of the tree will contain an operand - either f for false or t for true.

You will then be asked to perform a series of queries, in which, you evaluate the tree, or modification operations in which you change either an operator or an operand.

Input Format

The input begins with two space separated integers, n and q, on a line by itself.  n indicates the number of nodes in the tree, while q gives the number of queries and modification operations.

The next n lines will contain the values from the pre-order traversal of the tree. These will be chosen from the following set of values: {&, |, ^, !, t, f}.

The next q lines will be in one of the following formats:

mod [path] [new_value]

or

eval

where [path] is a string comprised of the symbols 'l' or 'r', and [new_value] is chosen from the following set of values: {&, |, ^, t, f}.

Constraints

1 ≤ n ≤ 10⁴

1 ≤ q ≤ 10³

Output Format

For each mod line, you will not output anything, however, you should change the state of the tree, by following the path indicated in the [path] string, and changing the value stored at the node at the end of the path to the value in [new_value]. For example, if the command where mod llr t, you would start at the root, go to the left child (which we will call n₁), go to n₁'s left child (which we will call n₂), and then go to n₂'s right child (which we will call n₃). You will then change the value stored at n₃ to true.

For each eval line, you should output, on a line by itself, the result obtained when evaluating the current state of the tree, either t or f.

Notes:

• You should not output anything for the mod lines.

• There is guaranteed to be a node located at the end of the path specified in the mod commands.

• After each mod command, you are guaranteed that the tree will remain a valid boolean expression tree. For example, you will never be asked to change a node containing the ! operator, you will never be asked to change the value of a node that contains an operand to an operator, nor will you be asked to change the value of a node that contains an operator to an operand.

Sample Input

6 4
^
!
t
|
f
t
mod ll f
eval
mod r &
eval

Sample Output

f
t

Explanation

Initially the tree looks like the following:

     ^
   /   \
  !     |
 /     / \
t     f   t

After the command mod ll f, the new tree looks like:

     ^
   /   \
  !     |
 /     / \
f     f   t

This corresponds to the boolean expression !f ^ (f | t) = t ^ t = f

Therefore at the eval command we will output f.

After the command mod r &, the new tree looks like:

     ^
   /   \
  !     &
 /     / \
f     f   t

This corresponds to the boolean expression !f ^ (f & t) = t ^ f = t

Therefore at the eval command we will output t.

To get credit you must submit a solution that deserializes the tree using a binary tree node class, and uses this tree to solve the problem.

The nodes must have the following methods, used when appropriate in the solution:

evaluate() that returns true if the subtree rooted at the node evaluates to true, and false otherwise. This method must be implemented recursively.

modify(String path, char newValue) that modifies the subtree by following the path in the first argument to set the node at the end of the path based on newValue. This method must also be implemented recursively.

Here is the code we discussed in class for this assignment:

Code to be written in C++:

class binary_tree_node
{
public:
    typedef char value_type;

    binary_tree_node();

    // Rest of code from lecture
    ...

    bool evaluate();
        
    void modify(string path, char symbol);
   
private:
    value_type data_field;
    binary_tree_node* left_field;
    binary_tree_node* right_field;
}


binary_tree_node::binary_tree_node() {
    cin >> data_field;
    left_field = NULL;
    right_field = NULL;
        
    if (data_field == '^' || data_field == '|' || data_field == '&') {
        left_field = new binary_tree_node();
        right_field = new binary_tree_node();           
    }
    else if (data_field == '!') {
        left_field = new binary_tree_node();            
    }
}


bool binary_tree_node::evaluate() {
    if (data_field == 't') return true;
    if (data_field == 'f') return false;
        
    if (data_field == '!') 
        return !left_field->evaluate();
    if (data_field == '|')
        return left_field->evaluate() || right_field->evaluate();
    // TODO: Finish this!!!
}
        
void binary_tree_node::modify(string path, char symbol){
    if (path == "") {
        data_field = symbol;
        return;
    }
    //TODO: recursive cases
}

int main() {
    int n, m;
    cin >> n >> m;
    binary_tree_node* root = new binary_tree_node();

    for (int i = 0; i < m; i++) {
        string command, path;
        char symbol;
        cin >> command;
        if (command == "eval") {
            // Evaluate the tree and output true or false
        }
        else { // command == "mod"
            cin >> path >> symbol;
            // Change the tree 
        }
    }
}

Answer 1

*YOUR GIVEN FUNCTIONS HAVE BEEN MODIFIED AND HIGHLIGHTED IN THE CODE WRITTEN BELOW. PLEASE RECTIFY THE SYNTAX ERROR IF ANY*


class binary_tree_node
{
public:
    typedef char value_type;

    binary_tree_node();

    // Rest of code from lecture
    ...

    bool evaluate();
        
    void modify(string path, char symbol);
   
private:
    value_type data_field;
    binary_tree_node* left_field;
    binary_tree_node* right_field;
}


binary_tree_node::binary_tree_node() {
    cin >> data_field;
    left_field = NULL;
    right_field = NULL;
        
    if (data_field == '^' || data_field == '|' || data_field == '&') {
        left_field = new binary_tree_node();
        right_field = new binary_tree_node();           
    }
    else if (data_field == '!') {
        left_field = new binary_tree_node();            
    }
}


bool binary_tree_node::evaluate() {
    if (data_field == 't') return true;
    if (data_field == 'f') return false;
        
    if (data_field == '!') 
        return !left_field->evaluate();
    if (data_field == '|')
        return left_field->evaluate() || right_field->evaluate();
    if (data_field == '&')
        return left_field->evaluate() && right_field->evaluate();
    if (data_field == '^')
        return left_field->evaluate() ^ right_field->evaluate();


}
        
void binary_tree_node::modify(string path, char symbol){
    if (path == "") {
        data_field = symbol;
        return;
    }
    char cur=path[0]
    if(cur=='l')
    {
        left_field->modify(path.substr(1),symbol);
    }
    else
    {
        right_field->modify(path.substr(1),symbol);

    }
    //TODO: recursive cases
}

int main() {
    int n, m;
    cin >> n >> m;
    binary_tree_node* root = new binary_tree_node();

    for (int i = 0; i < m; i++) {
        string command, path;
        char symbol;
        cin >> command;
        if (command == "eval") {
            bool ans=root->evaluate();
            if(ans)
            {
                cout<<"t";
            }
            else
            {
                cout<<"f";
            }
            cout<<endl;

            // Evaluate the tree and output true or false
        }
        else { // command == "mod"
            cin >> path >> symbol;
            root->modify(path,symbol);
            // Change the tree 
        }
    }
}