Description

Given an infix Boolean expression with parentheses, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Build a corresponding syntax tree for it.

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

EXPR = FACTOR | EXPR OP FACTOR

FACTOR = ID | (EXPR)

EXPR is the expression, ID is one of ‘A’, ‘B’, ’C’, or ‘D’, and OP is one of ‘&’ or ‘|’.

You will be provided with main.c and function.h. main.c contains the implementation of functions printPrefix and freeTree. function.h contains the definition of tree node and variables. You only need to implement the following three functions in function.c.

BTNode* makeNode(char c)   // create a node without any child

BTNode* EXPR()   // parse an infix expression and generate a syntax tree

BTNode* FACTOR()   // use the parse grammar FACTOR = ID | (EXPR) to deal with parentheses

For OJ submission:

        Step 1. Submit only your function.c into the submission block.(Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

Input

The input contains N infix expressions, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, two operators ‘&’ and ‘|’, and parentheses. All parentheses are matched. 

Output

The output contains N prefix expressions without parentheses, which are preorders of syntax trees.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Given an prefix Boolean expression, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Output its infix presentation with necessary parenthesis.

• Ex: input: ||A&BCD
  output: A|(B&C)|D

Hint : About necessary parenthesis, you can observe the syntax tree which has been constructed, then you will find out the rule. For example, the infix expression of |&|AB&CDA with necessary parenthesis is A|B&(C&D)|A, rather than (A|B)&(C&D)|A .

• Syntax tree of |&|AB&CDA

You will be provided with main.c and function.h, and asked to implement function.c.

For OJ submission:

        Step 1. Submit only your function.c into the submission block.(Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

Input

The first line will have a number N with the number of test cases, followed by N lines of input, each contain the prefix Boolean expression.

Output

There are N lines infix expression with necessary parenthesis.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Give a prefix Boolean expression, which only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’, print its truth table.

For example, if input is "|&AC|AB", then result will be

A B C D output

0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1

Input

The input contains a sequences of prefix expression. It only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’. The length of prefix expression is shorter than 30.

Output

It has 5 variables 'A', 'B', 'C', 'D', and output, each variable is separated by a space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are given a binary tree of N vertices numbered from 1 to N.

There are Q qustions.

Print the every direction if you want to walk from node A to node B. 

P: move to parent

R: move to right child

L: move to left child

Input

The first line contains a single integer N (2≤N≤3000).

Next N lines contain 2 integers, represent the left child and the right child of the i th node. (and 0 means empty)

Next line contains a integer Q (1≤Q≤3000);

The next Q lines contain two integers, A, B.

Output

For each question, output every direction that walks from node A to node B. 

Remember add a new line in the end of each question.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a prefix math expression, which has upper letters as its variables, and four operators ‘+’, ‘-’, ‘*’, and ‘/’. Please print the infix expression and add necessary parentheses if needed.

As we know, the operators ‘*’ and ‘/’ are performed before the operators ‘+’ and ‘-’. Hence, if we want to do the latter operation first, it requires adding parentheses on it.

For example, if we have a prefix expression *+ABC, we would perform A+B first and then perform (A+B)*C. In this case, the infix expression would be (A+B)*C rather than A+B*C.

The situation above is the only situation that requires adding parentheses. If we have a prefix expression *A*BC, it seems that we should perform B*C first and then perform A*(B*C). However, whether performing A*B first or performing B*C first would lead to the same result, due to the associative property (結合律). Thus it is fine to have the infix expression be A*B*C. Since we want to add only necessary parentheses, the expression A*B*C would be the answer rather than A*(B*C).

Hint: You can combine two homework. Build a syntax tree and print the infix expression with the necessary parentheses.

Input

The input contains one line, a prefix expression, which has only upper letters and four operators ‘+’, ‘-’, ‘*’ and ‘/’. The length of the prefix expression is less than 800.

Output

The output is an infix expression, with some parentheses, if necessarily.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

It doesn’t make any sense, but you are now a member of the literature club in a high school.

Currently, the director (社長) of the literature club, Monica, is worried about her homework from computer science class (she takes this course in high school due to 多元學習). As an outstanding student, Monica always finished her homework fast and perfectly. However, she is not quite good at computer science. Monica knows you are a 二類生, thus she asks you for help with the homework during today's club time. The problem is described below:

Given a preorder traversal sequence and a postorder traversal sequence of a binary tree. Then, given an inorder traversal sequence, answer whether these three sequences can construct a valid binary tree.

You won't want to disappoint Monica, so you better hurry.

Hint from Yuri's notebook: 
If you have no idea how to implement, please take it as your reference and thanks Yuri for her help.

By the way, Yuri wants to remind you that not every preorder sequence and inorder sequence could construct a binary tree. See sample input/output as reference.

#include <stdlib.h>
#include <stdio.h>
typedef struct _node {
    int value;
    struct _node *left;
    struct _node *right;
} Node;

// create a new node
Node *create_node(int value);
// verify whether the postorder is match with the input
int verify(Node *root, int *postorder);
// free the memory
void destroy(Node *root);

/*
    Parameter description:
    int *inorder : the inorder traversal sequence of the binary tree.
    int *preorder : the preorder traversal sequence of the binary tree.
    int inorder_start : the starting index of the inorder traversal of the subtree.
    int inroder_end : the ending index of the inorder traversal of the subtree.

    As for the preorder traversal index, you can try declaring a global variable.
*/
// build the tree using recursive
Node *build(int *inorder, int *preorder, int inorder_start, int inorder_end);

Input

The first line of input contains an integer N, indicating the number of nodes on the tree.
The second line contains N distinct numbers, which is the preorder traversal sequence of the binary tree.
The third line contains N distinct numbers, which is the postorder traversal sequence of the binary tree.
Then, the fourth line contains an integer Q, indicating the number of queries.
The following Q lines each contain N distinct numbers, which is the inorder traversal sequence of the binary tree.

Constraints:

1 ≤ N ≤ 2 x 10⁵
1 ≤ Q ≤ 20
For all x being the number on the binary tree, 0 ≤ x ≤ N-1.

Output

Output contains Q lines. For each query, print ‘Yes’ if the three sequences could construct a valid binary tree, otherwise print ‘No’.

Sample Input  Download

Sample Output  Download

Tags

Discuss