[已解决]【C++板块提升计划】梦想护卫舰 第20关 逻辑表达式

zhangjinxuan

上一关：铺地毯

梦想护卫舰 第20关 逻辑表达式

你们的聪明才智惊住了他们，不过他们还是不服气

打算用一个逻辑表达式来难住你们

在一个逻辑表达式中，元素的值只有两种可能：0（表示假）和 1（表示真）。元素之间有多种可能的逻辑运算，本题中只需考虑如下两种：“与”（符号为 &）和“或”（符号为 |）。其运算规则如下：

0&0=0 0&1=0 1&0=0 1&1=1
0|0=0 0|1=1 1|0=1 1|1=1

在一个逻辑表达式中还可能有括号。规定在运算时，括号内的部分先运算；两种运算并列时，& 运算优先于 | 运算；同种运算并列时，从左向右运算。

比如，表达式 0|1&0 的运算顺序等同于 0|(1&0)；表达式 0&1&0|1 的运算顺序等同于 ((0&1)&0)|1。

此外，在 C++ 等语言的有些编译器中，对逻辑表达式的计算会采用一种“短路”的策略：在形如 a&b 的逻辑表达式中，会先计算 a 部分的值，如果 a=0，那么整个逻辑表达式的值就一定为 0，故无需再计算 b 部分的值；同理，在形如 a|b 的逻辑表达式中，会先计算 a 部分的值，如果 a=1那么整个逻辑表达式的值就一定为 1，无需再计算 b 部分的值。

现在给你一个逻辑表达式，你需要计算出它的值，并且统计出在计算过程中，两种类型的“短路”各出现了多少次。需要注意的是，如果某处“短路”包含在更外层被“短路”的部分内则不被统计，如表达式 1|(0&1) 中，尽管 0&1 是一处“短路”，但由于外层的 1|(0&1) 本身就是一处“短路”，无需再计算 0&1 部分的值，因此不应当把这里的 0&1 计入一处“短路”。

输入格式
一个字符串，表示表达式

输出格式
输出共两行，第一行输出一个字符 0 或 1，表示这个逻辑表达式的值；第二行输出两个非负整数，分别表示计算上述逻辑表达式的过程中，形如 a&b 和 a|b 的“短路”各出现了多少次。

输入样例1

0&(1|0)|(1|1|1&0)

输出样例1

1
1 2

输入样例2

(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0

输出样例2

0
2 3

数据范围
对于所有数据，保证1 <= n <= 1e6，且字符串是一个合法的逻辑表达式

注意：本题非原创，转载于 CSP-J 2022 第三题，题解个人原创

C/C++时间限制：1000ms
C/C++空间限制：512mb
其他语言时间限制：2000ms
其他语言空间限制：1024mb

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]


最佳战士排行榜

	第一名	第二名	第三名
名字
链接
语言
效率
代码得分
综合得分
奖励	5鱼币5荣誉+“最佳答案(另一贴)”	3鱼币3荣誉+"最佳答案"(本贴)	2鱼币2荣誉

综合评分会参照运行时间（代码效率），代码长度，代码可读性，解题思路，代码得分等来进行评分

                               
登录/注册后可看大图

下一关：解题

创作不易，如果你喜欢，别忘了评分、顶

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-2-4 11:05:45

看看

跳转到最佳答案楼层

元豪

研究研究, 先抢个楼先

sfqxx

看看

dolly_yos2

好奇怪的算法，有点看不懂两个样例的意思（尤其是第二个）
按照 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;
}

zhangjinxuan

dolly_yos2 发表于 2023-2-4 11:55
好奇怪的算法，有点看不懂两个样例的意思（尤其是第二个）
按照 C 的标准样例一似乎应该只有一个 and_skip ...

只有20分：https://www.luogu.com.cn/record/101402602

dolly_yos2

zhangjinxuan 发表于 2023-2-4 12:16
只有20分：https://www.luogu.com.cn/record/101402602

符合预期，这对于这道题而言是一个错误的算法
（这道题本身的逻辑就很奇怪）

zhangjinxuan

dolly_yos2 发表于 2023-2-4 12:48
符合预期，这对于这道题而言是一个错误的算法
（这道题本身的逻辑就很奇怪）

ExiaGN001

P8815,完全没思路的

sfqxx

好像不是原创……

zhangjinxuan

sfqxx 发表于 2023-2-5 16:28
好像不是原创……

所以我没说原创

sfqxx

是我理解错了吗？

zhangjinxuan

sfqxx 发表于 2023-2-5 17:07
是我理解错了吗？

不好意思，我直接从之前抄的格式……

sfqxx

zhangjinxuan 发表于 2023-2-5 17:31
不好意思，我直接从之前抄的格式……

下一关已经出了，但!
在审核

ExiaGN001

下一关传送门坏了