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

10966.c

Partial Judge Header

10966.h

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

10968.c

Partial Judge Header

10968.h

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

Long long time ago, there's a magic kingdom call "NTHU".
Children living there need go to magic schools, "CS", when they're 13 years old.
The magic schools teach spell.

Spell have categories(詞類).

Take English for example, English have ten parts of speech, like "noun", "verb" etc.
And just like English, the spell has four parts of speech, like "Fire", "Air", "Water", and "Earth".

Besides part of speech , the spell also has its own magic grammar.

Most of the words can be classified into those four part of speech, but besides that , there are another thing in magic grammar call "spell". "Spell" means the whole sentence.

Here's a example for the grammar:
Use 1, 2, 3, 4 stands for fire, air, water, earth, and the 0 means spell, -1 means end.

Rule1: 1 1 1 -1
Rule2: 2 -1
Rule3: 3 0 4 -1

Follow the rules above , 3 2 4 -1 (water , air , earth) can be a legal spell, and so does "3 3 1 1 1 4 4 -1".

If chant it incorrectly, sometimes the spell won't work, sometimes it will blow-up.
So as a 1st grade student, the most important thing is to remember which of sententce is effective.

The homework is as following:
"Given some spell, determine whether they are effective spell or not."

Hint1 : In each grammar there is at most one "0", so it is equal to "[somthing] 0 [something]" grammar.

Hint2 : If you get RE in some testcases, you may search for "stack overflow" (堆疊溢位).

 

Input

First line contains two integers N, M, representing # of grammars and # of sentences.

The next N lines give the grammar. Each line contains a grammar.

The next M lines give the sentence. Each line contains a sentence.

 

It is guaranteed that:

• 1 ≤ N, M ≤ 100
• The length of each sentence is ≤ 100.
• There will be at most one "0" in each grammar. (For easy version)
• "0" won't appear in sentences.

 

Output

For each sentence output one line.

If the sentence is legal, output "True"; otherwise output "False".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Niflheimr is a poor student. He can't afford to buy a scientific caculator, but his simple calculator can't type in a mathematical expression.

 

So he decided to create a calculator on his own!
He learned in class that he can evaluate an expression by converting the expression into prefix and create a binary tree accordingly.

Unfortunately, Niflheimr is a careless person. He often types the expression wrong, and if that happens, after he removed the wrong part, he has to rebuild the whole binary tree and calculate everything again. He thinks that rebuilding is too sloooooooooow, so he asks you to help him make it fast.
If you can help him correctly, he will feel happy and give you a big AC.

==========

Note (2018.4.11) : (Thanks J3soon for the reminder!) There won't be any cross-subtree deletion, i.e. the following case won't happen in our testcase:

Note2 (2018.4.12) : In this problem, the expression will never be empty.

Sorry for the incompleteness of the problem description ><"

==========

Hint: If you got a TLE in the last testcase, instead of rebuilding the tree all the time, try to add some extra field in the node inside the binary tree, e.g. size, and utilize them to speed up operations.

For example, you can define your Node inside the binary tree like this:

Input

First line of input is an integer N, indicating the # of deletions.
Second line of input is the expression in prefix. The expression contains only +, -, * and digits. All the number in the expression are between 1 and 9, that is, every number in the expression are DIGITS(個位數).

The following N lines are deletions, the format is "A B", indicating that Niflheimr wants to delete from Ath character to Bth character in the expression. 
Note that the index starts from 1, and the index of the characters in the expression should be re-calculated after each deletion.

 

It is guaranteed that:

• The length of the expression is less than 3*10⁵
• 1 ≤ N ≤ 3*10⁴
• The height of the binary tree is always ≤ 20.
• The range of deletion is always within the expression, i.e. 1 ≤ A, B ≤ length of expression
• The expression is always valid after each operation.

Output

The output consists of N+1 lines.
First line of output is the result of the original expression.
The following N lines are the results after each deletion.
Niflheimr hates big numbers, since it will make calculation more complex. So for every output, please print the result after modulo 10007 (% 10007).

Sample Input  Download

Sample Output  Download

Tags

Discuss