Description

In this problem, you have to build a Boolean expression with right associativity into a syntax tree.

The associativity of an operator is a property that determines how operators of the same precedence are grouped in the absence of parentheses.

EX.

Consider the expression: A&B|C

With left associativity, the expression is interpreted as:

        (A&B)|C

With right associativity, the expression is interpreted as:

        A&(B|C)

 

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 following right associativity.

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

EXPR = FACTOR | FACTOR OP EXPR

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

11389.c

Partial Judge Header

11389.h

Tags

Discuss

Description

In the programming academy, students enjoy learning from each other, where each person can become the “seafu” of others. Over time, this has led to a unique hierarchical system similar to a tree structure.

Within the academy, every student has exactly one "direct seafu,” except for the "Master FrankLee”, who sits atop the academy's hierarchy. He is the only one without a "direct seafu”, and he is the “seafu” of every students.

There are N students in the academy, each person has a uniuqe id number from 1 ~ N. There is a unique custom in the academy, seafu's id must be smaller than disciples' id. So "FrankLee" is always id number 1.

Now give you every student's direct seafu's id (except “FrankLee”), please answer the following questions.

Note: a student can be more than 1 students' "direct seafu", but can only have 1 "direct seafu".

 

Disciples Query:

Given an id number X. Output the number of disciples of student X.

A person is disciple of student X if student X is this person’s seafu. So Master FrankLee has N-1 disciples.

 

Seafu Test:

Given 2 id numbers A, B. (A≠B)

Check if student A is B’s seafu or student B is A’s seafu or neither.

if student A is B’s seafu, output "1".

if student B is A’s seafu, output "0".

if neither output "-1"

 

Note: A person x is person y’s seafu if person x is y’s direct seafu or y’s direct seafu’s direct seafu or y’s direct seafu’s direct seafu’s direct seafu, and so on…

Input

• The first line contains an integer N (1 ≤ N ≤ 1000), representing the number of people (excluding FrankLee) in the academy.
• The second line contains N - 1 space-separated integers, representing p_2, p₃, ..., p_N, which p_i means the direct seafu id of student i.
• Student id number 1 is always master FrankLee. And it is guarantee that p_i < i.
• The following line contains an integer Q (1 ≤ Q ≤ 1000), representing the number of queries.
• Each of the next Q lines contains a query "1 X"(disiples query) or "2 A B"(seafu test).

Constraints

• Testcase 1: There is only seafu test query, and the answer is to the query is either 0 or 1.
• Testcase 2: There is only seafu test query.
• Testcase 3~4: There is only disiples query. 
• Testcase 5~6: Satisfy no additional constraints.

 

Output

• Output Q lines, each lines contain the answer tod  each query.

Sample Input  Download

Sample Output  Download

Tags

Discuss