小学期2——展示真值表C++版本

发表于 更新于 分类于 ，

521，冤种还在写题🥹
又闻线下上课，但大学牲仍禁止出校，悲伤超级加倍

大概思路是：
先用户输入的中缀表达式先预处理转换成后缀表达式，再用二进制枚举的方法枚举出真值表的每一条。
对于真值的每一条：用每个变量的具体的真值情况（0或1）来替换预处理过后缀表达式中具体的变量，最后再计算输出后缀表达式的真值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <cstring>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
using namespace std;
// 优先级
map<char, int> prior = {{'!', 5}, {'&', 4}, {'|', 3}};
// 是否为运算操作符
bool isOperator(char op) {
    if (op == '|' || op == '&' || op == '!') return true;
    return false;
}
// 中缀转后缀
string getPostfix(string infix) {
    // 一个栈存储运算符
    stack<char> s;
    // 存储后缀表达式
    string postfix;
    for (int i = 0; i < infix.size(); i++) {
        char tmp = infix[i];
        if (isOperator(tmp)) {
            while (!s.empty() && isOperator(s.top()) &&
                   prior[s.top()] >= prior[tmp]) {
                postfix.push_back(s.top());
                s.pop();
            }
            s.push(tmp);
        } else if (tmp == '(') {
            s.push(tmp);
        } else if (tmp == ')') {
            while (s.top() != '(') {
                postfix.push_back(s.top());
                s.pop();
            }
            s.pop();
        } else if (isalpha(tmp))
            postfix.push_back(tmp);
    }
    while (!s.empty()) {
        postfix.push_back(s.top());
        s.pop();
    }
    return postfix;
}
// 计算后缀表达式
bool Caculate(string postfix) {
    // 栈存储真值
    stack<int> s;
    bool left, right;
    bool flag;
    // 从左到右遍历后缀表达式
    for (int i = 0; i < postfix.size(); i++) {
        char c = postfix[i];
        // 如果是真值
        if (c == '0' || c == '1') {
            s.push(c - '0');
            continue;
            // 对 ! 特判，是为了简化代码
        } else if (c == '!') {
            flag = s.top();
            s.pop();
            s.push(!flag);
            continue;
        }
        // 对 ｜ 和 & 的判断
        right = s.top();
        s.pop();
        left = s.top();
        s.pop();
        if (c == '|') {
            s.push(left | right);
            continue;
        } else if (c == '&') {
            s.push(left & right);
            continue;
        }
    }
    return s.top();
}

//真值表输出
void Print(string infix) {
    // 生成后缀表达式 postfix
    string postfix = getPostfix(infix);
    // 存储命题变量
    vector<char> v;
    for (int i = 0; i < postfix.size(); i++)
        if (isalpha(postfix[i])) v.push_back(postfix[i]);
    // 删除重复的命题变量，此时 v 中存储的是命题变量的集合
    // v.size()为命题变量的个数
    v.erase(unique(v.begin(), v.end()), v.end());

    // 输出最上面一行
    // 先输出变量
    for (int i = 0; i < v.size(); i++) printf("%5c", v[i]);
    // 再输出中缀式，
    printf("    %s\n", infix.c_str());

    // 变量有几个，就有 2^n 个表达式
    // 比如有 2 个变量，它的真值情况就是 00, 01, 10, 11 四种情况
    // 转换为十进制就是 0 1 2 3
    // 此时每一个变量的真值情况可以表示为一个二进制位
    for (int i = 0; i < (1 << v.size()); i++) {
        // 将后缀式赋给临时字符串，用于计算
        string tmp = postfix;
        // 输出这一个的变量表达式
        for (int k = 0; k < v.size(); k++) printf("%5d", 1 & (i >> k));
        int j = 0;
        // 将临时字符串中的变量替换为对应的值
        while (j < tmp.size()) {
            if (isalpha(tmp[j])) {
                // 先找到位置
                int index = find(v.begin(), v.end(), tmp[j]) - v.begin();
                // 再找到对应的真值
                tmp[j] = (char)((int)(1 & (i >> index)) + '0');
            }
            j++;
        }
        // 最后输出它的真值
        printf("%5d\n", Caculate(tmp));
    }
    return;
}

int main() {
    string infix;
    printf("请您输入合法表达式(&表示合取,|表示析取，!表示非)\n");
    while (cin >> infix) {
        Print(infix);
        printf("请您输入合法表达式(&表示合取,|表示析取，!表示非)\n");
    }
    return 0;
}