Strona główna » Algorytmy » Artykuły » Rozszerzony Kalkulator logiczny

Rozszerzony Kalkulator logiczny

· część 1 · część 2 ·

Cel

Dotychczas napisana wersja kalkulatora logicznego ograniczała się do wyliczania wartości logicznej pojedynczego zdania. Niniejszy artykuł opisuje rozszerzenie funkcjonalności kalkulatora. Dodana zostanie możliwość wtrącenia zmiennych zdaniowych. Pozwoli to na sprawdzenie czy wyrażenie jest tautologią, albo do wykrycia, który przypadek jest prawdziwy / fałszywy. Niewątpliwą zaletą będzie fakt, że program sam wykryje zmienne zdaniowe i rozpatrzy wszystkie przypadki.

Implementacja

Założenia

Jak wiadomo za każdym usprawnieniem kryją się pewne ograniczenia. W tym przypadku zostało założone, że zmienna zdaniowa to mała litera alfabetu łacińskiego od a do z. Jeśli zostaną wykryte zmienne zdaniowe to program wypisze na konsolę odpowiednią tabelkę. W tabelce będą podane wartości dla każdego możliwego wartościowania zmiennych. Ponadto program powiadomi użytkownika jeśli okaże się, że wyrażenie jest tautologią.

Wyszukiwanie zmiennych

Znalezione zmienne będą przechowywane w wektorze przechowującym znaki. Przed rozpoczęciem obliczeń program wywoła funkcję checkForLetters(), która doda do wektora wszystkie występujące zmienne tak, aby na liście każda znalazła się dokładnie raz.

  1. void checkForLetters(char* data, vector<char> &letters) {
  2.   for (int i = 0; data[i]; i++) {
  3.     if (data[i] >= 'a' && data[i] <= 'z') {
  4.       if (findPos(letters, data[i]) >= letters.size()) {
  5.         letters.push_back(data[i]);
  6.       }
  7.     }
  8.   }
  9. }

(1.) Zmienna przyjmuje data - wyrażenie w którym mają być znalezione zmienne oraz letters - przekazany przez referencję wektor do którego mają być dodawane znalezione zmienne. (2.) Dla każdego znaku w wyrażeniu: (3.) sprawdź czy jest małą literą alfabetu łacińskiego. (4.) Jeśli znak nie występuje jeszcze na liście to (5.) go dodaj.

Szukanie pozycji

Do wyszukiwania elementu w wektorze służy funkcja findPos(), która zwraca pozycję gdzie w wektorze v jest wartość c.

  1. int findPos(vector<char> &v, char c) {
  2.   return find(v.begin(), v.end(), c) - v.begin();
  3. }

Wszystkie kombinacje

Do rozwiązania pozostałe teraz kwestia odpowiedniego wartościowania zmiennych i wypisywanie każdego możliwego przypadku. Przyjęte rozwiązanie generuje każdą możliwą listę wartości zmiennych, a następnie wykonuje kopię wprowadzonego przez użytkownika zdania. Podczas przepisywania w miejsce symboli zmiennych wstawiane są konkretne wartości. Wynik jak zawsze zostaje uzyskany poprzez funkcję result().

