Description

 

Given several Boolean expressions, you need to handle three types of queries:

1. Expand the custom operator @.
2. Convert an infix expression into the preorder traversal of its syntax tree.
3. Expand the custom operator @, build the syntax tree, and evaluate the expression.

The expressions may contain the following characters:

0 1 & | ^ @ ( )

There are no spaces inside an expression.

Grammar

After all custom operators are expanded, the expression will contain only:

0 1 & | ^ ( )

To parse the infix expression with parentheses, use the grammar below.

EXPR   = FACTOR | FACTOR OP EXPR
FACTOR = ID | (EXPR)
ID     = 0 | 1
OP     = one of &, |, ^

All ordinary operators &, |, and ^ are parsed by this grammar. That is, they have the same precedence and are right-associative.

For example, 0|1&0 is parsed as 0|(1&0), so the preorder traversal of its syntax tree is |0&10.

Do not use the usual C operator precedence. Always use the grammar given in this problem.

Custom Operator

The custom operator @ is an infix binary operator.

For each custom operator:

• a is the nearest valid FACTOR immediately on its left.
• b is the nearest valid FACTOR immediately on its right.

The custom operator is defined as:

a @ b = a|b&a

When expanding @, directly replace a@b with a|b&a. Do not add extra parentheses. Only the parentheses that already belong to a or b should remain.

You must repeatedly perform the following operation:

1. Find the leftmost @ in the current expression.
2. Find its left operand a, the nearest FACTOR immediately on its left.
3. Find its right operand b, the nearest FACTOR immediately on its right.
4. Replace a@b with a|b&a.
5. The new expression becomes the current expression.
6. Repeat until there is no @.

Expansion Examples

0@1
=> 0|1&0

(0^1)@0
=> (0^1)|0&(0^1)

0@(1|0)
=> 0|(1|0)&0

For multiple custom operators, always expand the leftmost one first.

Query Types

Each test case contains a query type and an expression.

Type 1: Expand Custom Operators

For query type 1, output the expression after expanding all @. The output should contain no @.

Type 2: Infix To Syntax Tree Preorder

For query type 2, the input expression contains no @. Build the syntax tree using the grammar in this problem, then output the preorder traversal of the syntax tree.

Type 3: Evaluate The Expression

For query type 3, first expand all @. Then build the syntax tree using the grammar in this problem and evaluate the expression.

a & b = bitwise AND
a | b = bitwise OR
a ^ b = bitwise XOR

Since all operands are Boolean values, the answer is always 0 or 1.

Partial Judge

This is a partial judge problem. The judge provides main.c and function.h. The style is similar to the original infix-to-syntax-tree problem.

The judge provides:

BTNode* makeNode(char c);
void printPrefix(BTNode *root);
void freeTree(BTNode *root);

You only need to implement the following functions:

void replace_custom_operator(char expr[], char result[]);
BTNode* EXPR(void);
BTNode* FACTOR(void);
int evaluateTree(BTNode *root);

The global variable expr[] stores the expression currently being parsed. The global variable pos stores the current parsing position. The parser is intended to parse from the beginning of the expression.

Constraints

1 <= N <= 1000
1 <= |expression| <= 2000
After expanding all @, the expression length will not exceed 50000.

• Expressions contain only 0, 1, &, |, ^, @, (, and ).
• Expressions are valid.
• Parentheses are matched.
• Type 2 expressions do not contain @.
• There are 10 test cases.

Scoring

The score is based on the ratio of accepted test cases.

20%  Type 1, custom operator without parentheses.
     The operands of every @ are both IDs.

20%  Type 1, custom operator with FACTOR operands.
     The operands of @ may be parenthesized expressions.

20%  Type 2, syntax tree without parentheses.
     Expressions contain no parentheses and no @.

20%  Type 2, syntax tree with parentheses.
     Expressions may contain parentheses, but no @.

20%  Type 3, evaluation.
     Expressions may contain @ and parentheses.

Sample Explanation

For the first query:

0@1
=> 0|1&0

For the third query, 0|1&0 is parsed as 0|(1&0), so the preorder traversal is |0&10.

For the fifth query:

0@1^1
=> 0|1&0^1

By the grammar, this is parsed as 0|(1&(0^1)), and the value is 1.

 

Extra Note

This note is only for extra background and is not needed for solving the problem. The expansion rule for @ is a simplified rule designed for this problem. It is closer to macro expansion or textual replacement, such as #define, than to how a parser usually handles operators.

Input

The first line contains one integer N, the number of queries.

Each of the next N lines contains one query in the following format:

type expression

The meaning of type is:

• 1: expand custom operators and output the expanded expression.
• 2: output the preorder traversal of the syntax tree.
• 3: expand custom operators, then evaluate the expression.

Output

For each query, output one line.

• For type 1, output the expanded expression.
• For type 2, output the preorder traversal of the syntax tree.
• For type 3, output the evaluated value, either 0 or 1.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14949.c

Partial Judge Header

14949.h

Tags

Discuss