Description

The input is a postfix Boolean expression, which has at most four variables ‘A’, ’B’, ‘C’, and ‘D’, and two operators ‘&’ and ‘|’. The task is to use this postfix expression to construct a syntax tree, and print the corresponding infix expression. For example, if the input is 

AB|CD&&A|

then its syntax tree should be

 

The corresponding infix expression with parenthesis is 

   A|B&(C&D)|A

 

You need to implement the function "constructTree()" based on the two files "main.c" and "function.h" given below.

For OJ submission:

        You only need to copy and paste the code of your "function.c" into the submission block. Make sure you choose C compiler.

 

HINT : 

Please read partial judge code first. We help you dealing with input ：）

Input

The first line is a number N indicating the number of test cases. The next N lines contain the prefix Boolean expressions.

Output

The output contains N lines of the infix expressions with necessary parentheses.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11891.c

Partial Judge Header

11891.h

Tags

Discuss

Description

Given a binary tree, find the sum of values at all leaf nodes.

Defintion of leaf nodes: nodes without any child nodes.

 

e.g.

        1
      /   \
     2     3
    / \     / \
   4   5 6   7
          \
           8

 

The answer is 4 + 8 + 6 + 7 = 25

Input

The input has three lines.

The first line contains an integer N indicating the number of nodes of the binary tree.

The second line is the inorder traversal of the binary tree.

The third line is the preorder traversal of the binary tree.

Note that there are no duplicated integers in the binary tree.

Output

Print the sum of values at all leaf nodes.

There are '\n' in the end of input

Sample Input  Download

Sample Output  Download

Partial Judge Code

11892.c

Partial Judge Header

11892.h

Tags

Discuss

Description

The problem is to parse a series of commands to move the books that lie on the table. Initially there are n books lying on the table with book b_i adjacent to book b_i+1 for all 0 <= i < n-1, as shown in the diagram below:

Book N-1

......

Book 2

Book 1

Book 0

Table

 

The valid commands and limited for moving books are:

Illegal commands:

• A = B
• A or B is not in the range (e.g. You cannot move or remove any book that does not exist)

All illegal commands should be ignored and should have no affect on the configuration of books.

Valid commands:

• move A on B

Puts book A on book B.                                                                       

As below:

0 1 2 3 4

>> move 1 on 3

0 2 3 1 4

• move A under B

Puts book A under of book B.

As below:

0 1 2 3 4

>> move 1 under 3

0 2 1 3 4

• remove A

Remove book A from the list.

As below:

0 1 2 3 4

>> remove 1

0 2 3 4

• reverse

Reverse the entire list upside down.

As below:

0 1 2 3 4

>> reverse

4 3 2 1 0

• switch A

Using A as pivot, exchange the stack above A (containing A) and the stack below A (not containing A).

As below:

0 1 2 3 4

>> switch 3

3 4 0 1 2 

• exit

Finish moving the books, print the final status.

 

Remind you that solving this problem is relatively time-consuming.

However, 2 out of 3 testcases in this problem only require you to implement the original 4 commands (excluding reverse and switch A).

Input

The input begins with an integer n on a line by itself representing the number of books in the book world. You may assume that 0 < n <= 10000.

The number of books is followed by a sequence of book commands, one command per line. Your program should process all commands until the exit command is encountered.

You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.

Output

Your output should contains one line of sequence which represents the order of books from the bottom to the top. 

Each number is followed by a single space. And you are asked to add a new line character at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss