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 ‘|’. You have to use this prefix expression to construct a syntax tree.

 

 

• 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.

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" void printInfix(Node *root){ if (root != NULL) { printInfix(root->left); printf("%c", root->data); if((root->data == '|' || root->data == '&') && (root->right->left != NULL && root->right->right != NULL)) printf("("); printInfix(root->right); if((root->data == '|' || root->data == '&') && (root->right->left != NULL && root->right->right != NULL)) printf(")"); } } void freeTree(Node *root) { if (root!=NULL) { freeTree(root->left); freeTree(root->right); free(root); } } int main(void) { int n; scanf("%d", &n);// the number of test cases while(n>0) { getchar(); Node *root=NULL; constructTree(&root);// you have to implement this function printInfix(root);//output function printf("\n"); freeTree(root); n--; } return 0; }

function.h

#include <stdlib.h> typedef struct treeNode { char data; struct treeNode *left; struct treeNode *right; } Node; void constructTree(Node** head); void printInfix(Node *root); void freeTree(Node *root);

 

 

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

10984.c

Partial Judge Header

10984.h

Tags

Discuss

Description

The problem will ask you to create a binary search tree, and there will be 4 kinds of commands to complete

1. P : please print out the binary search tree in in-order form in th line ,if the tree is empty, please print "NULL"(There is an whitespace between each number, also after the last number,no space after NULL)

2. GetMax : print out the maximum height of the binary search tree( There need no space after output number)

3. SumLevel (input) : print out  the sum value of the nodes at the input level in the line, if the input level is bigger than the maximum height, please print out "0". ( There need no space after output number)

4. AverLevel (input) : print out the average value of the nodes at the input level in the line, please show only 3 digits after decimal point of the average numbers of level, if the input level is bigger than the maximum height, please print out "0". (You can simply use %.3f to display in such way) ( There need no space after output number)

the root level will represent as 1( for SumLevel & AverLevel, if the input level is 0, please print "0")

Input

The first line contains an integer N , which indicates the number of nodes of the binary search tree.

The second line is the data for create binary search tree

The third line contains an integer M , which indicates the number of commands.

Following line will be the input instruction

If there is same input value, please ignore the second one.

Output

There need to print newline in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss