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

Linked list

typedef struct _Node {
    int data;
    struct _Node *next;
} Node;

 

/* print the content of the linked list.*/

void printList(Node *head)
{
    Node *temp;
    for(temp=head; temp!=NULL; temp=temp->next) {
        printf("%d ", temp->data);
    }
}

/*Insert a node after the node pointed by nd.

Return 1 if insertion succeeds.
Otherwise, return 0.*/

int insertNode(Node* nd, int data)
{
    if (nd != NULL) {

        Node* temp = (Node*)malloc(sizeof(Node));
        temp->data = data;
        temp->next = nd->next;
        nd->next = temp;
        return 1;
    }
    return 0;
}

 

/*Delete a node after the node pointed by nd.

Return 1 if insertion succeeds. 

Otherwise, return 0.*/

int deleteNode(Node* nd)
{
    if (nd != NULL) {
        Node* temp = nd->next;
        if (temp != NULL) {
            nd -> next = temp->next;
            free(temp);
            return 1;
        }
    }
    return 0;
}

 

Binary tree

typedef struct _node {
     int data;
     struct _node *left, *right;
} BTNode;

 

Tree traversal

• Pre-order: visit root, left subtree, and right subtree
• In-order: visit left subtree, root, and right subtree
• Post-order: visit left subtree, right subtree, and root

 

Expression order

• Prefix:  operator, left operand,and right operand
• Infix:  left operand, operator, and right operand
• Postfix: left operand, right operand, and operator

 

Syntax tree

The internal nodes are operators, and the leaves are operands.

Recursive evaluation of prefix expression

/*It is a pseudo code */

int evalBoolExpr(){

char c = getchar();

If c is an operator

   op1 = evalBoolExpr();

   op2 = evalBoolExpr();

   return op1 c op2;

Else if c is a variable

   return the value of c;

}

Grammar of infix expression with parenthesis

• EXPR = FACTOR| EXPR OP FACTOR
• FACTROR = ID | (EXPR)

 

/*Suppose expr[] is an array of expression and pos is the current position, which initially is strlen(expr)-1. */

/*-------------------------------------*/

BTNode* makeNode(char c)
{
    int i;
    BTNode *node = (BTNode*)malloc(sizeof(BTNode));
    set node->data
    node->left = NULL;
    node->right = NULL;
    return node;
}

 

/*-------------------------------------*/

BTNode* FACTOR()
{
    char c;
    BTNode *node = NULL;
    if (pos>=0) {
        c = expr[pos--];
        if (c is an ID) {
            node = makeNode(c);
        } else if (c==‘)’) {
            node = EXPR();
            if(expr[pos--]!= '(') {
                printf("Error!\n");
                freeTree(node);
            }
        }
    }
    return node;
}

 

/*-------------------------------------*/

BTNode* EXPR()
{

    char c;

    BTNode *node = NULL, *right=NULL;

    if (pos>=0) {

        node = right = FACTOR();

        if (pos>0) {

            c = expr[pos];

            if (c is an operator) {

                node = makeNode(c);

                node->right = right;

                pos--;

                node->left = EXPR();

            }

        }

    }

    return node;

}

Input

Output

Sample Input  Download

Sample Output  Download

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