[CSP-J 2022] 逻辑表达式

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

先用调度场算法把中缀表达式转成后缀，再由后缀建出语法树，最后在树上按短路语义 dfs 求值，只统计真正访问到的子树里的短路次数。

OJ: luogu

题目 ID: P8815

难度:普及+/提高-

标签:栈字符串模拟

创建: 2026-06-19 20:55

更新: 2026-10-07 12:15

前置题目

luogu P1175表达式的转换B 的第一阶段直接复用 A 的「运算符栈按优先级与括号把中缀转后缀」这一步调度场转换，再叠加由后缀建语法树与短路语义的迭代求值

题意

给出一个只包含 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$ ，递归下降的解析最坏要递归 $O(|s|)$ 层。正式解把解析换成非递归的调度场算法，求值改成在显式语法树上做短路 dfs。

样例语法树

这张图展示样例 $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，右边整块都不会被访问。因此右子树内部的任何短路，也都不该被统计。

所以正式解分成三步：

用调度场算法把中缀表达式转成后缀表达式（后缀里不含括号）
扫描后缀表达式建出语法树
在语法树上 dfs 后根遍历，边求值边统计短路次数

第三步是后根遍历：先递归算左子树，拿到左值后才能判断本节点会不会短路：

遇到 & 且左值为 0，统计一次 & 短路，本节点值为 0，并且不递归右子树
遇到 $|$ 且左值为 1，统计一次 $|$ 短路，本节点值为 1，同样跳过右子树
否则递归右子树，最后用左右儿子的值算出本节点的值

短路时不递归右子树，右子树内部的短路自然不会被统计，正满足“被外层短路的整块不计入统计”。表达式退化成一条链（如 1|1|1|...）时递归深度会到 $O(|s|)$ ，评测机栈足够大时可以直接递归。

代码

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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-09 06:46
 * update_at: 2026-10-05 15:03
 */
// main.cpp：P8815 逻辑表达式，正式解。
// 分三步完成：
//   1. 用调度场算法把中缀表达式转成后缀表达式（后缀里没有括号）
//   2. 扫描后缀表达式，用一个栈建出表达式树
//   3. 在表达式树上 dfs 后根遍历，按短路语义求值，同时统计短路次数
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MAXL = 1000000 + 5;

string s;                 // 输入的中缀表达式
string postfix;           // 转换得到的后缀表达式

// 表达式树节点，struct 只放数据，一个节点的信息聚合在一起
struct Node {
    char type;   // 叶子是 '0'/'1'，内部节点是 '&'/'|'（只有 4 种，用 char 省内存）
    ll left;     // 左儿子编号，叶子为 0
    ll right;    // 右儿子编号，叶子为 0
    ll value;    // 节点的值，只会是 0 或 1
};

// 动态化静态：不用指针，用静态大数组 + node_cnt 当分配指针，
// new_node 每次“开点”就把 node_cnt 加一，返回新节点编号。
Node node[MAXL];          // 表达式树，节点 u 就是 node[u]
ll node_cnt;              // 已经创建的节点个数，最后一个节点是 node[node_cnt]

ll short_and;             // '&' 的短路次数
ll short_or;              // '|' 的短路次数

// 判断是不是运算符（本题只有两种）
bool is_op(char ch) {
    return ch == '&' || ch == '|';
}

// 运算符优先级，数字越大越先算；'(' 不参与比较，固定返回 0
ll priority_of(char ch) {
    if (ch == '|') {
        return 1;
    }
    if (ch == '&') {
        return 2;
    }
    return 0;
}

// 第一步：调度场算法，中缀表达式 -> 后缀表达式。
// 数字直接追加到结果里；运算符要入栈时，先把栈顶那些“应该先算”的弹出来。
// 因为本题同级都是从左到右算，所以栈顶优先级 >= 当前优先级时就要弹出。
string infix_to_postfix() {
    string result;
    stack<char> op_stack;  // 调度场算法的运算符栈，存放运算符和 '('

    for (ll i = 0; i < (ll)s.size(); i++) {
        char ch = s[i];

        if (!is_op(ch) && ch != '(' && ch != ')') {
            result.push_back(ch);  // 操作数直接输出
        } else if (ch == '(') {
            op_stack.push(ch);
        } else if (ch == ')') {
            // 把这对括号内部的运算符全部弹出，最后丢掉 '('
            while (op_stack.top() != '(') {
                result.push_back(op_stack.top());
                op_stack.pop();
            }
            op_stack.pop();  // 丢掉 '('
        } else {
            while (!op_stack.empty() && op_stack.top() != '(' &&
                   priority_of(op_stack.top()) >= priority_of(ch)) {
                result.push_back(op_stack.top());
                op_stack.pop();
            }
            op_stack.push(ch);
        }
    }

    // 扫描结束后，栈里剩下的运算符按顺序弹出
    while (!op_stack.empty()) {
        result.push_back(op_stack.top());
        op_stack.pop();
    }
    return result;
}

// 新建一个表达式树节点（动态开点），返回编号
ll new_node(char ch, ll left_id, ll right_id) {
    node_cnt++;
    node[node_cnt].type = ch;
    node[node_cnt].left = left_id;
    node[node_cnt].right = right_id;
    return node_cnt;
}