Funkcja solve() przyjmuje następujące zmienne: data - oryginalne wyrażenie wprowadzone przez użytkownika, datac - miejsce w pamięci gdzie można wykonać kopię zmiennej data, var_val - lista wartości logicznych zmiennych, vars - lista wykrytych zmiennych, t - zmienna, która przechowuje koniunkcję wartości logicznych wszystkich przypadków oraz i - wskazuje, której zmiennej wartość jest aktualnie ustalana.

  1. void checkAll(char* data, char* datac, bool* var_val, vector<char> &vars, bool &t, int i) {
  2.   if (i == vars.size()) {
  3.     for (int j = 0; j < vars.size(); j++) {
  4.       cout << (int)(var_val[j]) << " ";
  5.     }
  6.     for (int j = 0; data[j-1]; j++) {
  7.       if (data[j] >= 'a' && data[j] <= 'z') {
  8.         datac[j] = (int)(var_val[findPos(vars, data[j])]) + '0';
  9.       } else {
  10.         datac[j] = data[j];
  11.       }
  12.     }
  13.     int pos = 0;
  14.     bool res = result(datac, pos);
  15.     t &= res;
  16.     cout << (int)(res) << endl;

(2.) Jeśli zostały ustalone wartości wszystkich zmiennych to (3. - 5.) wypisz ustalone wartości zmiennych. Następnie utwórz wyrażenie na podstawie ustalonych wartości zmiennych: (6.) dla każdego znaku w data: (7.) jeśli wykryjesz zmienną to (8.) zastąp ją odpowiednią wartością. (9.) Jeśli przepisywany znak to nie zmienna to (10.) po prostu przepisz znak. (13. - 14.) Oblicz wartość uzyskanego wyrażenia. (15.) Oblicz koniunkcję dotychczasowych przypadków i (16.) Wypisz wynik przypadku.

W przypadku, gdy nie zostały ustalone wszystkie wartości zmiennych to:

  1.   } else {
  2.     for (int j = 0; j < 2; j++) {
  3.       var_val[i] = (bool)(j);
  4.       checkAll(data, datac, var_val, vars, t, i + 1);
  5.     }
  6.   }
  7. }

(18.) Dla każdej zmiennej: (19. - 22.) sprawdź przypadek dla każdej możliwej wartości logicznej. Rekurencyjnie w ten sposób uzyskuje się każdy możliwy przypadek.

Szukanie rozwiązanie

Ze względu na fakt, że funkcja solve() nie zwraca żadnej wartości to jej struktura znacząco się zmieniła, aby mogła wypisać wszystkie wyliczone dane. Funkcja dalej jednak przyjmuje tylko jeden argument: data - wprowadzone przez użytkownika wyrażenie.

  1. void solve(char* data) {
  2.   remSpaces(data);
  3.   vector<char> vars;
  4.   checkForLetters(data, vars);
  5.   char* datac = new char[strlen(data) + 1];
  6.   bool* var_val = new bool[vars.size()];
  7.   for (int i = 0; i < vars.size(); i++)
  8.     cout << vars[i] << " ";
  9.   cout << "wynik\n";
  10.   bool t = true;
  11.   checkAll(data, datac, var_val, vars, t);
  12.   if(vars.size() != 0)
  13.     cout << (!t ? "nie " : "") << "jest to tautologia\n";
  14.   delete datac, var_val;
  15. }

(2.) Na początku z wyrażenia usuwane są wszystkie zbędne spacje. (3.) Zadeklaruj wektor pod informacje o zmiennych. (4.) Znajdź wszystkie zmienne. Następnie (5.) alokuj miejsce pod kopię wprowadzonego wyrażenia oraz (6.) zadeklaruj listę w której będą przechowywane wartości wyrażeń dla każdego przypadku. Wypisz pierwszy wiersz tabelki wynikowej (7. - 8.) nazwy zmiennych oraz (9.) ostatnią kolumnę wynik. (10.) Załóż, że wprowadzone zdanie jest tautologią. (11.) Sprawdź wszystkie przypadki. (12.) Jeśli wyrażenie zawierało zmienne to (13.) wypisz informację czy wyrażenie jest tautologią. (14.) Zdealokuj zarezerwowaną pamięć.

Poprawki do kodu

Zmieniona została funkcja readvalue() w części dotyczącej operatora negacji. Teraz prócz znaku ~ do negacji można używać również znaku !. Teraz negacja nie neguje całego zdania po niej następującego, a jedynie wartość występującą po operatorze.

  1.     case '~':
  2.     case '!':
  3.       return !readvalue(data, i);

Testowanie funkcji

Po zmianach funkcja solve() nie zwraca żadnej wartości, ponieważ wyniki wypisuje bezpośrednio na konsolę. Poniższa funkcja main() wczytuje od użytkownika zdanie logiczne i wypisuje jego wartościowość dla każdego przypadku (dotyczy wyrażeń ze zmiennymi zdaniowymi).

  1. int main() {
  2.   char* data = new char[1024];
  3.   cin.getline(data, 1024);
  4.   solve(data);
  5.   delete data;
  6.   system("pause");
  7.   return 0;
  8. }