表达式递归求值模版

priority={"OR":1,"AND":2,"=":3}
def eval_(expression):
    n = len(expression)
    if n==3:
        return expression[0]==expression[2]
    levels=[0 for _ in range(n)]
    priorities=[0 for _ in range(n)]
    level=0
    for i, elem in enumerate(expression):
        if elem=="(":
            level+=1;
            levels[i] = level
        elif elem==")":
            levels[i] = level
            level-=1
        else:
            levels[i] = level
    onlyOneP=True
    for level in levels:
        if level==0:
            onlyOneP=False
            break
    if onlyOneP:
        return eval_(expression[1:-1])
    operator_idx=-1
    priority_cur=-1
    for i, elem in enumerate(expression):
        if levels[i]==0 and priority.get(elem, 0):
            if priority_cur==-1 or priority.get(elem)<priority_cur:
                priority_cur=priority.get(elem)
                operator_idx=i
    if expression[operator_idx] == "AND":
        return eval_(expression[:operator_idx]) and eval_(expression[operator_idx+1:])
    else:
        return eval_(expression[:operator_idx]) or eval_(expression[operator_idx+1:])

n,m=map(int, input().split())
expressions=[]
for i in range(n):
    expressions.append(input())
values={}
for i in range(m):
    key,value=input().split()
    values[key]=value
for i in range(n):
    expression=expressions[i]
    for k in values:
        expression=expression.replace(k,"'"+values[k]+"'")
    expression = expression.replace('(',' ( ')
    expression = expression.replace(')',' ) ')
    expression = expression.split()
    res=eval_(expression)
    if res:
        print(0)
    else:
        print(1)

主要思想：

1. 读数据

• 读取n,m 注意用nextInt()后记得用nextLine()读取换行符。
• 读取表达式，用数组存储，同时对数据进行初步加工：去除'，在(右边，)左边，=两边加空格，方便后续操作。
• 读取键值对，存储到HashMap里

2. 加工处理数据

粗加工

• 先把数据从字符串转为arrayList的集合里，以\\s+作为分隔。
• 对 键值进行替换
• 对 条件一 = 条件二进行替换 0,1

括号处理与AND,OR

• 从后往前定位(,),能保证定位到最内括号，并不会干扰原本的运算优先级。如果有括号，就定位，并删除，然后把括号里的进行计算合并。
• 如果没括号，直接就进行计算，按照AND优先级比OR优先级大，先处理AND,后处理OR。
• 最后集合里只剩余一个元素 0或者1

3. 打印结果

• 集合里的唯一一个元素 值为1，打印0；值为0，打印一。

不足

• 用的方法很笨，时间复杂度上也比较大，代码量也比较大 ，但是思路比较清晰。

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();//去除等号
            while (myA.size() > 1) {
                if(flag){
                    quAndOR(0,myA.size());
                }else{
                    quKAndOR();
                }
            }

            if (myA.get(0).equals("1")) {
                System.out.println(0);
            } else {
                System.out.println(1);
            }
        }
    }
    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;//没有左右括号
            //可以进行正常的，并先处理AND后处理OR
            you = myA.size();
        } else {
            myA.remove(you);
            myA.remove(z);
            you--;
        }
        quAndOR(z,you);
    }
    private static void quAndOR(int z,int you){
        String temp1, op, temp2;
        for (int i = z+1; i < you - 1; i++) {
            op = myA.get(i);
            if (op.equals("AND")) {
                //   i-1  i  i+1
                temp1 = myA.get(i - 1);
                temp2 = myA.get(i + 1);

                myA.remove(i + 1);
                myA.remove(i);
                if (temp1.equals("0") || temp2.equals("0")) {
                    op = "0";
                } else {
                    op = "1";
                }
                myA.set(i - 1, op);
                i--;
                you -= 2;
            }
        }
        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";
                } else {
                    op = "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");
                } else {
                    myA.set(j, "0");
                }
            }
        }
    }
}

eval 或者 exec

n, m = map(int, input().split())

ls = []
for _ in range(n):
    ls.append(input().replace('AND', 'and').replace('OR', 'or').replace('=', '=='))

dc = {}
for _ in range(m):
    key, value = input().split()
    dc[key] = value

for a in ls:
    result = eval(a, dc)
    print(0 if result else 1)

n, m = map(int, input().split())

ls = list()
for _ in range(n):
    ls.append(input().replace('AND', 'and').replace('OR', 'or').replace('=', '=='))

for _ in range(m):
    exec(input().replace(' ', ' = "')+'"')

for a in ls:
    print(0 if eval(a) else 1)

题面解释:

在这道题中，一线工程师需要对网络进行健康检查，通过解析布尔表达式来判断网络状态。输入包括两个整数 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
                }
            }
        }
    }
}