问题 F: 真值表(Ⅰ) 提交: 12021 解决: 1798 [状态] [提交] [命题人:cyh] 题目描述 同学们都学习过《离散数学》这门课程,知道真值表是用于逻辑中的一类数学用表,用来计算逻辑表示式在每一个逻辑变量取值组

合下的结果。现在给定一个逻辑表达式，请求出该表达式的真值表。

输入格式：
第一行包含一个正整数 n，表示逻辑变量的个数。

第二行包含一个长度不超过 n 的由大写字母和连接符 &、|、! 组成的字符串，表示逻辑表达式，其中 & 表示逻辑与，| 表示逻辑或，! 表示逻辑非。

输出格式：
输出该表达式的真值表，每行输出一个逻辑变量取值组合及对应的表达式取值，其中用 0 表示 False，用 1 表示 True。

每个变量取值组合占一行，按照变量从左到右的顺序输出，每个变量之间用空格隔开。

输入样例：
3
A&!B|C
输出样例：
0 0 1 1
0 1 1 0
1 0 0 1
1 1 0 1

相关问题

问题 G: 真值表(Ⅱ) 时间限制: 1 Sec 内存限制: 128 MB 提交: 4903 解决: 785 [状态] [提交] [命题人:cyh] 题目描述 第二阶段的任务是给定一个逻辑表达式，生成真值表。 输入 同子任务一。 输出 对于每一个逻辑表达式，输出其对应的真值表即可。相对于任务一，输出的最右边增加了一列，包含了表达式和它的各个值。具体见样例。 样例输入 Copy p p->q p||q 样例输出 Copy p p 1 1 0 0 p q p->q 1 1 1 1 0 0 0 1 1 0 0 1 p q p||q 1 1 1 1 0 1 0 1 1 0 0 0

以下是 Python3 的解法：

# 定义逻辑运算函数
def and_op(a, b):
    return a and b

def or_op(a, b):
    return a or b

def not_op(a):
    return not a

# 定义递归求解函数
def eval(node, values):
    if node.is_leaf():
        return values[node.data]
    else:
        left_value = eval(node.left, values)
        right_value = eval(node.right, values)
        op = node.data
        if op == '&':
            return and_op(left_value, right_value)
        elif op == '|':
            return or_op(left_value, right_value)
        elif op == '~':
            return not_op(left_value)
        else:
            raise ValueError('Invalid operator: {}'.format(op))

# 定义表达式解析函数
def parse_expr(expr):
    tokens = expr.split()
    stack = []
    for token in tokens:
        if token in {'&', '|', '~'}:
            right = stack.pop()
            left = stack.pop()
            node = Node(token, left, right)
            stack.append(node)
        else:
            node = Node(token)
            stack.append(node)
    return stack.pop()

# 定义主函数
if __name__ == '__main__':
    while True:
        try:
            expr = input()
        except:
            break
        # 解析表达式
        root = parse_expr(expr)
        # 输出表头
        var_names = sorted(root.get_vars())
        print(' '.join(var_names + [expr]))
        # 枚举所有可能的变量取值，并输出真值表
        for i in range(2 ** len(var_names)):
            values = {}
            for j, name in enumerate(var_names):
                values[name] = bool((i >> j) & 1)
            row = [str(int(values[name])) for name in var_names]
            row.append(str(int(eval(root, values))))
            print(' '.join(row))

其中，`Node` 类是用来表示逻辑表达式的节点的，具体实现可以参考以下代码：

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def is_leaf(self):
        return self.left is None and self.right is None

    def get_vars(self):
        if self.is_leaf():
            return {self.data}
        else:
            return self.left.get_vars() | self.right.get_vars()

在主函数中，先使用 `parse_expr` 函数解析输入的逻辑表达式，然后输出表头，再枚举所有可能的变量取值，计算表达式的值，并输出每一行的真值表。

