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

In this problem, you have to build a Boolean expression with right associativity into a syntax tree.

The associativity of an operator is a property that determines how operators of the same precedence are grouped in the absence of parentheses.

EX.

Consider the expression: A&B|C

With left associativity, the expression is interpreted as:

        (A&B)|C

With right associativity, the expression is interpreted as:

        A&(B|C)

 

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 following right associativity.

To parse the infix expression with parentheses following right associativity, use the grammar below.

EXPR = FACTOR | FACTOR OP EXPR

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

 

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 contains N infix expressions, which has at most 4 variables ‘A’, ’B’, ‘C’, and ‘D’, two operators ‘&’ and ‘|’, and parentheses. All parentheses are matched. 

Output

The output contains N prefix expressions without parentheses, which are preorders of syntax trees.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11389.c

Partial Judge Header

11389.h

Tags

Discuss

Description

This problem asks you：

 

Step 1: Create a linked list to store a sequence of colors.

Step 2: Insert a node at an appropriate position.

Step 3: Check nodes adjacent to the inserted node on both left and right sides.

Step 4: Delete the checked node if its color is the same as the inserted node.

Step 5: Do Step 3 and Step 4 again until the color of checked node is different.

 

Note:

• Color = {BLUE, GREEN, RED, HEAD, TAIL}, but HEAD and TAIL are only used to create the Head node and the Tail node in the beginning.
• Each statement for inserting contains a command and a position. Translate the command to the corresponding Color and insert it if the position is valid.
• You cannot insert a node after the Tail node.

 

For example, if the input is

r r g r e

3

r 1

b 4

g 6

 

 

The first sequence is r r g r e, so a linked list is created as

For the statement (r, 1):

Step 2:

Step 3 ~ Step 5 (on the left side):

Step 3 ~ Step 5 (on the right side):

For the statement (b, 4):

 

Step 2:

Step 3 ~ Step 5:

For the statement (g, 6):

 

Due to illegal position, ignore this statement.

Finally, the output should be red green red blue.

 

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 contains 2 parts:

 

1. A sequence of initial colors as the linked list, except the last one, which is e.

 

1. A number N means the number of operations, and each of the next N lines contains a pair of numbers (X, Y). X is the Color and Y is the position at which you are asked to insert a new node.

Output

The output contains the sequence of the remaining colors.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11390.c

Partial Judge Header

11390.h

Tags

Discuss