这是一份标准的 AC 代码。

解题核心思路

1. 建树（表达式树）： 为了正确统计“短路”次数，我们需要模拟表达式的计算过程。由于逻辑运算具有优先级且可能短路（跳过右侧部分的计算），构建一棵表达式树是最清晰的方法。树的结构天然反映了运算的嵌套关系。
   • 我们使用双栈法（一个存节点编号，一个存操作符）来构建树，这类似于中缀转后缀的逻辑，但在操作时直接生成树节点。
   • 优先级：& (2) > | (1) > ( (0)。
2. DFS 求值与统计： 建树完成后，从根节点开始递归求值。
   • 与运算 (&)：先算左子树。如果左子树为 0，则触发短路（cnt_and++），直接返回 0，不再递归右子树。
   • 或运算 (|)：先算左子树。如果左子树为 1，则触发短路（cnt_or++），直接返回 1，不再递归右子树。
   • 如果没触发短路，则继续递归计算右子树。

标准 C++ 代码

#include <iostream>
#include <string>
#include <stack>

using namespace std;

const int MAXN = 1000005;

// 定义树的节点结构
struct Node {
    int val;      // 若是叶子节点，存储数值 0 或 1
    int op;       // 节点类型：0=数值, 1=|, 2=&
    int left, right; // 左右子节点编号
} tree[MAXN];

int node_cnt = 0; // 节点计数器
int ans_and = 0;  // & 短路次数
int ans_or = 0;   // | 短路次数

// 获取运算符优先级
int get_priority(char c) {
    if (c == '&') return 2;
    if (c == '|') return 1;
    return 0; // 左括号优先级最低，用于阻断弹出
}

// 创建一个新的运算节点，连接栈顶的两个子树
void create_op_node(char c, stack<int>& nodes) {
    int r = nodes.top(); nodes.pop(); // 栈顶是右操作数
    int l = nodes.top(); nodes.pop(); // 次顶是左操作数
    
    node_cnt++;
    tree[node_cnt].op = (c == '&' ? 2 : 1);
    tree[node_cnt].left = l;
    tree[node_cnt].right = r;
    
    nodes.push(node_cnt); // 新节点入栈
}

// 深度优先搜索进行求值和短路统计
int dfs(int u) {
    // 如果是叶子节点（数值），直接返回
    if (tree[u].op == 0) {
        return tree[u].val;
    }

    // 先计算左子树
    int l_val = dfs(tree[u].left);

    if (tree[u].op == 2) { // 当前是 & 运算
        if (l_val == 0) {
            // 触发 & 短路：左边为 0，右边无需计算
            ans_and++;
            return 0;
        } else {
            // 未短路，继续计算右子树
            return dfs(tree[u].right);
        }
    } 
    else { // 当前是 | 运算
        if (l_val == 1) {
            // 触发 | 短路：左边为 1，右边无需计算
            ans_or++;
            return 1;
        } else {
            // 未短路，继续计算右子树
            return dfs(tree[u].right);
        }
    }
}

int main() {
    // 优化输入输出
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin >> s;

    stack<int> nodes;  // 存储树节点编号的栈
    stack<char> ops;   // 存储运算符的栈

    // 1. 解析字符串并建树 (Shunting-yard 算法变种)
    for (int i = 0; i < s.size(); i++) {
        char c = s[i];

        if (c == '0' || c == '1') {
            // 遇到数字，创建叶子节点
            node_cnt++;
            tree[node_cnt].op = 0;
            tree[node_cnt].val = c - '0';
            nodes.push(node_cnt);
        } 
        else if (c == '(') {
            ops.push(c);
        } 
        else if (c == ')') {
            // 遇到右括号，弹出运算符直到左括号
            while (!ops.empty() && ops.top() != '(') {
                create_op_node(ops.top(), nodes);
                ops.pop();
            }
            if (!ops.empty()) ops.pop(); // 弹出 '('
        } 
        else if (c == '&' || c == '|') {
            // 遇到运算符，维护单调栈：弹出优先级 >= 当前运算符的栈顶元素
            // 这里的 >= 保证了同级运算符从左向右结合
            while (!ops.empty() && get_priority(ops.top()) >= get_priority(c)) {
                create_op_node(ops.top(), nodes);
                ops.pop();
            }
            ops.push(c);
        }
    }

    // 处理栈中剩余的运算符
    while (!ops.empty()) {
        create_op_node(ops.top(), nodes);
        ops.pop();
    }

    // 建树完成后，nodes 栈中剩下的唯一元素就是根节点
    int root = nodes.top();

    // 2. DFS 计算结果与统计短路
    int result = dfs(root);

    // 3. 输出
    cout << result << "\n";
    cout << ans_and << " " << ans_or << "\n";

    return 0;
}

你好！我是你的OI教练。这道题是 CSP-J 2022 的第四题，考察的是表达式求值与树形结构的结合。

这道题的难点不在于计算最终结果（0还是1），而在于正确统计“短路”的次数。因为短路会跳过后面一部分的计算，而那部分里面如果还有原本会触发短路的操作，是不应该被统计进去的。

为了解决这个问题，普通的栈式求值（边解析边计算）会非常麻烦，因为很难判断“跳过”的范围。最稳妥的方法是构建表达式树（语法树）。

下面我给你提供核心的解题思路提示：

1. 核心思路：表达式树 (Expression Tree)

我们平时做数学表达式求值（如 1+2*3），可以直接用两个栈算出结果。但这道题要求统计短路，这意味着我们需要知道表达式的层级结构。

比如表达式 1 | (0 & 1)：

• 如果画成一棵树，根节点是 |。
• 左子树是 1。
• 右子树是 &，其下有两个子节点 0 和 1。

当我们在根节点 | 处计算时，发现左边是 1，触发短路。此时我们就不需要进入右子树了。一旦不进入右子树，右子树里的 & 运算自然就不会被执行，也就不会被统计。 这完美契合题目的要求。

2. 第一步：建树（使用双栈法）

我们需要把输入的字符串转化为一棵树。可以使用经典的中缀表达式转后缀表达式的思路（类似“调度场算法”），但在转换过程中直接建树。

你需要准备两个栈：

1. 数值/节点栈：存储树的节点编号（int）。
2. 符号栈：存储运算符（char）。

建树流程提示：

• 遇到 数字（0/1）：新建一个叶子节点，将该节点的编号压入节点栈。
• 遇到 左括号 (：直接压入符号栈。
• 遇到 右括号 )：不断弹出符号栈顶的运算符，直到遇到左括号。
  • 弹出一个运算符时做什么？ 从节点栈弹出两个节点（分别为右孩子、左孩子），新建一个父节点（该运算符），将父节点编号压回节点栈。
• 遇到 运算符 & 或 |：
  • 比较当前运算符与符号栈顶运算符的优先级。
  • 规则：& 的优先级高于 |。同级运算从左到右（即左结合）。
  • 如果 栈顶优先级 >= 当前优先级，则弹出栈顶运算符并建树（同上），直到栈空或栈顶优先级更低。
  • 最后将当前运算符压入符号栈。

处理完字符串后，如果符号栈不空，继续弹出建树。最后节点栈里剩下的唯一一个节点就是树根。

3. 第二步：递归求值与统计（DFS）

树建好后，所有的逻辑关系就已经固定了。我们只需要从根节点开始写一个递归函数 dfs(u) 来求值。

递归逻辑提示： 假设当前节点是 u：

1. 如果是叶子节点（存的是数字）：直接返回该数字。
2. 如果是 & 节点：
   • 先递归计算左子树：val_left = dfs(u.left)。
   • 短路判断：如果 val_left == 0：
     • 发生了 & 短路。计数器 cnt_and 加 1。
     • 直接返回 0（千万不要去递归右子树！）。
   • 否则（val_left == 1）：
     • 递归计算右子树：val_right = dfs(u.right)。
     • 返回 val_right。
3. 如果是 | 节点：
   • 先递归计算左子树：val_left = dfs(u.left)。
   • 短路判断：如果 val_left == 1：
     • 发生了 | 短路。计数器 cnt_or 加 1。
     • 直接返回 1（千万不要去递归右子树！）。
   • 否则（val_left == 0）：
     • 递归计算右子树：val_right = dfs(u.right)。
     • 返回 val_right。

4. 数据结构与细节

• 数组模拟树： 由于字符串长度 $10^6$，可以用结构体数组来存树：

  struct Node {
      int l, r; // 左右孩子编号
      char op;  // 存储 '&', '|' 或 'N' (Number，代表叶子)
      int val;  // 如果是叶子，存 0 或 1
  } tree[1000005];
  

• 优先级处理：可以写个小函数 priority(char c)，& 返回 2，| 返回 1，( 返回 0。
• 输入读取：直接读入整个字符串 cin >> s; 即可。

按照这个思路，先建树，再 DFS，就能完美解决这道题，且时间复杂度是 $O(|s|)$，可以通过所有测试点。加油！