题面解释:

在这道题中，一线工程师需要对网络进行健康检查，通过解析布尔表达式来判断网络状态。输入包括两个整数 n 和 m，分别表示布尔表达式的数量和采集数据的数量。接下来是 n 行的布尔表达式，每个表达式使用 AND、OR、() 和 = 等符号来描述条件。然后是 m 行的数据，每行由一个字段名和对应的值组成。根据提供的条件，如果数据满足表达式，则网络健康（输出 0），否则不健康（输出 1）。

思路

对于回答的字符串，将里面的key+value替换成1或0，得到一个只包含1，0,&,|,的字符串也就是转换成表达式求值问题模拟即可$\\$

题解

在本题中，工程师需要通过给定的布尔表达式来判断网络的健康状态。表达式中包含多个条件，每个条件由字段名和相应的值组成。我们需要根据提供的字段值，计算布尔表达式的结果，并输出网络的健康状态。网络健康被表示为 0，不健康则表示为 1。

输入包含以下几个部分：

1. 两个整数 n 和 m，分别表示布尔表达式的数量和采集的数据条数。
2. n 行布尔表达式，每个表达式使用 AND 和 OR 逻辑运算符，以及 = 运算符。
3. m 行字段名和对应值的数据。

我们的目标是将布尔表达式中的条件替换为 0 或 1，然后评估表达式的值。

时间复杂度分析：

该程序的时间复杂度为 ( O(n x L + m) )，其中 ( n ) 是布尔表达式的数量，( L ) 是表达式的平均长度，( m ) 是采集的数据数量。

代码如下

python

# 读取输入的两个整数，分别表示布尔表达式的数量和替换的数据数量
num_expressions, num_replacements = list(map(int, input().split()))

# 创建一个空列表，用于存储布尔表达式
expressions = []
# 读取每个布尔表达式并存储到列表中
for _ in range(num_expressions):
    expressions.append(input())

# 创建一个字典，用于存储替换的字段名及其对应的值
replacements = {}
# 读取每个字段名和对应的值，并将其存储到字典中
for _ in range(num_replacements):
    key, value = input().split()
    replacements[key] = str(value)  # 确保值被存储为字符串

# 遍历每个布尔表达式
for expression in expressions:
    # 将 "=" 替换为 "==" 以符合 Python 的比较语法
    expression = expression.replace("=", "==")
    # 将逻辑运算符 "AND" 替换为 Python 的 "and"
    expression = expression.replace("AND", "and")
    # 将逻辑运算符 "OR" 替换为 Python 的 "or"
    expression = expression.replace("OR", "or")
    
    # 使用 eval 函数计算表达式的结果
    # globals() 用于提供全局命名空间，replacements 提供变量的值
    result = eval(expression, globals(), replacements)
    
    # 根据结果输出 0（健康）或 1（不健康）
    print(0 if result else 1)

cpp

#include <bits/stdc++.h>
using namespace std;

// 存储布尔表达式
string ss[100];
// 存储字段名和对应值的映射
map<pair<string, string>, int> mp;
// 用于读取输入的临时变量
string a, w;
char dyh = '\''; // 表示单引号字符
stack<int> num; // 数值栈，用于存储布尔值
stack<char> op; // 操作符栈，用于存储操作符

// 操作符优先级映射
unordered_map<char, int> h{ {'&', 2}, {'|', 1} };

// 评估栈顶操作
void eval() {
    int a = num.top(); // 取出栈顶的第一个操作数
    num.pop(); // 弹出栈顶元素
    
    int b = num.top(); // 取出栈顶的第二个操作数
    num.pop(); // 弹出栈顶元素
    
    char p = op.top(); // 取出栈顶操作符
    op.pop(); // 弹出栈顶操作符
    
    int r = 0; // 结果初始化

    // 根据操作符计算结果
    if (p == '&') {
        r = (b == 1 && a == 1) ? 1 : 0; // AND 操作
    }
    if (p == '|') {
        r = (b == 1 || a == 1) ? 1 : 0; // OR 操作
    }
    num.push(r); // 将结果推入数值栈
}

