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

Given an infix Boolean expression with parentheses, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. Please remove unnecessary parentheses and print the infix expression. Existence of unnecessary parentheses doesn’t affect the result of expression. For example,

(A&B)|(C&D) → A&B|(C&D)

(((A|B))) → A|B

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

For OJ submission:

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

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

Input

The input is an infix expression, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, two operators ‘&’ and ‘|’, and parentheses. The length of the infix expression is less than 256.

Output

The output is an infix expression without unnecessary parentheses.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Niflheimr discovers an interesting fact: trees grow upward in real world, but trees grow downward in CS world.
He decides to study the trees in CS world, so he choose the simplest one for his study: binary tree. Before study begins, he needs to construct a binary tree first.

Given a in-order traversal sequence and a pre-order traversal sequence of a binary tree, construct the binary tree and print the post-order traversal sequence of that binary tree.

Hint:

      1. If you have no idea how to implement, please take it as your reference.

function.h

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

Node *create_node(int value);
void postorder(Node *root);
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, try declaring a static variable inside this function.
*/
Node *build(int *inorder, int *preorder, int inorder_start, int inorder_end);

      2. If you get a TLE in the last testcase, try to think over the property underlined in "Input" section.

​

Input

 The first line of input contains a integer N, indicating the number of nodes on the tree.
The second line contains N distinct numbers, which is the in-order traversal sequence of the binary tree.
The third line contains N distinct numbers, which is the pre-order traversal sequence of the binary tree.

It is guaranteed that:

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

Output

Print out the post-order traversal sequence of the binary tree.
There is a white space after each number (including the last one). For example, [0 1 2 3 ].
Remember to print a '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

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

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 LJH”, 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 "LJH" is always id number 1.

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

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

Distance Calculation:

Calculate the distance between the "Master LJH" and every other person in the academy. The distance between a person and master "LJH" is the number k which a person's k level seafu is "LJH".

Level Seafu Query:

Respond to Q queries, each of the form (A, B), where A represents a person and B represents a level. For each query, determine person A's B level seafu. If such a seafu does not exist, print -1.

What is K level seafu? direct seafu is 1 level seafu, direct seafu's direct seafu is 2 level seafu, and so on...

Input

• The first line contains an integer N (1 ≤ N ≤ 1000), representing the number of people (excluding LJH) 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 LJH. 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 two integers A and B, representing a query.

Output

• The first line outputs N - 1 integers, representing the distance between person 2 to N and master “LJH”. (No space in the end)
• In the next Q lines, output the answer to each query in sequence.

Sample Input  Download

Sample Output  Download

Tags

Discuss