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 link list structure named Node.

 

typedef struct _Node {

    int data;

    struct _Node *next;

} Node;

 

Given a list, rotate the list to the left by k places, where k is non-negative and k is smaller than the count of nodes in linked list.

For example: 
Given 1->2->3->4->5->NULL and k = 3, 
return 4->5->1->2->3->NULL.

 

Input

The input contains 2 sequence of positive integers.The first sequence is to create a linked list of integers, except the last one, which is -1, indicating the end of the sequence. The second line is an integer k. 

Output

The output contains the sequence of resulting linklist.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11283.c

Partial Judge Header

11283.h

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

Given an infix expression which contains three operators ‘+’, ‘-’ and ‘*’, operating on non-negative integers. Build a corresponding syntax tree for it.

To parse such infix expressions, use the grammar below.

Expression  := Term | Expression ADDSUB(+ -) Term
Term        := Factor | Term MUL(*) Factor
Factor      := Integer

You are provided with function.h and main.c, where function.h contains the declarations/definitions of the involved data structures, variables, constants, and functions, while main.c contains the implementation of two functions printPrefix and FACTOR. You only need to implement the following five functions in function.c.

Node* EXPR()   // parse an infix expression and generate its syntax tree

Node* TERM()   // handle the rule Term := Factor | Term MUL Factor

Node* makeNode(char c, int value) // create a tree node without any child

void freeTree(Node *root) // free the whole tree

long long calculate(Node *root) // calculate the result of the infix expression

 

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 consists of multiple lines. Each line is an infix expression.

The input integers are guaranteed to be less than 1000, and all the intermediate values during caculation won't exceed 10¹⁸ (don't need to consider overflow if you use long long).

The length of each expression is less than 10⁶. Total length of all lines is less than 10⁷.

Output

For each infix expression, print its prefix expression and result.

Sample Input  Download

Sample Output  Download

Partial Judge Code

12196.c

Partial Judge Header

12196.h

Tags

Discuss

Description

Attention: This is makeup for lab3
For those who already got full score on Fairy Testing in lab3, you don't need to do this problem.
Otherwise, if you get a higher score on this problem than you did in lab3, we will update your score to the higher one in lab3.

We strongly suggest you do the other 3 problems first since the problems of mid-term account for more score.

In this problem, you are given a prefix Boolean expression, which has at most N=10^5 variables and 2 kinds of operators ‘&’ and ‘|’. Each variable has an ID number. The values of these variables can be either 0 or 1, and are all initialized as 0.

You will be given M ID numbers. For each ID number, you should flip (0 will become 1, 1 will become 0) the value of the corresponding variable and then compute/output the result of the prefix Boolean expression.

Example:

Assume the prefix Boolean expression is &[1][2] and the given ID numbers are “2 1”. First the value of variable 2 will change from 0 to 1. The output of &[1][2] is 0&1=0. Next, the value of variable 1 will change from 0 to 1. The output of &[1][2] is 1&1=1.

 

Hint: (You can go to the Input/Output description directly, and come back for hints if necessary.)

Hint 1: To solve this problem, you can parse the input and derive the output recursively each time a variable is flipped. Unfortunately, this brute-force approach is not efficient and can lead to TLE, in particular the 3^rd and 4^th testcases in this problem. We encourage you to use the syntax tree of the prefix Boolean expression for better efficiency.

Hint 2: The key idea behind the syntax-tree approach is to avoid re-evaluation of the whole expression every time a bit is flipped. Some more hints are provided for you as follows:

• [Data structure] Use a tree node pointer array to record the address of each variable (leaf) node of the syntax tree: you can locate each variable to be flipped directly;
• [Data structure] For each tree node i, record the value of its subtree (rooted at node i);
• [Algorithm] Starting from the variable node to be flipped, move upward following the syntax tree and update the node values until the output of the syntax tree (or the Boolean expression) can be determined. 

Example:

Consider the following syntax tree for "|&|[1][2][3][4]". Assume [1] is flipped. You will find that the value of node A should be changed to 1|0=1. Moreover, you note that the value of B remains unchanged, i.e., 1&0=0, and the checking process can stop.

 

Later, when [3] is flipped, both the values of node B and the root node should be changed. In this case, the output is also changed.

Sample structure:

typedef struct node{

    int value; // This is the value of the subtree, not the ID number

    int tokentype;

    struct node *leftchild;

    struct node *rightchild;

    struct node *parent; //pointing to the parent node

}Node;

Node* variable[100001]; // This array stores the pointers pointing to the tree nodes. For example, variable[0] points to the node with ID number 0.

Input

The first line has one number T, 0<T<= 7, indicating the number of testcases.

The following lines are the inputs of the testcases.

Each testcase contains three lines:

1. N, M (0<N<=100000, indicating the number of variables in a given prefix Boolean expression. 0<M<=100000, indicating how many times the values are flipped).

2. A string S, describing the prefix Boolean expression (& means and gate, | means or gate, [i] means a variable ID)

3. M numbers, where each number i means the value of variable i is flipped. The order matters.

 

Note that all the variables are initially 0.

Each ID number only appears once in the prefix Boolean expression.

The depth of the tree is no more than 30.

Output

For each testcase, you should output M lines, each showing the output of the prefix Boolean expression after a variable is flipped.

0 for false, 1 for true.

Sample Input  Download

Sample Output  Download

Tags

Discuss