| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10966 | Infix to syntax tree |
|
| 10972 | Remove unnecessary parentheses |
|
| 10980 | practice Josephus |
|
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.cPartial Judge Header
10966.hTags
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
The Josephus problem is notoriously known. For those who are not familiar with the problem, among n people numbered 1, 2, . . . , n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give the message about the incident.
Given a group of n men arranged in a circle under the edict that every m man will be executed going around the circle until only one remains. Find the position in which you should stand in order to be the last survivor.
Input
Each line with 2 integers, n, m. n is the number of people. m is the number that every m person is executed. Input terminated by EOF.
Output
The output will consist in separate lines containing the position of the person which life will be saved. Each line should be ended with a newline character '\n'.