Strona główna » Algorytmy » Artykuły » Kalkulator Logiczny
 

Kalkulator Logiczny

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

Wstęp

Kalkulator logiczny to program, który dla danego wyrażenia logicznego pozwoli obliczyć jego wartość. Opisany poniżej program będzie jego najprostszą implementacją, która będzie rozpoznawać główne operatory logiczne: koniunkcję, negację, alternatywę i równość. Wartości fałsz i prawda będą reprezentowane kolejno przez 0 i 1. Ponadto program będzie uwzględniał nawiasy okrągłe w celu podwyższenia priorytetu wybranego fragmentu równania.

Implementacja

Operacje logiczne

Przed przystąpieniem do pisania właściwej części programu warto napisać funkcję, która na podstawie danych wartości logicznych oraz operatora zwróci odpowiedni wynik. W tym przypadku funkcja check() przyjmuje dwa argumenty logiczne val1 i val2 oraz operator op. Ze względu na fakt, że negacja jest operatorem jednoargumentowym to zostanie zaimplementowana oddzielnie.

  1. bool check(bool val1, bool val2, char op){
  2.   switch (op){
  3.     case '|':
  4.       return val1 || val2;
  5.     case '&':
  6.       return val1 && val2;
  7.     case '^':
  8.       return val1 ^ val2;
  9.     case '=':
  10.       return val1 == val2;
  11.     default:
  12.       return false;
  13.   }
  14. }

(2.) Na podstawie znaku operatora zwróć wynik: (3. - 4.) alternatywy, (5. - 6.) koniunkcji, (7. - 8.) alternatywy wykluczającej czy (9. - 10.) równość. (11.) W przypadku braku rozpoznania operatora (12.) zwróć fałsz.

Kolejne wyrażenia

Kolejna funkcja result() przyjmuje dwa argumenty: data - ciąg znaków z danymi oraz pos - pozycję od której ma rozpocząć obliczanie wyrażenia. W celu wydobycia z wyrażenia wartości logicznych program korzysta z funkcji readvalue() zamieszczonej niżej.

  1. bool result (char* data, int &pos){
  2.   bool w = readvalue(data, pos);
  3.   char op;
  4.   while(data[pos] != '\0'){
  5.     op = data[pos++];
  6.     w = check(w, readvalue(data, pos), op);
  7.     if(data[pos] == ')'){
  8.       pos++;
  9.       return w;
  10.     }
  11.   }
  12.   return w;
  13. }

(2.) Wyodrębnij pierwszą wartość logiczną. (3.) Zadeklaruj zmienną op do przechowywania ostatniego znaku. (4.) Dopóki nie ma końca danych to (5.) pobierz operator i (6.) wylicz nową wartość. (7.) Jeśli następny znak to ")" to (8.) zwiększ numer pozycji i (9.) zwróć wartość. Fragment (7. - 9.) pozwala na zwrócenie wartości podczas obliczania wyrażenia w nawiasach. W przypadku głównego wywołania funkcji result() program zakończy się w linijce (12.) zwracając aktualną wartość zmiennej w tj. aktualnie obliczonego wyrażenia.

Rozpoznawanie znaków specjalnych

W trakcie pobierania wartości przed lub po operatorze może dojść do sytuacji, że (4.) zostanie użyta negacja wtedy należy zanegować (5.) wartość dalszej części wyrażenia. (6.) Zostanie podane wyrażenie w nawiasie - wtedy (7.) wyrażenie należy obliczyć oddzielnie. Poprzednia funkcja result() rozpozna znak ")" i przerwie obliczania wyrażania w nawiasach. Jednak jeśli żaden znak specjalny nie wystąpił to (9.) wystarczy zwrócić wartość wskazywaną przez cyfrę. (10.) W takim przypadku należy numer znaku 0 lub 1 zamienić na wartość liczbową, a następnie na wartość logiczną. Innym sposobem jest porównanie pobranego znaku do 1. Aby program wiedział, którą część wyrażenia rozpoznaje (2.) zwiększony zostaje numer rozpatrywanej pozycji w data.

  1. bool readvalue (char* data, int &i) {
  2.   ++i;
  3.   switch(data[i - 1]){
  4.     case '~':
  5.       return !result(data, i);
  6.     case '(':
  7.       return result(data, i);
  8.     default:
  9.       return bool(data[i - 1] - '0');
  10.   }
  11. }

Pozycja

Wszystkie funkcje podczas pobieranie kolejnego znaku zwiększają tą samą zmienną w pamięci. Pozwala to najprostsze zarządzenie przeglądaniem wszystkich informacji, ale przez to potrzebna jest dodatkowa funkcja, która taką zmienną zaalokuje w pamięci:

  1. bool solve (char* data){
  2.   int pos = 0;
  3.   return result(data, pos);
  4. }

Podczas korzystania z kalkulatora logicznego w innym programie wystarczy podać funkcji solve() odpowiedni ciąg znaków.

Testowanie funkcji

W celu przetestowania funkcji można skorzystać z poniższego kodu. Należy pamiętać, że wyrażenie powinno składać się wyłącznie z następujących znaków: 0, 1, &, |, ^, = oraz nawiasów okrągłych (, ).

  1. int main() {
  2.   char* data = new char[1024];
  3.   cin.getline(data, 1024);
  4.   cout << (solve(data) ? "PRAWDA" : "FALSZ") << endl;
  5.   system("pause");
  6.   return 0;
  7. }

Zadania

Zadanie 1

Napisz program, który prawidłowo będzie pomijał znaki spacji oraz będzie rozpoznawał implikację, która będzie reprezentowana przez =>.

Poprawne przykładowe dane:

  1. 0 => 1
  1. ~ ( 0&1)=>1