表达式的值

题目描述

对 1 位二进制变量定义两种运算：⊕（字符 +）结果为 0 当且仅当两边都为 0（即逻辑或），×（字符 *）结果为 1 当且仅当两边都为 1（即逻辑与）；求值顺序为先算括号内、再算 ×、最后算 ⊕，同级从左到右。

给定一个只含 + * ( ) 四种字符的未完成表达式，操作数位置是横线，横线数 = 运算符个数 + 1，每条横线独立填入 0 或 1，求使表达式值为 0 的填法数模 10007。输入共 2 行：第一行为整数 L（0 ≤ L ≤ 100000），第二行为长度为 L 的表达式串；输出一行一个整数。例如输入 L=4、串 +(*)（即 _+(_*_)）时，答案为 3。

思路

对每个子表达式只记录 (c0, c1)——使它取 0 / 取 1 的横线填法数，叶子横线是 (1,1)；× 合并时 c1=a1·b1，⊕ 合并时 c0=a0·b0，另一维用总方案数 (a0+a1)(b0+b1) 相减（注意题面的 ⊕ 按真值表是逻辑或而非异或）。用调度场双栈按优先级一遍扫描、边扫边合并（该出现操作数时补一条横线 (1,1)，括号用栈边界隔离），最后栈底 c0 即答案，时间 O(L)、空间 O(L)，不怕深括号嵌套。

参考代码

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#!/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-02 09:20
# update_at: 2026-10-02 09:32

import sys

MOD = 10007          # 方案数对 10007 取模
PREC = {'+': 1, '*': 2}   # 题面规定 × 先算、⊕ 后算，同级从左到右


def reduce_top(opds: list[tuple[int, int]], ops: list[str]) -> None:
    """弹出栈顶运算符，把它的两个操作数 (取0方案数, 取1方案数) 合并后压回。

    两个子表达式的横线互不相交，所以合并时方案数直接相乘；
    整体方案 = 两边各自全部方案之积，再按运算规则拆成 0/1 两份。
    """
    b0, b1 = opds.pop()
    a0, a1 = opds.pop()
    whole = (a0 + a1) * (b0 + b1) % MOD   # 合并后的全部填法
    if ops.pop() == '*':                   # ×(AND)：两边都是 1 才得 1
        one = a1 * b1 % MOD
        opds.append(((whole - one) % MOD, one))
    else:                                  # ⊕(OR)：两边都是 0 才得 0
        zero = a0 * b0 % MOD
        opds.append((zero, (whole - zero) % MOD))


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    length = int(next(data))  # 第 1 个 token L：运算符与括号个数，横线都夹在它们之间
    s = next(data).decode()   # 第 2 个 token：只剩 + * ( ) 的半成品表达式

    opds: list[tuple[int, int]] = []   # 操作数栈：(该子表达式为 0 的方案数, 为 1 的方案数)
    ops: list[str] = []                # 运算符栈
    expect = True                      # 当前位置该出现操作数（横线或左括号）

    for c in s:
        # 期待操作数却直接遇到运算符 → 运算符前面藏了一条横线
        if expect and c != '(':
            opds.append((1, 1))        # 单条横线取 0、取 1 各 1 种填法
            expect = False
        if c in '+*':
            # 栈顶运算符不比当前低级（× 先于 ⊕、同级从左到右）就先弹出来算
            while ops and ops[-1] != '(' and PREC[ops[-1]] >= PREC[c]:
                reduce_top(opds, ops)
            ops.append(c)
            expect = True              # 运算符后面必然跟一个操作数
        elif c == '(':
            ops.append(c)              # 左括号入栈，等里面的表达式算完再弹
        elif c == ')':
            while ops[-1] != '(':
                reduce_top(opds, ops)
            ops.pop()                  # 去掉左括号，整个括号体作为一个操作数
            expect = False

    if expect:                         # 表达式以横线收尾
        opds.append((1, 1))
    while ops:
        reduce_top(opds, ops)

    print(opds[0][0])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 14:43
 * update_at: 2026-10-06 14:43
 */

// 按题面真值表：+ 是逻辑或（同为 0 才得 0），* 是逻辑与（同为 1 才得 1）。
// 对每个子表达式记录 (c0, c1)：使它取 0 / 取 1 的横线填法数，叶子横线是 (1,1)。
// 用调度场双栈一遍扫描：按优先级弹运算符合并，O(L) 求出整个表达式取 0 的方案数。

#include <cstdio>
#include <string>
#include <vector>

typedef long long ll;

const ll MOD = 10007;

// 合并结果的结构：c[0] 是子表达式取 0 的填法数，c[1] 是取 1 的填法数
struct Node {
    ll c0;
    ll c1;
};

std::string expr;              // 输入的运算符与括号串
std::vector<Node> nums;        // 操作数栈：每个元素是一个子表达式的 (c0, c1)
std::vector<char> ops;         // 运算符栈：保存 + * ( 三种字符
bool expect_num;               // 当前位置是否该出现操作数（横线是隐式的，靠它补上）

// 弹出一个运算符，合并操作数栈顶的两个子表达式
void reduce_top() {
    Node b = nums.back(); nums.pop_back();
    Node a = nums.back(); nums.pop_back();
    ll whole = (a.c0 + a.c1) * (b.c0 + b.c1) % MOD; // 两侧横线互不相交，方案数相乘
    Node res;
    if (ops.back() == '*') {
        // 与：结果为 1 当且仅当两边都是 1
        res.c1 = a.c1 * b.c1 % MOD;
        res.c0 = (whole - res.c1 + MOD) % MOD;
    } else {
        // 或：结果为 0 当且仅当两边都是 0
        res.c0 = a.c0 * b.c0 % MOD;
        res.c1 = (whole - res.c0 + MOD) % MOD;
    }
    nums.push_back(res);
    ops.pop_back();
}

// 判断栈顶运算符优先级是否不低于当前运算符（* 高于 +，同级从左到右）
bool should_reduce(char cur) {
    if (ops.back() == '(') return false;
    if (ops.back() == '*' && cur == '+') return true;
    return ops.back() == cur; // 同级先算左边的
}

int main() {
    ll len;
    scanf("%lld", &len);
    (void)len;
    // 表达式串最长 1e5，用静态大缓冲读入
    static char big[100005];
    scanf("%s", big);
    expr = big;

    expect_num = true;
    for (ll i = 0; i < (ll)expr.size(); i++) {
        char ch = expr[i];
        if (ch == '(') {
            // 左括号直接压栈，括号内自成一层
            ops.push_back('(');
            expect_num = true;
        } else if (ch == ')') {
            // 遇右括号：先补上括号内最后一条横线，再弹到左括号为止
            if (expect_num) nums.push_back(Node{1, 1});
            while (ops.back() != '(') reduce_top();
            ops.pop_back(); // 弹掉 '('，括号内结果收成一个操作数
            expect_num = false;
        } else {
            // 是运算符：若该出现操作数，说明前面藏着一条横线
            if (expect_num) nums.push_back(Node{1, 1});
            // 按优先级先合并栈顶可以算完的
            while (!ops.empty() && should_reduce(ch)) reduce_top();
            ops.push_back(ch);
            expect_num = true;
        }
    }
    // 表达式以横线收尾（如以运算符结束）时补最后一条横线
    if (expect_num) nums.push_back(Node{1, 1});
    // 弹空运算符栈，最终操作数栈里只剩整个表达式的 (c0, c1)
    while (!ops.empty()) reduce_top();
    printf("%lld\n", nums.back().c0);
    return 0;
}

目录

题目描述

思路

参考代码