C++: построить таблицу истинности для логического выражения
Сервисы для вычисления таблиц истинности есть онлайн, прежде всего, на Вольфраме или вот здесь хороший js-сервис.
Так что напишем мы, конечно, велосипедик, для тех, кому нужно построение таблицы истинности для произвольного логического выражения именно в исходниках.
Вот как выглядит консольный интерфейс программы, также показан пример ввода выражения и результаты вывода:
Truth table evaluation
Expression example: (A|B)&!(A&B)
'!' Boolean NOT
'&' Boolean AND
'|' Boolean OR
'>' Implication
'#' Equivalence
'A',...,'Z' Variables
'q' Quit
Input the expression: (A|B)&C
A B C (A|B)&C
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Conjunction normal form
M(0, 1, 2, 4, 6)
(AvBvC)^(AvBv!C)^(Av!BvC)^(!AvBvC)^(!Av!BvC)
Disjunction normal form
M(3, 5, 7)
(!A^B^C)v(A^!B^C)v(A^B^C)
Для продолжения нажмите любую клавишу . . .
Достаточно легко решить задачу с использованием обратной польской записи выражений, но мы хотим, чтобы юзер писал в нормальной инфиксной форме (см. функцию infix_to_suffix).
Для экономичности разработки, везде для хранения данных применялись контейнеры STL.
Код не должен бояться тавтологий типа A&A&A, но в целом на совершенство не претендует, просто таких исходников в сети почти нет.
Код печатает немного отладочной инфы на тему CNF и DNF.
Также интересны в коде функции cls и pause, пытающиеся быть "универсальными" для Windows- и Unix-платформ.
Запускалось в консоли Visual Studio 2019, но должно работать и в версиях помладше, по крайней мере, с 2010-й.
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <cctype>
#include <cmath>
using namespace std;
int isoperator(char c) {
switch (c) {
case '!': case '&': case '|': case '>': case '#': return 1;
}
return 0;
}
int isbinaryoperator(char c) {
return c != '!' && isoperator(c);
}
int isinvalidchar(char c) {
if (c == '(' || c == ')') return 0;
else if (isupper(c) || isoperator(c)) return 0;
return 1;
}
int isupperalpha(char c) { return isupper(c); }
int priority(char opr) {
switch (opr) {
case '!': return 5;
case '&': return 4;
case '|': return 3;
case '>': return 2;
case '#': return 1;
default: return 0;
}
}
int is_valid_expression(const string& exp) {
if (exp.empty()) {
cout << "Empty input！" << endl; return 0;
}
string::const_iterator pos;
pos = find_if(exp.begin(), exp.end(), isinvalidchar);
if (pos != exp.end()) {
cout << "Error char: '" << *pos << '\'' << endl; return 0;
}
if (!isupper(*(exp.begin())) && *(exp.begin()) != '(' && *(exp.begin()) != '!') {
cout << "Error start char(s)!" << endl; return 0;
}
if (!isupper(*(exp.rbegin())) && *(exp.rbegin()) != ')') {
cout << "Error end char(s)!" << endl; return 0;
}
if (0 == count_if(exp.begin(), exp.end(), isupperalpha)) {
cout << "No arguments!" << endl; return 0;
}
if (count(exp.begin(), exp.end(), '(') != count(exp.begin(), exp.end(), ')')) {
cout << "Unpair brackets!" << endl; return 0;
}
vector<int> bracketpos[2];
for (pos = exp.begin(); pos != exp.end(); ++pos) {
if (*pos == '(') bracketpos[0].push_back(distance(exp.begin(), pos));
else if (*pos == ')') bracketpos[1].push_back(distance(exp.begin(), pos));
}
vector<int>::size_type v;
for (v = 0; v != bracketpos[0].size(); ++v) {
if (bracketpos[0][v] > bracketpos[1][v]) {
cout << "Bad brackets!" << endl; return 0;
}
}
string::size_type i;
for (i = 0; i != exp.size() - 1; ++i) {
if (isupper(exp[i])) {
if (exp[i + 1] != ')' && !isbinaryoperator(exp[i + 1])) {
cout << '\'' << exp[i] << "' Bad operand:" << exp[i] << exp[i + 1] << endl; return 0;
}
}
else if (exp[i] == '(') {
if (exp[i + 1] == ')' || isbinaryoperator(exp[i + 1])) {
cout << '\'' << exp[i] << "' Bad operand:" << exp[i] << exp[i + 1] << endl; return 0;
}
}
else if (exp[i] == ')') {
if (exp[i + 1] != ')' && !isbinaryoperator(exp[i + 1])) {
cout << '\'' << exp[i] << "' Bad operand:" << exp[i] << exp[i + 1] << endl; return 0;
}
}
else if (exp[i] == '!') {
if (exp[i + 1] == ')' || isbinaryoperator(exp[i + 1])) {
cout << '\'' << exp[i] << "' Bad operand:" << exp[i] << exp[i + 1] << endl; return 0;
}
}
else {
if (exp[i + 1] == ')' || isbinaryoperator(exp[i + 1])) {
cout << '\'' << exp[i] << "' Bad operand:" << exp[i] << exp[i + 1] << endl; return 0;
}
}
}
return 1;
}
set<char> get_expinfo(const string& exp) {
set<char> exp_elem;
for (string::size_type i = 0; i != exp.size(); ++i) {
if (isupper(exp[i])) {
exp_elem.insert(exp[i]);
}
}
return exp_elem;
}
string infix_to_suffix (const string& exp) {
char top;
stack<char> s;
string suffix;
for (string::size_type i = 0; i != exp.size(); ++i) {
if (isupper(exp[i])) suffix += exp[i];
else if (exp[i] == '(') s.push(exp[i]);
else if (isoperator(exp[i])) {
while (1) {
if (s.empty() || s.top() == '(') {
s.push(exp[i]); break;
}
else {
top = s.top();
if (priority(exp[i]) > priority(top) || (exp[i] == '!' && top == '!')) {
s.push(exp[i]); break;
}
else {
suffix += s.top(); s.pop();
}
}
}
}
else if (exp[i] == ')') {
while (!s.empty() && (top = s.top()) != '(') {
suffix += top; s.pop();
}
s.pop();
}
}
while (!s.empty()) {
suffix += s.top(); s.pop();
}
return suffix;
}
int eval(const string& row, const string& suffix, const set<char>& exp_elem) {
char temp = 0;
int p, q, ret;
stack<char> s;
map<char, int> m;
string::size_type i;
set<char>::const_iterator pos;
for (pos = exp_elem.begin(), i = 0; pos != exp_elem.end(); ++pos, ++i) {
m.insert(pair<char, int>(*pos, row[i] - '0'));
}
p = q = 0;
for (i = 0; i != suffix.size(); ++i) {
if (isupper(suffix[i])) s.push(m[suffix[i]]);
else if (isoperator(suffix[i])) {
q = s.top(); s.pop();
if (suffix[i] != '!' && !s.empty()) {
p = s.top(); s.pop();
}
switch (suffix[i]) {
case '!':
temp = !q;
break;
case '&':
temp = p && q;
break;
case '|':
temp = p || q;
break;
case '>':
temp = !p || q;
break;
case '#':
temp = (!p || q) && (!q || p);
break;
}
s.push(temp);
}
}
ret = s.top();
s.pop();
return ret;
}
vector<char> print_table(const string& exp) {
int cols, rows, temp;
string row, suffix;
set<char> exp_elem;
exp_elem = get_expinfo(exp);
for (set<char>::iterator pos = exp_elem.begin(); pos != exp_elem.end(); ++pos) {
cout << '\t' << *pos;
}
cout << '\t' << exp << endl;
suffix = infix_to_suffix(exp);
cols = exp_elem.size();
rows = static_cast<int>(pow(2.0, cols));
bitset <26> bs;
vector <char> result;
for (int i = 0; i < rows; ++i) {
bs = i;
row = bs.to_string<char, char_traits<char>, allocator<char> >();
row.erase(0, 26 - cols);
for (int j = 0; j < cols; ++j) {
cout << '\t' << row[j];
}
temp = eval(row, suffix, exp_elem);
result.push_back(temp);
cout << '\t' << temp << endl;
}
return result;
}
int is_tautology(const vector<char>& result) {
return result.end() == find(result.begin(), result.end(), 0);
}
int is_contradiction(const vector<char>& result) {
return result.end() == find(result.begin(), result.end(), 1);
}
void print_cnf (const vector<char>& result, const set<char>& exp_elem) {
if (is_tautology(result)) return;
vector<char> elem;
copy(exp_elem.begin(), exp_elem.end(), back_inserter(elem));
size_t i, j;
vector<int> v;
for (i = 0; i != result.size(); ++i) {
if (result[i] == 0) v.push_back(i);
}
cout << "Conjunction normal form\n" << "M(";
for (i = 0; i != v.size(); ++i) {
if (i < v.size() - 1) cout << v[i] << ", ";
else cout << v[i];
}
cout << ')' << endl;
bitset <26> bs;
string row;
for (i = 0; i != v.size(); ++i) {
cout << '(';
bs = v[i];
row = bs.to_string<char, char_traits<char>, allocator<char> >();
row.erase(0, 26 - elem.size());
for (j = 0; j != elem.size(); ++j) {
if (row[j] == '1') cout << "!" << elem[j];
else cout << elem[j];
if (j < elem.size() - 1) cout << "v";
}
if (i < v.size() - 1) cout << ")^";
else cout << ')' << endl;
}
}
void print_dnf(const vector<char>& result, const set<char>& exp_elem) {
if (is_contradiction(result)) return;
vector<char> elem;
copy(exp_elem.begin(), exp_elem.end(), back_inserter(elem));
size_t i, j;
vector<int> v;
for (i = 0; i != result.size(); ++i) {
if (result[i] == 1) v.push_back(i);
}
cout << "Disjunction normal form\n" << "M(";
for (i = 0; i != v.size(); ++i) {
if (i < v.size() - 1) cout << v[i] << ", ";
else cout << v[i];
}
cout << ')' << endl;
bitset <26> bs;
string row;
for (i = 0; i != v.size(); ++i) {
cout << '(';
bs = v[i];
row = bs.to_string<char, char_traits<char>, allocator<char> >();
row.erase(0, 26 - elem.size());
for (j = 0; j != elem.size(); ++j) {
if (row[j] == '1') cout << elem[j];
else cout << "!" << elem[j];
if (j < elem.size() - 1) cout << "^";
}
if (i < v.size() - 1) cout << ")v";
else cout << ')' << endl;
}
}
void cls() {
#ifdef _WIN32
system("cls");
#else
system("clear");
#endif
}
void pause() {
#ifdef _WIN32
system("pause");
#else
system("read -p \"Press any key to continue...\" tmp");
#endif
}
void instruction() {
cout
<< "Truth table evaluation\n"
<< "Expression example: (A|B)&!(A&B)\n"
<< "'!' Boolean NOT\n"
<< "'&' Boolean AND\n"
<< "'|' Boolean OR\n"
<< "'>' Implication\n"
<< "'#' Equivalence\n"
<< "'A',...,'Z' Variables\n"
<< "'q' Quit\n"
<< "Input the expression: ";
}
int main() {
string exp;
set<char> exp_elem;
vector<char> result;
while (1) {
cls();
instruction();
cin >> exp;
if (exp == "q") break;
if (!is_valid_expression(exp)) {
pause();
continue;
}
exp_elem = get_expinfo (exp);
result = print_table (exp);
print_cnf (result, exp_elem);
print_dnf (result, exp_elem);
pause();
}
return 0;
}
Bonus. Маленькая прога ниже выводит просто "нули и единицы" для нужного количества разрядов (в примере 4), не самый оптимальный способ, зато без библиотек :)
#include <iostream>
using namespace std;
void comb_impl(bool* begin, bool* end, size_t n) {
if (n) {
for (short i = 0; i < 2; comb_impl(begin, end, n - 1), ++i)
*(end - n) = i;
}
else {
for (bool* it = begin; it != end; ++it)
cout << *it << ' ';
cout << '\n';
}
}
void comb(size_t width) {
bool* seq = new bool[width];
comb_impl(seq, seq + width, width);
delete[] seq;
}
int main() {
comb(4);
cin.get();
return 0;
}
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1
06.02.2020, 13:06 [7190 просмотров]