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 a prefix Boolean expression, which only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’. Also given the values of ‘A’, ‘B’, ‘C’, and ‘D’. Please evaluate the value of the prefix Boolean expression.

For example, if the expression is "|&AC|AB" and, A, B, C, D are 0, 1, 0, 1 then the result will be 1.

Input

The input contains 2 lines.

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

The second line contains 4 values of 1 or 0, representing the values of A, B, C, D respectively. Each is separated by a space.

Output

Print out the value of the prefix Boolean expression. There should be no trailing newline character at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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 in the position at p0, p1, …pk-1 of the linked list, where 1<=p0<p1<…pk-1<=N. If the node is not existing,do nothing. And show the final results.

For example, if the first sequence is 1, 2, 3, 4, 5, 6,7, a linked list is created as

If the second sequence is 1, 1, 4, do the follows.

After p1=1, the list becomes

because the first node is 1.  After p2 = 1, the list becomes

because the first node is 2.  After p3 = 4, the list becomes

because the fourth node is 6.

 

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 at 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(&head) and deleteNode(&head, pi).  You only need to implement createList(&head) and deleteNode(&head, pi) in function.c, in which head is the head of the linked list, and pi is the node at pi to be deleted.

 

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 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 sequence of positive integers as the linklist and the order, except the last one, which is -1, indicating the end of the sequence. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11883.c

Partial Judge Header

11883.h

Tags

Discuss

Description

Niflheimr loves playing with trees, and this time he wants to try trees with multiple children.
So he begins with the simplest part: traversing the tree.

Given the height of the tree and the number of children for each node (except for leaf nodes), and number(編號) the tree nodes from top to bottom, from left to right. Id begins with 0.
Niflheimr wants to perform a preorder-like traversal. That is, for every tree node, print out the id of itself first, then traverse its children from left to right.

For example, height = 3 and number of children = 3,

The number inside the nodes are their ids.

The preorder-like traversal sequence will be "0 1 4 5 6 2 7 8 9 3 10 11 12".

Input

Input contains a single line with two integers.

The first integer is the height of the tree.

The second integer is the number of childs for an internal node.

It is guaranteed that:

• The height of the tree won't exceed 20.
• The number of children for each node (except for leaf nodes) is less than 5.
• The number of total nodes in the tree won't exceed 5*10⁶ (Is it necessary to build the whole tree?)

Output

Print out the preorder-like traversal sequence of the tree. There is a space after each number, and print a '\n' at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This problem is the midterm exam bonus!​

Niflheimr is a poor student. He can't afford to buy a scientific caculator, but his simple calculator can't type in a mathematical expression.

 

So he decided to create a calculator on his own!
He learned in class that he can evaluate an expression by converting the expression into prefix and create a binary tree accordingly.

Unfortunately, Niflheimr is a careless person. He often types the expression wrong, and if that happens, after he removed the wrong part, he has to rebuild the whole binary tree and calculate everything again. He thinks that rebuilding is too sloooooooooow, so he asks you to help him make it fast.
If you can help him correctly, he will feel happy and give you a big AC.

==========

Note (2018.4.11) : (Thanks J3soon for the reminder!) There won't be any cross-subtree deletion, i.e. the following case won't happen in our testcase:

Note2 (2018.4.12) : In this problem, the expression will never be empty.

Sorry for the incompleteness of the problem description ><"

==========

Hint: If you got a TLE in the last testcase, instead of rebuilding the tree all the time, try to add some extra field in the node inside the binary tree, e.g. size, and utilize them to speed up operations.

For example, you can define your Node inside the binary tree like this:

Input

First line of input is an integer N, indicating the # of deletions.
Second line of input is the expression in prefix. The expression contains only +, -, * and digits. All the number in the expression are between 1 and 9, that is, every number in the expression are DIGITS(個位數).

The following N lines are deletions, the format is "A B", indicating that Niflheimr wants to delete from Ath character to Bth character in the expression. 
Note that the index starts from 1, and the index of the characters in the expression should be re-calculated after each deletion.

 

It is guaranteed that:

• The length of the expression is less than 3*10⁵
• 1 ≤ N ≤ 3*10⁴
• The height of the binary tree is always ≤ 20.
• The range of deletion is always within the expression, i.e. 1 ≤ A, B ≤ length of expression
• The expression is always valid after each operation.

Output

The output consists of N+1 lines.
First line of output is the result of the original expression.
The following N lines are the results after each deletion.
Niflheimr hates big numbers, since it will make calculation more complex. So for every output, please print the result after modulo 10007 (% 10007).

Sample Input  Download

Sample Output  Download

Tags

Discuss