问题 F: 真值表(Ⅰ) 时间限制: 1 Sec 内存限制: 128 MB 提交: 7689 解决: 1053 [状态] [提交] [命题人:cyh] 题目描述 同学们都学习过《离散数学》这门课程，知道真值表是用于逻辑中的一类数学用表，用来计算逻辑表示式在每一个逻辑变量取值组合下的值。在这里我们给定一个逻辑表达式，要求生成对应的真值表。提示一下，数据结构教材中介绍了数学表达式的处理算法，可以将其改造以适用于我们的项目。 项目分为三个子项目，第一部分为词法分析，即将逻辑表达式分隔为多个词(token)。下面给出两个例子。 例一： 逻辑表达式p^q中有p、^和q共三个词; 例二： 逻辑表达式p^(q^r)中有p、^、（、q、^、r和）共七个词。 逻辑联结词有五个，见下表，这些符号和教材上的有所不同，主要是为了方便。 否定 合取 析取 蕴涵 等值 ! ^ || -> <-> 引入括号，规定基本逻辑联接词优先顺序从高到低依次是：( )、!、∧、||、->、<->。 同一优先级，从左到右顺序进行。 输入

本题需要实现一个逻辑表达式的真值表生成器，需要实现以下几个步骤：

1. 词法分析：将逻辑表达式分解为多个词（token），包括变量、操作符和括号等。
2. 语法分析：根据操作符的优先级和结合性，将分解后的词组合成一个语法树。
3. 真值表生成：遍历所有可能的变量取值组合，计算得出每一行的结果，输出真值表。

以下是一个可能的实现思路：

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

using namespace std;

// 定义操作符的优先级和结合性
const map<char, pair<int, int>> op_precedence = {
    {'(', {0, 0}},
    {'!', {5, 1}},
    {'^', {4, 0}},
    {'|', {3, 0}},
    {'>', {2, 0}},
    {'=', {1, 0}}
};

// 定义每个变量的取值
map<char, bool> var_values;

// 词法分析：将表达式分解为多个词
vector<string> tokenize(const string& expr) {
    vector<string> tokens;
    string token;
    for (char ch : expr) {
        if (isspace(ch)) {  // 忽略空白字符
            continue;
        }
        if (isalpha(ch)) {  // 变量
            token += ch;
        } else if (op_precedence.count(ch)) {  // 操作符
            if (!token.empty()) {
                tokens.push_back(token);
                token.clear();
            }
            tokens.push_back(string(1, ch));
        } else {  // 非法字符
            cerr << "Error: invalid character '" << ch << "'\n";
            exit(1);
        }
    }
    if (!token.empty()) {
        tokens.push_back(token);
    }
    return tokens;
}

// 语法分析：将词组合成语法树
class Expression {
public:
    virtual bool evaluate() const = 0;
    virtual ~Expression() {}
};

class BinaryOp : public Expression {
protected:
    Expression* left_;
    Expression* right_;
public:
    BinaryOp(Expression* left, Expression* right)
        : left_(left), right_(right) {}
    virtual ~BinaryOp() {
        delete left_;
        delete right_;
    }
};

class UnaryOp : public Expression {
protected:
    Expression* child_;
public:
    UnaryOp(Expression* child) : child_(child) {}
    virtual ~UnaryOp() {
        delete child_;
    }
};

class Variable : public Expression {
    char name_;
public:
    Variable(char name) : name_(name) {}
    virtual bool evaluate() const {
        return var_values.at(name_);
    }
};

class Not : public UnaryOp {
public:
    Not(Expression* child) : UnaryOp(child) {}
    virtual bool evaluate() const {
        return !child_->evaluate();
    }
};

class And : public BinaryOp {
public:
    And(Expression* left, Expression* right)
        : BinaryOp(left, right) {}
    virtual bool evaluate() const {
        return left_->evaluate() && right_->evaluate();
    }
};

class Or : public BinaryOp {
public:
    Or(Expression* left, Expression* right)
        : BinaryOp(left, right) {}
    virtual bool evaluate() const {
        return left_->evaluate() || right_->evaluate();
    }
};

class Implies : public BinaryOp {
public:
    Implies(Expression* left, Expression* right)
        : BinaryOp(left, right) {}
    virtual bool evaluate() const {
        return !left_->evaluate() || right_->evaluate();
    }
};