// 第二步：扫描后缀表达式建表达式树，返回根节点编号。
// 后缀里是「左操作数 右操作数 运算符」，所以弹栈时先弹出的是右儿子。
ll build_expr_tree() {
    stack<ll> node_stack;  // 建树时的节点栈，存放还没有被合并的子树根编号

    for (ll i = 0; i < (ll)postfix.size(); i++) {
        char ch = postfix[i];

        if (!is_op(ch)) {
            node_stack.push(new_node(ch, 0, 0));  // 操作数建成叶子
        } else {
            ll right_id = node_stack.top();
            node_stack.pop();
            ll left_id = node_stack.top();
            node_stack.pop();
            node_stack.push(new_node(ch, left_id, right_id));
        }
    }

    return node_stack.top();  // 栈里最后剩下的就是整棵树的根
}

// 第三步：dfs 后根遍历表达式树，把求值和短路统计合在一起做。
// 后根遍历：先递归算完左子树，拿到它的值后才能判断要不要短路。
// 短路时整棵右子树都不递归，所以右子树内部的短路也就不会被统计。
void dfs_calc_value(ll u) {
    if (!is_op(node[u].type)) {
        node[u].value = node[u].type - '0';  // 叶子：值就是 '0'/'1' 本身
        return;
    }

    dfs_calc_value(node[u].left);  // 先递归算左子树

    // a&b 中 a 为 0，或 a|b 中 a 为 1：短路，右子树不用求值
    if (node[u].type == '&' && node[node[u].left].value == 0) {
        short_and++;
        node[u].value = 0;
        return;
    }
    if (node[u].type == '|' && node[node[u].left].value == 1) {
        short_or++;
        node[u].value = 1;
        return;
    }

    // 不短路：右子树也要递归求值，最后算自己
    dfs_calc_value(node[u].right);
    if (node[u].type == '&') {
        node[u].value = node[node[u].left].value & node[node[u].right].value;
    } else {
        node[u].value = node[node[u].left].value | node[node[u].right].value;
    }
}

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

    cin >> s;

    postfix = infix_to_postfix();
    ll root = build_expr_tree();
    dfs_calc_value(root);

    cout << node[root].value << '\n';
    cout << short_and << ' ' << short_or << '\n';
    return 0;
}

Python 短解法

Python 版可以更进一步：不显式建树，把“一段表达式的结果”记成三元组（值、& 短路次数、 $|$ 短路次数）。调度场算法每归约一次，就把栈顶的左右两段合成一段：左段一旦短路，右段一整段都不求值，右段的短路次数直接丢弃——这正对应树上写法“短路时不递归右子树”。归约完栈里剩下的最后一段就是答案。

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-05 15:21
# update_at: 2026-10-05 15:21

# 这个代码的特点: 不用真的建立表达式树，用调度场算法+短路计数来直接计算
# vals 里面直接存 计算的结果和短路的次数

import sys

type Value = tuple[int, int, int]  # 一段表达式的结果：(值, & 短路次数, | 短路次数)
type Values = list[Value]          # 调度场算法的操作数栈，栈里每段是一个 Value

PRIO = {'&': 2, '|': 1}  # 运算符优先级：& 高于 |；'(' 不参与比较，取默认 0


def reduce_top(vals: Values, ops: list[str]) -> None:
    """归约一层：把栈顶运算符和左右两段结果合成一段，短路时丢弃右段的短路次数。"""
    right = vals.pop()
    left = vals.pop()
    op = ops.pop()
    lval, l_and, l_or = left
    rval, r_and, r_or = right

    if op == '&':
        if lval == 0:
            # a&b 中 a 为 0：整段值为 0，b 一整段都不求值，右段的短路次数全部作废
            vals.append((0, l_and + 1, l_or))
        else:
            vals.append((lval & rval, l_and + r_and, l_or + r_or))
    else:
        if lval == 1:
            # a|b 中 a 为 1：整段值为 1，b 一整段都不求值，右段的短路次数全部作废
            vals.append((1, l_and, l_or + 1))
        else:
            vals.append((lval | rval, l_and + r_and, l_or + r_or))


def evaluate(s: str) -> Value:
    """调度场算法边扫描边归约，直接算出整个表达式的结果。"""
    vals: Values = []
    ops: list[str] = []  # 运算符栈，只放 '&', '|', '('

    for ch in s:
        if ch in '01':
            vals.append((int(ch), 0, 0))  # 叶子：单个 0/1，自身没有短路
        elif ch == '(':
            ops.append(ch)
        elif ch == ')':
            while ops[-1] != '(':
                reduce_top(vals, ops)
            ops.pop()  # 丢掉 '('
        else:
            # 栈顶“该先算”的运算符先归约；同级从左到右，所以 >= 就弹
            while ops and ops[-1] != '(' and PRIO[ops[-1]] >= PRIO[ch]:
                reduce_top(vals, ops)
            ops.append(ch)

    while ops:
        reduce_top(vals, ops)
    return vals[0]  # 归约完栈里剩下的最后一段就是整个表达式


def solve() -> None:
    # 输入就是一整行表达式本身，没有空白可切分，直接整行读
    s = sys.stdin.readline().strip()
    value, short_and, short_or = evaluate(s)
    print(value)
    print(short_and, short_or)


if __name__ == "__main__":
    solve()

时间复杂度同为 $O(|s|)$ ，只是 Python 常数更大， $10^6$ 长度的最坏数据实测不到 $1$ 秒。

复杂度

建树和求值都只会对每个字符或节点做常数次处理，所以总时间复杂度是 $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] 逻辑表达式

目录

题意

思路

样例语法树

代码

Python 短解法

复杂度

总结

一图流解析