问题 F: 真值表(Ⅰ)

题目描述

给定一个逻辑表达式，其中包含 n 个变量（变量用字母表示，不区分大小写），求其真值表。

真值表是指对于逻辑表达式中的每个变量，分别列出它们可能的取值组合，并计算出整个表达式的值。

例如，对于逻辑表达式 (A and B) or (not A and C)，其真值表如下：

| A | B | C | (A and B) or (not A and C) |
|:-:|:-:|:-:|:------------------------:|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |

输入格式

输入文件首行包含一个整数 n，表示变量的个数。

第二行包含一个字符串，表示逻辑表达式。表达式中可以包含括号、与、或、非四种逻辑运算符，变量用任意大小写字母表示。

输出格式

输出文件共 n+1 行，第一行为变量名，第二行为变量的所有可能取值（0 或 1），后面 n 行为每一行的真值表。

变量名和真值表之间用一个空格隔开，每一行的末尾不要有多余空格。

变量名按字母序排列，如果有多个变量名相同的变量，则按照它们在表达式中第一次出现的顺序排列。

变量的所有取值组合按照二进制数的顺序排列，例如，对于 3 个变量，其取值组合的顺序为 000, 001, 010, 011, 100, 101, 110, 111。

输入样例

3
(A and B) or (not A and C)

输出样例

A B C
0 0 0 1 1 0 0 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

算法1

回溯算法

递归地枚举每个变量的取值，直到所有变量都被赋值。在枚举的过程中，根据逻辑表达式的运算规则计算表达式的值，最后将变量名、变量取值和表达式的值输出即可。

时间复杂度

设变量个数为 n，每个变量有两种取值，因此总共有 2^n 种取值组合。对于每种取值组合，需要 O(n) 的时间计算表达式的值。因此总时间复杂度为 O(n * 2^n)。

空间复杂度

递归调用的深度为 n，因此空间复杂度为 O(n)。

C++ 代码

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

// 变量名和变量取值
vector<pair<string, int>> variables;

// 变量名和变量的下标
map<string, int> variable_index;

// 逻辑表达式
string expression;

// 计算逻辑表达式的值
bool evaluate(const vector<int>& values) {
    vector<int> stack;

    for (char c : expression) {
        if (c == ' ') {
            continue;
        } else if (c == '(') {
            stack.push_back(-1);
        } else if (c == ')') {
            int op = stack.back(); stack.pop_back();
            int v = 1;
            while (op != -1) {
                v = v && op;
                op = stack.back(); stack.pop_back();
            }
            stack.push_back(v);
        } else if (c == 'and') {
            stack.push_back(-2);
        } else if (c == 'or') {
            stack.push_back(-3);
        } else if (c == 'not') {
            stack.push_back(-4);
        } else {
            int index = variable_index[string(1, c)];
            stack.push_back(values[index]);
        }

        while (stack.size() >= 3 && stack[stack.size() - 2] < 0) {
            int op = stack[stack.size() - 2];
            int op2 = stack.back(); stack.pop_back();
            int op1 = stack.back(); stack.pop_back();
            int v;
            if (op == -2) {
                v = op1 && op2;
            } else if (op == -3) {
                v = op1 || op2;
            } else if (op == -4) {
                v = !op2;
            }
            stack.push_back(v);
        }
    }

    return stack.back();
}

// 递归地枚举每个变量的取值
void dfs(int depth, vector<int>& values) {
    if (depth == (int)variables.size()) {
        cout << variables[0].first;
        for (int i = 1; i < (int)variables.size(); i++) {
            cout << " " << variables[i].first;
        }
        cout << endl;

        for (int i = 0; i < (int)variables.size(); i++) {
            cout << variables[i].second;
            for (int j = 1; j < (int)values.size(); j++) {
                cout << " " << ((j >> i) & 1);
            }
            cout << endl;
        }

        vector<int> vs;
        for (int i = 0; i < (int)variables.size(); i++) {
            vs.push_back(values[variable_index[variables[i].first]]);
        }
        cout << evaluate(vs) << endl;

        return;
    }

    values[depth] = 0;
    dfs(depth + 1, values);

    values[depth] = 1;
    dfs(depth + 1, values);
}

