[CSP-J 2022] 逻辑表达式

GitHub 跳转原题关系图返回列表

先按优先级把中缀表达式建成语法树，再用显式栈按短路语义迭代求值，只统计真正访问到的子树里的短路次数。

OJ: luogu

题目 ID: P8815

难度:普及+/提高

标签:栈字符串模拟

日期: 2026-06-19 20:55

题意

给出一个只包含 0、1、&、 $|$ 、括号的合法逻辑表达式。

需要输出：

表达式最终的值
形如 a&b 的短路次数
形如 $a|b$ 的短路次数

题目规定括号优先，& 高于 $|$ ，同级从左到右计算。

思路

最直接的办法是按文法递归下降解析，并在解析过程中按短路语义求值。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102#include <bits/stdc++.h>
using namespace std;

struct Result {
    int value;
    long long short_and;
    long long short_or;
};

static string s;
static int pos_idx;

Result parse_or();
void skip_or();

Result parse_factor() {
    if (s[pos_idx] == '0' || s[pos_idx] == '1') {
        int value = s[pos_idx] - '0';
        ++pos_idx;
        return {value, 0, 0};
    }

    ++pos_idx;  // skip '('
    Result res = parse_or();
    ++pos_idx;  // skip ')'
    return res;
}

void skip_factor() {
    if (s[pos_idx] == '0' || s[pos_idx] == '1') {
        ++pos_idx;
        return;
    }

    ++pos_idx;  // skip '('
    skip_or();
    ++pos_idx;  // skip ')'
}

Result parse_and() {
    Result left_res = parse_factor();

    while (pos_idx < (int)s.size() && s[pos_idx] == '&') {
        ++pos_idx;
        if (left_res.value == 0) {
            ++left_res.short_and;
            skip_factor();
        } else {
            Result right_res = parse_factor();
            left_res.value &= right_res.value;
            left_res.short_and += right_res.short_and;
            left_res.short_or += right_res.short_or;
        }
    }
    return left_res;
}

void skip_and() {
    skip_factor();
    while (pos_idx < (int)s.size() && s[pos_idx] == '&') {
        ++pos_idx;
        skip_factor();
    }
}

Result parse_or() {
    Result left_res = parse_and();

    while (pos_idx < (int)s.size() && s[pos_idx] == '|') {
        ++pos_idx;
        if (left_res.value == 1) {
            ++left_res.short_or;
            skip_and();
        } else {
            Result right_res = parse_and();
            left_res.value |= right_res.value;
            left_res.short_and += right_res.short_and;
            left_res.short_or += right_res.short_or;
        }
    }
    return left_res;
}

