论坛 › C\C++交流 › 【C++板块提升计划】梦想护卫舰 第20关 逻辑表达式

zhangjinxuan 发表于 2023-2-4 07:56:59

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

本帖最后由 zhangjinxuan 于 2023-5-22 18:18 编辑


上一关：铺地毯


梦想护卫舰 第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

static/image/hrline/1.gif

答案与解析
**** Hidden Message *****


最佳战士排行榜

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

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

static/image/hrline/1.gif

下一关：解题

创作不易，如果你喜欢，别忘了评分、顶{:10_281:}

元豪 发表于 2023-2-4 09:00:29

研究研究, 先抢个楼先

sfqxx 发表于 2023-2-4 11:05:45

看看

dolly_yos2 发表于 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 = '\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 发表于 2023-2-4 12:16:52

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

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

dolly_yos2 发表于 2023-2-4 12:48:56

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

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

zhangjinxuan 发表于 2023-2-4 13:59:15

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

{:10_277:}

ExiaGN001 发表于 2023-2-4 15:05:01

P8815,完全没思路的

sfqxx 发表于 2023-2-5 16:28:00

好像不是原创……

zhangjinxuan 发表于 2023-2-5 17:05:33

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

所以我没说原创

sfqxx 发表于 2023-2-5 17:07:00

是我理解错了吗？

zhangjinxuan 发表于 2023-2-5 17:31:57

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

不好意思，我直接从之前抄的格式……{:10_282:}

sfqxx 发表于 2023-2-5 18:18:49

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

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

ExiaGN001 发表于 2023-2-7 11:43:42

下一关传送门坏了

查看完整版本: 【C++板块提升计划】梦想护卫舰 第20关 逻辑表达式