|
|
发表于 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
楼主
