| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10955 | Prefix to truth table 2 |
|
| 10990 | cheat sheet |
|
| 11616 | Editor |
|
| 11626 | BST - Remove |
|
Description
Give a prefix Boolean expression, which only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’, print its truth table which output equal to 1.
For example, if input is "&|AB|CA", then result will be
A B C D output
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
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 4 variables 'A', 'B', 'C', 'D', and output, each variable is separated by a space.
Sample Input Download
Sample Output Download
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
請寫出一個簡單的Editor，並且有左右、backspace功能
Input
input只有一行且最後沒有換行符號('\n')，裡面會有char a~z, A~Z, 0~9, 空白（' '）, 逗點（','）, 句點（'.'）, 驚嘆號（'!'）, 問號（'?'）, 左括號（'('）, 右括號（')'），當輸入這些字元，則在游標所在位置新增這個字元，注意:游標一開始就會在開頭
以及特殊指令
- 左 (/l)：將游標向左移動一格，若已經移動到開頭，則不做動作 （注意： 若這行是 abc，游標是可以移動到a前面，輸入1可以得到這行為1abc）
- 右 (/r)：將游標向右移動一格，若已經移動到結尾，則不做動作
- backspace (/b)：刪除游標前的一個字元
Output
根據input，輸出整行（最後須有換行符號'\n'）
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Giving you a Binary Search Tree (BST) and a list of numbers, you need to remove all the nodes in the BST whose value appears in the list.
Input
The first line contains an integer N (N < 500), represents the number of nodes in the BST.
The second line contains N integers, construct a BST in order of appearance (treat the first value as root).
The third lines contains an array of integers, remove all of them in BST if it existed.
for example: The BST constructed from sample input would be like :
Output
Output the in-order traversal of the BST.
Note: The corret result should be in ascending order .