БлогNot. C++: построить таблицу истинности для логического выражения

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&#65281;" << 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

теги: программирование математика c++ textprocessing

06.02.2020, 13:06; рейтинг: 79