signed main() {
    int n, m;
    cin >> n >> m; // 读取表达式数量和数据数量
    getline(cin, a); // 读取换行符

    // 读取布尔表达式
    for (int i = 1; i <= n; i++) {
        getline(cin, a);
        string b = "";
        // 去除表达式中的空格
        for (char c : a) {
            if (c != ' ') {
                b += c;
            }
        }
        ss[i] = b; // 存储处理后的表达式
    }

    // 读取数据并映射
    for (int i = 1; i <= m; i++) {
        cin >> a >> w;
        mp[{a, w}] = 1; // 将字段名和对应值的映射设为1
    }

    // 处理每个布尔表达式
    for (int j = 1; j <= n; j++) {
        string s = ss[j];
        for (int i = 0; i < s.size(); i++) {
            // 如果是字段赋值
            if (s[i] != '(' && s[i] != ')' && !(s[i] >= 'A' && s[i] <= 'Z')) {
                string s1 = "", s2 = "";
                int k = i;
                // 读取字段名
                while (s[k] != '=') {
                    s1 += s[k];
                    if (k == int(s.size() - 1)) {
                        break;
                    }
                    k++;
                }
                k += 2; // 跳过 '=' 和空格
                // 读取字段值
                while (s[k] != dyh) {
                    s2 += s[k];
                    if (k == int(s.size() - 1)) {
                        break;
                    }
                    k++;
                }
                i = k; // 更新索引
                num.push(mp[{s1, s2}]); // 将对应值推入数值栈
            }
            // 处理 AND 操作
            else if (s[i] == 'A') {
                while (op.size() && h[op.top()] >= h['&'])
                    eval(); // 计算优先级高的操作
                op.push('&'); // 将操作符压入栈
                i += 2; // 跳过 'ND'
            }
            // 处理 OR 操作
            else if (s[i] == 'O') {
                while (op.size() && h[op.top()] >= h['|'])
                    eval(); // 计算优先级高的操作
                op.push('|'); // 将操作符压入栈
                i += 1; // 跳过 'R'
            }
            // 处理左括号
            else if (s[i] == '(') {
                op.push(s[i]); // 将左括号压入栈
            }
            // 处理右括号
            else if (s[i] == ')') {
                while (op.top() != '(')
                    eval(); // 计算直到遇到左括号
                op.pop(); // 弹出左括号
            }
        }
        // 处理完表达式后评估剩余操作
        while (op.size()) eval();
        cout << (num.top() ^ 1) << '\n'; // 输出健康状态（取反）
    }
    return 0;
}

Java

import java.util.*;

public class Main {
    // 用于存储布尔表达式的列表
    static List<String> myA;
    // 用于存储输入的布尔表达式
    static String[] express;
    // 用于存储字段名及其对应值的映射
    static Map<String, String> kV = new HashMap<>();
    // 表达式和数据的数量
    static int n = 0, m = 0;
    // 标记是否处理了括号
    static boolean flag = false;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 读取布尔表达式数量
        m = sc.nextInt(); // 读取替换数据数量
        sc.nextLine(); // 读取换行符
        express = new String[n]; // 初始化布尔表达式数组
        String temp; // 临时变量存储输入
        String[] tempS; // 临时数组用于存储替换数据

        // 数据初次加工：读取布尔表达式并进行格式化处理
        for (int i = 0; i < n; i++) {
            temp = sc.nextLine()
                        .replaceAll("'+", " ") // 去除多余的单引号
                        .replaceAll("\\(", "( ") // 在左括号后加空格
                        .replaceAll("\\)", " )") // 在右括号前加空格
                        .replaceAll("=", " = ") // 在等号两边加空格
                        .trim(); // 去除首尾空格
            express[i] = temp; // 存储格式化后的表达式
        }

        // 读取替换数据并存入映射
        for (int i = 0; i < m; i++) {
            tempS = sc.nextLine().split(" "); // 读取字段名和对应值
            kV.put(tempS[0], tempS[1]); // 将字段名和值存入映射
        }

