问题 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 技术，使用智能指针来管理内存。