class Iff : public BinaryOp {
public:
    Iff(Expression* left, Expression* right)
        : BinaryOp(left, right) {}
    virtual bool evaluate() const {
        return left_->evaluate() == right_->evaluate();
    }
};

Expression* parse_expression(const vector<string>& tokens, int& pos,
                             int min_precedence) {
    if (pos >= tokens.size()) {
        cerr << "Error: unexpected end of expression\n";
        exit(1);
    }
    string token = tokens[pos];
    if (isalpha(token[0])) {  // 变量
        ++pos;
        return new Variable(token[0]);
    } else if (token == "!") {  // 非
        ++pos;
        return new Not(parse_expression(tokens, pos, op_precedence.at('!').first));
    } else if (token == "(") {  // 左括号
        ++pos;
        Expression* expr = parse_expression(tokens, pos, op_precedence.at('(').first);
        if (pos >= tokens.size() || tokens[pos] != ")") {
            cerr << "Error: expected ')'\n";
            exit(1);
        }
        ++pos;
        return expr;
    } else {  // 二元操作符
        auto it = op_precedence.find(token[0]);
        if (it == op_precedence.end()) {
            cerr << "Error: invalid operator '" << token << "'\n";
            exit(1);
        }
        int precedence = it->second.first;
        if (precedence < min_precedence) {
            return nullptr;
        }
        ++pos;
        Expression* left = parse_expression(tokens, pos, precedence + it->second.second);
        while (pos < tokens.size()) {
            token = tokens[pos];
            if (op_precedence.find(token[0]) == op_precedence.end() ||
                op_precedence.at(token[0]).first != precedence) {
                break;
            }
            ++pos;
            Expression* right = parse_expression(tokens, pos, precedence + it->second.second);
            if (right == nullptr) {
                cerr << "Error: expected right operand for '" << token << "'\n";
                exit(1);
            }
            if (token == "^") {
                left = new And(left, right);
            } else if (token == "|") {
                left = new Or(left, right);
            } else if (token == ">") {
                left = new Implies(left, right);
            } else if (token == "=") {
                left = new Iff(left, right);
            } else {
                cerr << "Error: invalid operator '" << token << "'\n";
                exit(1);
            }
        }
        return left;
    }
}

// 真值表生成：遍历所有可能的变量取值组合，计算结果
void generate_truth_table(const Expression* expr) {
    int num_vars = 0;
    for (char ch : expr_str) {
        if (isalpha(ch)) {
            var_values.emplace(ch, false);
            ++num_vars;
        }
    }
    cout << expr_str << endl;
    cout << string(num_vars * 2 - 1, '-') << endl;
    for (int i = 0; i < (1 << num_vars); ++i) {
        for (auto& var : var_values) {
            var.second = (i >> (--num_vars)) & 1;
            cout << var.second << " ";
        }
        cout << "| " << expr->evaluate() << endl;
        num_vars = var_values.size();
    }
}

int main() {
    string expr_str;
    cout << "请输入逻辑表达式: ";
    getline(cin, expr_str);

    vector<string> tokens = tokenize(expr_str);
    int pos = 0;
    Expression* expr = parse_expression(tokens, pos, 0);
    if (pos < tokens.size()) {
        cerr << "Error: unexpected token '" << tokens[pos] << "'\n";
        exit(1);
    }

    generate_truth_table(expr);

    delete expr;

    return 0;
}

该程序首先读入一个逻辑表达式，然后进行词法分析，将表达式分解为多个词（变量、操作符和括号等）。

接着进行语法分析，将分解后的词组合成一个语法树。这里使用了一些类来表示不同类型的表达式，如变量、非、与、或、蕴涵和等值等。为了方便析构，这些类都继承自一个基类 Expression，并实现了 evaluate() 方法来计算表达式的值。

解析表达式的过程中，程序使用了一个 map 来存储操作符的优先级和结合性，以便进行正确的语法分析。

最后，程序使用遍历所有可能的变量取值组合的方式，计算出每一行的结果，输出真值表。

注意，为了避免使用全局变量，在本程序中使用了一些比较复杂的类来表示表达式和操作符等。同时，为了方便析构，本程序中使用了 RAII 技术，使用智能指针来管理内存。