        // 遍历每个布尔表达式进行计算
        for (String s : express) {
            flag = false; // 重置标记
            myA = new ArrayList<>(Arrays.asList(s.split("\\s+"))); // 将表达式按空格拆分为列表
            quEqual(); // 处理等号，替换字段值
            // 处理 AND 和 OR 运算，直到只剩一个结果
            while (myA.size() > 1) {
                if (flag) {
                    quAndOR(0, myA.size()); // 如果处理过括号，则直接处理 AND 和 OR
                } else {
                    quKAndOR(); // 处理括号
                }
            }

            // 根据结果输出网络健康状态
            if (myA.get(0).equals("1")) {
                System.out.println(0); // 健康
            } else {
                System.out.println(1); // 不健康
            }
        }
    }

    // 处理括号内的 AND 和 OR 运算
    private static void quKAndOR() {
        String temp; // 临时变量
        int z = 0, you = myA.size() + 1; // 左右括号的位置
        for (int i = myA.size() - 1; i >= 0; i--) {
            temp = myA.get(i);
            if (temp.equals(")")) {
                you = Math.min(you, i); // 右括号的位置
            }
            if (temp.equals("(")) {
                z = i; // 左括号的位置
                break;
            }
        }
        if (you == myA.size() + 1) {
            flag = true; // 如果没有括号，标记为 true
            you = myA.size(); // 设置右边界为当前大小
        } else {
            myA.remove(you); // 移除右括号
            myA.remove(z); // 移除左括号
            you--; // 更新右边界
        }
        quAndOR(z, you); // 处理括号内的运算
    }

    // 处理 AND 和 OR 运算
    private static void quAndOR(int z, int you) {
        String temp1, op, temp2; // 临时变量
        // 处理 AND 运算
        for (int i = z + 1; i < you - 1; i++) {
            op = myA.get(i);
            if (op.equals("AND")) {
                temp1 = myA.get(i - 1); // 左操作数
                temp2 = myA.get(i + 1); // 右操作数

                myA.remove(i + 1); // 移除右操作数
                myA.remove(i); // 移除 AND 运算符
                // 根据操作数计算结果
                if (temp1.equals("0") || temp2.equals("0")) {
                    op = "0"; // 只要有一个为 0，结果为 0
                } else {
                    op = "1"; // 都为 1，结果为 1
                }
                myA.set(i - 1, op); // 将结果放回到列表中
                i--; // 调整索引
                you -= 2; // 更新右边界
            }
        }
        // 处理 OR 运算
        for (int i = z + 1; i < you - 1; i++) {
            op = myA.get(i);
            if (op.equals("OR")) {
                temp1 = myA.get(i - 1);
                temp2 = myA.get(i + 1);

                myA.remove(i + 1);
                myA.remove(i);
                // 根据操作数计算结果
                if (temp1.equals("1") || temp2.equals("1")) {
                    op = "1"; // 只要有一个为 1，结果为 1
                } else {
                    op = "0"; // 都为 0，结果为 0
                }
                myA.set(i - 1, op);
                i--;
                you -= 2; // 更新右边界
            }
        }
    }

    // 判断是否为合法的变量名
    private static boolean zi(String temp) {
        if (temp.equals("=") || temp.equals("AND") || temp.equals("OR") || temp.equals("(") || temp.equals(")")) {
            return false; // 这些符号不算变量名
        }
        return true; // 合法变量名
    }

    // 替换字段值并去除等号
    private static void quEqual() {
        String temp1, op, temp2; // 临时变量
        // 进行替换操作
        for (int i = 0; i < myA.size(); i++) {
            temp1 = myA.get(i);
            if (kV.containsKey(temp1)) {
                myA.set(i, kV.get(temp1)); // 替换字段名为对应值
            }
        }
        // 去除等号并计算结果
        for (int j = 0; j < myA.size() - 2; j++) {
            temp1 = myA.get(j);
            op = myA.get(j + 1);
            temp2 = myA.get(j + 2);

            if (op.equals("=") && zi(temp1) && zi(temp2)) {
                // 如果是条件1 = 条件2
                myA.remove(j + 2); // 移除右操作数
                myA.remove(j + 1); // 移除等号
                // 根据条件比较结果
                if (temp1.equals(temp2)) {
                    myA.set(j, "1"); // 相等返回 1
                } else {
                    myA.set(j, "0"); // 不相等返回 0
                }
            }
        }
    }
}

题目内容

一线工程师每到重要节日需要对网络进行健康检查，在网络中对各个网元采集数据，判断当前网络是否健康。

因每个网元的判断条件以及采集的数据不同，现在需要你对网络采集到的数据，以及工程师提供的判断条件进行解析。判断条件为布尔表达式，保证合法，字段名不会与关键字冲突。

若采集数据符合条件，则认为网络健康，否则网络处于不健康状态。

输入描述

第一行有$2$个整数$nm$ 接下来有n行字符串$express$ 接下来$m$行，每行均有两个字符串，$key$和$value$ 备注: 表达式中仅会出现 $AND、OR、()、'、$空格、$=$、字段名、数据(单引号内)，给出的表达式一定是有效的，$AND$优先级高于$OR$ “$=$"左侧为字段名 “$=$"右侧为数据，类型为字符串 $0<n≤5$ $0<m≤10$

输出描述

返回表达式结果$:0,1$。 $0$表示健康，$1$表示不健康。

样例1

输入

2 2
error = '0' AND (name = 'NE40' OR name = 'NE20')
error = '1' AND (name = 'NE40' OR name = 'NE20')
name NE40
error 0

输出

0
1

说明

对于条件:$error='0'AND (name='NE40'OR name='NE20')$ 当$name$取值为$NE40$，$error$取值为$0$时，表达式计算结果为$true$,所以输出$0$，表示健康 对于条件:$error ='1' AND (name = 'NE40' OR name ='NE20')$ 当$name$取值为$NE40$，$error$取值为$0$时，表达式计算结果为$false$，所以输出$1$，表示不健康

样例2

输入

3 2
error = '1' AND (name = 'NE40' OR name ='NE20')
error = '2' AND (name = 'NE40' OR name ='NE20')
error = '3' AND (name = 'NE40' OR name ='NE20')
name NE40
error 3

输出

1
1
0

说明

对于条件:$error ='1' AND (name ='NE40' OR name ='NE20')$ 当$name$取值为$NE40$，$error$取值为$3$时，表达式计算结果为$false$，所以输出$1$，表示不健康 对于条件:$error ='2' AND (name = 'NE40' OR name = 'NE20')$ 当$name$取值为$NE40$，$error$取值为$3$时，表达式计算结果为$false$，所以输出$1$，表示不健康 对于条件:$error ='3' AND (name= 'NE40' OR name ='NE20')$ 当$name$取值为$NE40$，$error$取值为$3$时，表达式计算结果为$true$，所以输出$0$，表示健康