|
|
发表于 2023-2-4 11:55:34
|
显示全部楼层
好奇怪的算法，有点看不懂两个样例的意思（尤其是第二个）
按照 C 的标准样例一似乎应该只有一个 and_skip 和一个 or_skip，只有第一个 0 和第二个括号中的第一个 1 会被求值
一些非常朴素的实验- #include <stdio.h>
- #include <stdbool.h>
- #define eval_helper(name, value) int name;bool f_##name(){name = 1; return value;}
- eval_helper(a, false);
- eval_helper(b, true);
- eval_helper(c, false);
- eval_helper(d, true);
- eval_helper(e, true);
- eval_helper(f, true);
- eval_helper(g, false);
- int main(){
- if(f_a() && (f_b() || f_c()) || (f_d() || f_e() || f_f() && f_g())) printf("!\n");
- printf("%d %d %d %d %d %d %d\n", a, b, c, d, e, f, g);
- return 0;
- }
一个不正确的重量级解法，既然写了就发上来吧- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.h>
- struct eval_environment{
- size_t or_skip;
- size_t and_skip;
- };
- struct tree_node{
- bool (*eval)(struct tree_node* target, struct eval_environment* environment);
- void (*release)(struct tree_node* target);
- void (*print)(struct tree_node* target, FILE* stream);
- };
- struct node_list{
- struct tree_node* node;
- struct node_list* next;
- };
- struct binary_expression_node{
- struct tree_node tree_node;
- struct node_list* children;
- struct node_list* last_children;
- };
- bool and_eval(struct tree_node* target, struct eval_environment* environment){
- struct binary_expression_node* node = (struct binary_expression_node*)target;
- bool result = true;
- for(struct node_list* child = node->children; child != NULL; child = child->next){
- result = result && child->node->eval(child->node, environment);
- if(result == false && child != node->last_children){
- environment->and_skip += 1;
- break;
- }
- }
- return result;
- }
- bool or_eval(struct tree_node* target, struct eval_environment* environment){
- struct binary_expression_node* node = (struct binary_expression_node*)target;
- bool result = false;
- for(struct node_list* child = node->children; child != NULL; child = child->next){
- result = result || child->node->eval(child->node, environment);
- if(result == true && child != node->last_children){
- environment->or_skip += 1;
- break;
- }
- }
- return result;
- }
- void binary_print(struct tree_node* target, char op, FILE* stream){
- struct binary_expression_node* node = (struct binary_expression_node*)target;
- fprintf(stderr, "(");
- bool begin = true;
- for(struct node_list* child = node->children; child != NULL; child = child->next){
- if(begin) begin = false;
- else fprintf(stream, " %c ", op);
- child->node->print(child->node, stream);
- }
- fprintf(stderr, ")");
- }
- void and_print(struct tree_node* target, FILE* stream){
- binary_print(target, '&', stream);
- }
- void or_print(struct tree_node* target, FILE* stream){
- binary_print(target, '|', stream);
- }
- void binary_release(struct tree_node* target){
- struct binary_expression_node* node = (struct binary_expression_node*)target;
- struct node_list* next = NULL;
- for(struct node_list* child = node->children; child != NULL; child = next){
- next = child->next;
- child->node->release(child->node);
- free(child);
- }
- free(target);
- }
- void binary_attach_child(struct binary_expression_node* node, struct tree_node* child){
- struct node_list* l = malloc(sizeof(struct node_list));
- l->node = child;
- l->next = NULL;
- node->last_children->next = l;
- node->last_children = l;
- }
- struct value_expression_node{
- struct tree_node tree_node;
- bool value;
- };
- bool value_eval(struct tree_node* target, struct eval_environment* environment){
- struct value_expression_node* node = (struct value_expression_node*)target;
- return node->value;
- }
- void value_release(struct tree_node* target){
- free(target);
- }
- void value_print(struct tree_node* target, FILE* stream){
- struct value_expression_node* node = (struct value_expression_node*)target;
- fprintf(stream, "%d", node->value);
- }
- struct tree_node* make_or_node(char** input);
- struct tree_node* make_and_node(char** input);
- struct tree_node* make_unary_node(char** input);
- struct tree_node* make_value_node(char** input);
- struct tree_node* make_or_node(char** input){
- struct tree_node* sub_node = make_and_node(input);
- if(**input != '|') return sub_node;
- struct binary_expression_node* node = malloc(sizeof(struct binary_expression_node));
- node->tree_node.eval = or_eval;
- node->tree_node.release = binary_release;
- node->tree_node.print = or_print;
- node->children = malloc(sizeof(struct node_list));
- node->children->node = sub_node;
- node->children->next = NULL;
- node->last_children = node->children;
- while(**input == '|'){
- *input += 1;
- sub_node = make_and_node(input);
- binary_attach_child(node, sub_node);
- }
- return (struct tree_node*)node;
- }
- struct tree_node* make_and_node(char** input){
- struct tree_node* sub_node = make_unary_node(input);
- if(**input != '&') return sub_node;
- struct binary_expression_node* node = malloc(sizeof(struct binary_expression_node));
- node->tree_node.eval = and_eval;
- node->tree_node.release = binary_release;
- node->tree_node.print = and_print;
- node->children = malloc(sizeof(struct node_list));
- node->children->node = sub_node;
- node->children->next = NULL;
- node->last_children = node->children;
- while(**input == '&'){
- *input += 1;
- sub_node = make_unary_node(input);
- binary_attach_child(node, sub_node);
- }
- return (struct tree_node*)node;
- }
- struct tree_node* make_unary_node(char** input){
- if(**input == '('){
- *input += 1;
- struct tree_node* result = make_or_node(input);
- *input += 1;
- return result;
- }else{
- return make_value_node(input);
- }
- }
- struct tree_node* make_value_node(char** input){
- struct value_expression_node* node = malloc(sizeof(struct value_expression_node));
- node->tree_node.eval = value_eval;
- node->tree_node.release = value_release;
- node->tree_node.print = value_print;
- if(**input == '0') node->value = false;
- else node->value = true;
- *input += 1;
- return (struct tree_node*)node;
- }
- void clear_input(char* buffer){
- char* next = buffer;
- while(*buffer != '\0'){
- if(
- *buffer == '0'
- || *buffer == '1'
- || *buffer == '('
- || *buffer == ')'
- || *buffer == '&'
- || *buffer == '|'
- ) *next++ = *buffer;
- buffer++;
- }
- *next = '\0';
- }
- int main(){
- enum{ BufferSize = 2000000 };
- char* buffer = malloc(BufferSize);
- size_t real_size = fread(buffer, 1, BufferSize, stdin);
- buffer[real_size] = '\0';
- char* input = buffer;
- clear_input(buffer);
- fprintf(stderr, "[%s]\n", buffer);
- struct tree_node* expression_tree = make_or_node(&input);
- expression_tree->print(expression_tree, stderr);
- fprintf(stderr, "\n");
- struct eval_environment environment = { .or_skip = 0, .and_skip = 0 };
- int result = expression_tree->eval(expression_tree, &environment);
- printf("%d\n%zu %zu\n", result, environment.and_skip, environment.or_skip);
- expression_tree->release(expression_tree);
- free(buffer);
- return 0;
- }
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
置顶卡
千斤顶
显身卡
发表于 2023-2-4 11:05:45
楼主