void skip_or() {
    skip_and();
    while (pos_idx < (int)s.size() && s[pos_idx] == '|') {
        ++pos_idx;
        skip_and();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;
    pos_idx = 0;
    Result ans = parse_or();
    cout << ans.value << '\n';
    cout << ans.short_and << ' ' << ans.short_or << '\n';
    return 0;
}

brute.cpp 用 $parse_or / parse_and / parse_factor$ 描述整个文法，并在发生短路时用 $skip_*$ 函数把右侧子表达式整体跳过。这个版本很适合理解题意和对拍。

正式解的问题在于：表达式长度能到 $10^6$ ，递归解析和递归求值都可能爆栈。

样例语法树

这张图展示样例 $0&(1|0)|(1|1|1&0)$ 对应的主要语法结构：

graph TD
  A["|"] --> B["&"]
  A --> C["|"]
  B --> D["0"]
  B --> E["(1|0)"]
  C --> F["|"]
  C --> G["1&0"]
  F --> H["1"]
  F --> I["1"]

从图里可以看到，短路求值本质上就是“先看左儿子，再决定要不要进右儿子”。例如左边的 $0&(1|0)$ ，只要看到左儿子是 0，就能直接确定整棵 & 子树结果为 0，右边整块都不会被访问。因此右子树内部的任何短路，也都不该被统计。

所以正式解分成两步：

先用运算符栈按优先级把中缀表达式建成语法树
再用显式栈模拟递归求值过程

求值时：

先处理左子树
若当前是 & 且左值为 0，统计一次 & 短路并直接返回
若当前是 $|$ 且左值为 1，统计一次 $|$ 短路并直接返回
否则继续处理右子树，再合并最终值

这样既满足短路定义，也避免了深递归。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132#include <bits/stdc++.h>
using namespace std;

const int MAXL = 1000000 + 5;

static int left_son[MAXL];
static int right_son[MAXL];
static char node_type[MAXL];
static unsigned char node_value[MAXL];
static int node_cnt;

static int value_stack[MAXL];
static char op_stack[MAXL];
static int eval_node_stack[MAXL];
static unsigned char eval_state_stack[MAXL];

int priority_of(char ch) {
    if (ch == '|') {
        return 1;
    }
    if (ch == '&') {
        return 2;
    }
    return 0;
}

int new_node(char ch, int left_id, int right_id) {
    ++node_cnt;
    node_type[node_cnt] = ch;
    left_son[node_cnt] = left_id;
    right_son[node_cnt] = right_id;
    return node_cnt;
}

void apply_once(int &value_top, int &op_top) {
    char op = op_stack[op_top--];
    int right_id = value_stack[value_top--];
    int left_id = value_stack[value_top--];
    value_stack[++value_top] = new_node(op, left_id, right_id);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int value_top = 0;
    int op_top = 0;

    for (char ch : s) {
        if (ch == '0' || ch == '1') {
            value_stack[++value_top] = new_node(ch, 0, 0);
        } else if (ch == '(') {
            op_stack[++op_top] = ch;
        } else if (ch == ')') {
            while (op_top > 0 && op_stack[op_top] != '(') {
                apply_once(value_top, op_top);
            }
            --op_top;
        } else {
            while (op_top > 0 && op_stack[op_top] != '(' &&
                   priority_of(op_stack[op_top]) >= priority_of(ch)) {
                apply_once(value_top, op_top);
            }
            op_stack[++op_top] = ch;
        }
    }

    while (op_top > 0) {
        apply_once(value_top, op_top);
    }

    int root = value_stack[value_top];
    long long short_and = 0;
    long long short_or = 0;

    int eval_top = 1;
    eval_node_stack[1] = root;
    eval_state_stack[1] = 0;

    // 迭代模拟递归求值，只在真正访问到的子树里统计短路次数。
    while (eval_top > 0) {
        int u = eval_node_stack[eval_top];
        char ch = node_type[u];

        if (ch == '0' || ch == '1') {
            node_value[u] = (ch == '1');
            --eval_top;
            continue;
        }

        if (eval_state_stack[eval_top] == 0) {
            eval_state_stack[eval_top] = 1;
            eval_node_stack[++eval_top] = left_son[u];
            eval_state_stack[eval_top] = 0;
            continue;
        }

        if (eval_state_stack[eval_top] == 1) {
            if (ch == '&' && node_value[left_son[u]] == 0) {
                ++short_and;
                node_value[u] = 0;
                --eval_top;
                continue;
            }
            if (ch == '|' && node_value[left_son[u]] == 1) {
                ++short_or;
                node_value[u] = 1;
                --eval_top;
                continue;
            }

            eval_state_stack[eval_top] = 2;
            eval_node_stack[++eval_top] = right_son[u];
            eval_state_stack[eval_top] = 0;
            continue;
        }

        if (ch == '&') {
            node_value[u] = node_value[left_son[u]] & node_value[right_son[u]];
        } else {
            node_value[u] = node_value[left_son[u]] | node_value[right_son[u]];
        }
        --eval_top;
    }

    cout << (int)node_value[root] << '\n';
    cout << short_and << ' ' << short_or << '\n';
    return 0;
}

复杂度

建树和求值都只会对每个字符或节点做常数次处理，所以总时间复杂度是 $O(|s|)$ ，空间复杂度也是 $O(|s|)$ 。

总结

这题的关键不是普通表达式求值，而是“短路会让整棵右子树失去访问资格”。把表达式显式建成语法树后，这个限制就会变得很自然。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P8815 [CSP-J 2022] 逻辑表达式

题目描述

逻辑表达式是计算机科学中的重要概念和工具，包含逻辑值、逻辑运算、逻辑运算优先级等内容。

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

$0 \mathbin{\&} 0 = 0 \mathbin{\&} 1 = 1 \mathbin{\&} 0 = 0$ ， $1 \mathbin{\&} 1 = 1$ ；
$0 \mathbin{|} 0 = 0$ ， $0 \mathbin{|} 1 = 1 \mathbin{|} 0 = 1 \mathbin{|} 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 计入一处“短路”。

输入格式

输入共一行，一个非空字符串 $s$ 表示待计算的逻辑表达式。

输出格式

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

输入输出样例 #1

输入 #1

text

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

输出 #1

text

1
21
1 2

输入输出样例 #2

输入 #2

text

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

输出 #2

text

1
20
2 3

说明/提示

【样例解释 #1】

该逻辑表达式的计算过程如下，每一行的注释表示上一行计算的过程：

plain

1
2
3
4
5
60&(1|0)|(1|1|1&0)
=(0&(1|0))|((1|1)|(1&0)) //用括号标明计算顺序
=0|((1|1)|(1&0))   //先计算最左侧的 &，是一次形如 a&b 的“短路”
=0|(1|(1&0))       //再计算中间的 |，是一次形如 a|b 的“短路”
=0|1               //再计算中间的 |，是一次形如 a|b 的“短路”
=1

【样例 #3】

见附件中的 expr/expr3.in 与 expr/expr3.ans。

【样例 #4】

见附件中的 expr/expr4.in 与 expr/expr4.ans。

【数据范围】

设 $\lvert s \rvert$ 为字符串 $s$ 的长度。

对于所有数据， $1 \le \lvert s \rvert \le {10}^6$ 。保证 $s$ 中仅含有字符 0、1、&、|、(、) 且是一个符合规范的逻辑表达式。保证输入字符串的开头、中间和结尾均无额外的空格。保证 $s$ 中没有重复的括号嵌套（即没有形如 ((a)) 形式的子串，其中 a 是符合规范的逻辑表达式）。

测试点编号	$\lvert s \rvert \le$	特殊条件
$1 \sim 2$	$3$	无
$3 \sim 4$	$5$	无
$5$	$2000$	1
$6$	$2000$	2
$7$	$2000$	3
$8 \sim 10$	$2000$	无
$11 \sim 12$	${10}^6$	1
$13 \sim 14$	${10}^6$	2
$15 \sim 17$	${10}^6$	3
$18 \sim 20$	${10}^6$	无

其中：
特殊性质 1 为：保证 $s$ 中没有字符 &。
特殊性质 2 为：保证 $s$ 中没有字符 |。
特殊性质 3 为：保证 $s$ 中没有字符 ( 和 )。

【提示】

以下给出一个“符合规范的逻辑表达式”的形式化定义：

字符串 0 和 1 是符合规范的；
如果字符串 s 是符合规范的，且 s 不是形如 (t) 的字符串（其中 t 是符合规范的），那么字符串 (s) 也是符合规范的；
如果字符串 a 和 b 均是符合规范的，那么字符串 a&b、a|b 均是符合规范的；
所有符合规范的逻辑表达式均可由以上方法生成。

[CSP-J 2022] 逻辑表达式

目录

题意

思路

样例语法树

代码

复杂度

总结

一图流解析