Description

This problem will give you a sequence of positive integers.  Use this sequence to create a linked list to store those integers.  Next, the problem will give you another sequence of positive integers, p0, p1,…pk-1.  Delete the nodes that the data is equal to one of p0, p1, …pk-1 of the linked list. If the node is not existing,do nothing.  And show the final results.

 

The framework of the program is provided.

1. Create a linked list from the input  (createList)
2. while there are still some data pi
3. read in pi
4. delete node that data is equal to pi  (deleteNode)
5. print the remaining list (printList)
6. free the list (freeList)

You will be provided with main.c and function.h. main.c contains the implementation of function printList, and freeList, and function.h contains the definition of node and the interface of createList() and deleteNode(&head, pi).  You only need to implement createList() and deleteNode(&head, pi) in function.c, in which head is the head of the linked list, and pi is the data of the node to be deleted.

 

For OJ submission, you only need to submit your createList and deleteNode implementation to the submission block. (Choose c compiler) 

 

Below is the partial code for main.c

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" void printList(Node *head){ Node *temp; for(temp = head; temp!=NULL; temp=temp->next) { printf("%d ", temp->data); } } void freeList(Node *head){ Node *temp; for(temp=head; temp!=NULL; temp=head){ head = head->next; free(temp); } } int main() { Node *head; int data; head = createList(); while(1){ scanf("%d", &data); if(data>-1){ deleteNode(&head,data); }else break; } printList(head); freeList(head); return 0; }

 

function.h

#include <stdlib.h> #include <stdio.h> typedef struct _Node { int data; struct _Node *next; } Node; void deleteNode(Node ** nd, int data); Node* createList();

Input

The input contains 2 sequences of positive integers.  The first sequence is to create a linked list of integers, and the second sequence is the nodes to be deleted.  Each sequence is ended by -1. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10981.c

Partial Judge Header

10981.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 ‘|’. Build a corresponding syntax tree for it and print it's truth table.

For example, if input is "(A&C)|(A|B)", then result will be

A B C D output

0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1

 

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 four 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

void printResult(BTNode *root)    // print the truth table

 

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 <string.h> #include <stdlib.h> #include "function.h" int main() { sym[0]='A'; sym[1]='B'; sym[2]='C'; sym[3]='D'; sym[4]='&'; sym[5]='|'; while (scanf("%s", expr)!=EOF) { pos = strlen(expr) - 1; BTNode *root = EXPR(); printResult(root); printf("\n"); freeTree(root); } return 0; } /* clean a tree.*/ void freeTree(BTNode *root) { if (root!=NULL) { freeTree(root->left); freeTree(root->right); free(root); } }

function.h

#include <stdio.h> #include <stdlib.h> #define MAXEXPR 256 #define NUMSYM 6 char expr[MAXEXPR]; // string to store the input expression. int pos; // current position of parsing, from end to start typedef enum {ID_A, ID_B, ID_C, ID_D, OP_AND, OP_OR} TokenSet; char sym[NUMSYM]; typedef struct _Node { TokenSet data; struct _Node *left, *right; } BTNode; BTNode* EXPR(); BTNode* FACTOR(); BTNode* makeNode(char c); void freeTree(BTNode *root); void printResult(BTNode *root);

Input

The input contains a sequences of prefix expression. It only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’. The length of prefix expression is shorter than 30.

Output

It has 5 variables 'A', 'B', 'C', 'D', and output, each variable is separated by a space.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10982.c

Partial Judge Header

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

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