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

Chihaya_Yuka · 2025-01-12 18:31:10 · 题解

Tips：本人 AC 这道题目的代码属于图灵完备的编译器。

题目回顾

“逻辑表达式”题目要求我们计算一个给定的逻辑表达式的值，并统计计算过程中出现的“短路”次数。逻辑表达式由 0、1、& (与)、| (或) 和括号组成。需要注意的是，& 的优先级高于 |，同级运算从左到右，括号优先。

这道题看起来好难啊。

那我们写一个编译器吧。

短路是指在 a & b 中，若 a 为 0 则整个表达式值为 0，不再计算 b；以及在 a | b 中，若 a 为 1 则整个表达式值为 1，不再计算 b。

解题思路

这道题的核心在于如何正确地解析表达式，并按照规定的运算顺序进行计算。直接模拟计算过程较为繁琐，容易出错。而使用 AST 可以将表达式的结构清晰地表示出来，方便我们进行计算和统计。

什么是抽象语法树 (AST)

抽象语法树 (Abstract Syntax Tree, AST) 是源代码语法结构的一种树状表示形式。它以树状的形式表现编程语言的语法结构，每个节点都代表源代码中的一个语法结构。在逻辑表达式中，我们可以用 AST 来表示运算的优先级和嵌套关系。

例如，表达式 0&(1|0)|(1|1|1&0) 的 AST 可以大致表示为：

      |
     / \
    &   |
   / \ / \
  0   | 1   |
     / \   / \
    1   0 1   &
           / \
          1   0

代码解析

我们将分解代码的各个部分，并解释其功能以及与 AST 和编译原理概念的联系。

1. 头文件和全局变量

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

using namespace std;

// 定义全局变量统计短路次数
int and_short_circuit = 0;
int or_short_circuit = 0;

iostream: 用于输入输出。
string: 用于处理字符串。
stack: 用于实现栈数据结构，在构建 AST 的过程中存储操作符和节点。
vector: 用于存储后缀表达式。
and_short_circuit 和 or_short_circuit: 全局变量，分别用于统计 & 和 | 的短路次数。

2. AST 节点定义

// 定义 AST 节点类型
enum class NodeType {
    VALUE,
    AND,
    OR
};

// 定义 AST 节点结构
struct Node {
    NodeType type;
    int value; // 仅当 type 为 VALUE 时有效
    Node* left;
    Node* right;

    Node(NodeType t, int v = 0, Node* l = nullptr, Node* r = nullptr) : type(t), value(v), left(l), right(r) {}
};

NodeType: 枚举类型，定义了 AST 节点的三种类型：VALUE (值节点，表示 0 或 1)、AND (与节点) 和 OR (或节点)。
Node: 结构体，表示 AST 的节点。
- type: 节点类型。
- value: 当节点类型为 VALUE 时，存储 0 或 1。
- left 和 right: 指向左右子节点的指针。

3. 中缀表达式转后缀表达式 (infixToPostfix)

vector<char> infixToPostfix(const string& infix) {
    // ... 代码 ...
}

这一部分实现了经典的调度场算法，将中缀表达式转换为后缀表达式。后缀表达式也称为逆波兰表达式，它将操作符放在操作数之后，更便于计算机处理。

原理： 使用一个栈来存储操作符，遍历中缀表达式：
- 遇到数字：直接添加到后缀表达式。
- 遇到左括号：压入栈。
- 遇到右括号：弹出栈中操作符并添加到后缀表达式，直到遇到左括号。
- 遇到操作符：
  - 如果栈顶操作符优先级高于或等于当前操作符，则弹出栈顶操作符并添加到后缀表达式，直到栈顶操作符优先级低于当前操作符或栈为空或栈顶为左括号。
  - 将当前操作符压入栈。
- 遍历结束后，将栈中剩余的操作符弹出并添加到后缀表达式。
与编译原理的联系： 这是词法分析和语法分析的一部分。中缀表达式是人类可读的形式，而后缀表达式更接近于机器指令的形式，便于后续的 AST 构建。

4. 构建 AST (buildAST)

Node* buildAST(const vector<char>& postfix) {
    // ... 代码 ...
}

此函数根据后缀表达式构建 AST。

原理： 使用一个栈来存储 AST 节点，遍历后缀表达式：
- 遇到数字：创建一个 VALUE 节点，并将其压入栈。
- 遇到操作符：
  - 弹出栈顶的两个节点作为右子节点和左子节点。
  - 创建一个新的 AND 或 OR 节点，将左右子节点连接到该节点。
  - 将新创建的节点压入栈。
- 遍历结束后，栈中剩下的唯一节点即为 AST 的根节点。
与编译原理的联系： 这是语法分析的进一步体现，将线性的后缀表达式转换为树状的 AST，体现了表达式的语法结构。

5. 计算 AST 的值并统计短路 (evaluateAST)

int evaluateAST(Node* node, bool is_short_circuit_parent = false) {
    // ... 代码 ...
}

此函数递归地计算 AST 的值，并统计短路次数。

原理： 使用递归的方式遍历 AST：
- VALUE 节点：直接返回其值。
- AND 节点：
  - 先计算左子节点的值。
  - 如果左子节点的值为 0，则发生短路，根据is_short_circuit_parent判断是否是嵌套短路，如果不是则更新 and_short_circuit，直接返回 0。
  - 否则，计算右子节点的值，并返回左右子节点值的逻辑与。
- OR 节点：
  - 先计算左子节点的值。
  - 如果左子节点的值为 1，则发生短路，根据is_short_circuit_parent判断是否是嵌套短路，如果不是则更新 or_short_circuit，直接返回 1。
  - 否则，计算右子节点的值，并返回左右子节点值的逻辑或。
is_short_circuit_parent: 这个参数用于标记当前节点是否处于一个已经被短路的父节点中。如果是，则当前节点的短路不应该被重复统计。

6. 释放 AST (deleteAST)

void deleteAST(Node* node) {
    // ... 代码 ...
}

此函数递归地释放 AST 占用的内存，防止内存泄漏。

7. 主函数 (main)

int main() {
    string infix;
    cin >> infix;

    vector<char> postfix = infixToPostfix(infix);
    Node* root = buildAST(postfix);

    int result = evaluateAST(root);

    cout << result << endl;
    cout << and_short_circuit << " " << or_short_circuit << endl;

    deleteAST(root);

    return 0;
}

主函数负责读取输入，调用各个函数完成表达式的转换、AST 的构建、计算和结果输出，以及最后的 AST 释放。

评测记录：https://www.luogu.com.cn/record/197925479

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

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