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

Add Tag

Discuss