int main() {
    int n;
    cin >> n;
    getline(cin, expression);
    getline(cin, expression);

    expression += " ";  // 添加一个空格，方便解析

    // 解析变量名
    for (char c : expression) {
        if (isalpha(c)) {
            string name(1, c);
            if (variable_index.find(name) == variable_index.end()) {
                variable_index[name] = variables.size();
                variables.push_back({name, -1});
            }
        }
    }

    // 枚举变量取值
    vector<int> values(variables.size());
    dfs(0, values);

    return 0;
}

C++ 代码说明

- evaluate: 计算逻辑表达式的值，其中 stack 存储当前正在计算的表达式部分的值。遇到左括号时将 -1 入栈，遇到右括号时将栈顶的一组值计算出来，并将结果入栈。遇到 and、or、not 运算符时将其对应的标识符入栈。遇到变量时将其对应的值入栈。遇到运算符时从栈中弹出两个操作数，计算结果并入栈，直到栈中只剩下一个值，即为表达式的值。
- dfs: 递归地枚举每个变量的取值。当枚举完所有变量的取值后，输出变量名、变量取值和表达式的值。

C++ 代码中使用了以下数据结构和函数：

- vector: 可变长数组，用于存储变量名和变量取值，以及计算逻辑表达式时中间结果的栈。
- map: 存储变量名和变量在变量列表中的下标。
- string: 字符串，用于存储逻辑表达式。
- isalpha: 判断一个字符是否是字母。
- stoi: 将字符串转换为整数。

算法2

位运算

一种更简单的方法是使用位运算。对于每种取值组合，我们可以将其看作是一个 n 位二进制数，其中第 i 位为 0 表示第 i 个变量的取值为 0，为 1 则表示第 i 个变量的取值为 1。然后，我们可以使用位运算来计算逻辑表达式的值。

时间复杂度

设变量个数为 n，每个变量有两种取值，因此总共有 2^n 种取值组合。对于每种取值组合，需要 O(n) 的时间计算表达式的值。因此总时间复杂度为 O(n * 2^n)。

空间复杂度

由于使用了位运算，因此空间复杂度为 O(1)。

C++ 代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int n;
string expression;
vector<string> variable_names;
vector<int> variable_indices;

// 将整数转换为二进制字符串
string to_binary_string(int x) {
    string s;
    for (int i = n - 1; i >= 0; i--) {
        s += to_string((x >> i) & 1);
    }
    return s;
}

// 计算逻辑表达式的值
bool evaluate(const string& values) {
    vector<int> stack;

    for (char c : expression) {
        if (c == ' ') {
            continue;
        } else if (c == '(') {
            stack.push_back(-1);
        } else if (c == ')') {
            int op = stack.back(); stack.pop_back();
            int v = 1;
            while (op != -1) {
                v = v && op;
                op = stack.back(); stack.pop_back();
            }
            stack.push_back(v);
        } else if (c == 'and') {
            stack.push_back(-2);
        } else if (c == 'or') {
            stack.push_back(-3);
        } else if (c == 'not') {
            stack.push_back(-4);
        } else {
            int index = variable_indices[c - 'A'];
            stack.push_back(values[index] - '0');
        }

        while (stack.size() >= 3 && stack[stack.size() - 2] < 0) {
            int op = stack[stack.size() - 2];
            int op2 = stack.back(); stack.pop_back();
            int op1 = stack.back(); stack.pop_back();
            int v;
            if (op == -2) {
                v = op1 && op2;
            } else if (op == -3) {
                v = op1 || op2;
            } else if (op == -4) {
                v = !op2;
            }
            stack.push_back(v);
        }
    }

    return stack.back();
}

int main() {
    cin >> n;
    getline(cin, expression);
    getline(cin, expression);

    // 解析变量名
    for (char c : expression) {
        if (isalpha(c)) {
            string name(1, c);
            if (find(variable_names.begin(),