Konwerter wyrażeń logicznych na tożsame, zawierające jedynie wyszczególnione operatory

    -- Sebastian Pawlak, 2003.


Celem projektu było zaprogramowanie algorytmu, realizującego przekształcanie dowolnych wyrażeń logicznych na tożsame, zawierające jedynie wyszczególnione operatory logiczne.

Do dyspozycji mamy kilka operatorów logicznych: negację (¬), alternatywę (V), koniunkcję (Λ), implikację (→) oraz równoważność (↔). Jako symboli zdań elementarnych można używać liter alfabetu [a...z] oraz 0 i 1.
Zatem, poprawnym wyrażeniem logicznym, będzie:

(¬p→(rVq))↔(rΛa)

Zdanie to jest równoważne poniższemu, zawierającemu jedynie operatory implikacji:

(((((p→0)→((r→0)→q))→((r→(a→0))→0))→((((r→(a→0))→0)→((p→0)→((r→0)→q)))→0))→0)

Albo innemu, tym razem z operatorami negacji (¬), alternatywy (V) i koniunkcji (Λ):

(¬((¬(¬p)V(rVq))Λ¬(rΛa))Λ¬((¬(¬p)V(rVq))Λ¬(rΛa)))

Zaprojektowany przeze mnie program dokonuje takich właśnie konwersji wyrażeń logicznych na tożsame, ale składające się z wyszczególnionych operatorów.
Zdefiniowanych zostało kilka grup operatorów, na które będzie następować konwersja. Podczas uruchamiania programu, użytkownik musi podać numer grupy (listę grup można uzyskać uruchamiając program bez parametrów).

Program został napisany w języku C, zgodnym ze standardem ANSI. Program został skompilowany w systemie operacyjnym Linux.


Zasady kompilacji

Program należy kompilować używając polecenia: 

gcc -o konwerter konwerter.c stos.c


Algorytmy użyte w programie

Podane przez użytkownika wyrażenie logiczne przekształcane jest do wyrażenia w Odwrotnej Notacji Polskiej. W ten sposób pozbywamy się z wyrażenia nawiasów oraz czynimy jego analizę łatwiejszą.
Oto jak działa algorytm konwersji wyrażenia w notacji nawiasowej do wyrażenia w Odwrotnej Notacji Polskiej (funkcja konwerterOdwNotPl()):

Krok 1
Jeżeli nie ma więcej znaków w ciągu wejściowym, to realizuj krok 6; w przeciwnym razie, przeczytaj następny element (nawias, operator lub argument) i nazwij go x.

Krok 2
Jeżeli x jest argumentem, to zapisz go w ciągu wyjściowym, umieść po nim spację i przejdź do realizacji kroku 1.

Krok 3
Jeżeli x jest nawiasem otwierającym, wpisz go na stos i realizuj krok 1. Jeżeli x jest nawiasem zamykającym, przejdź do realizacji kroku 4, a w przeciwnym razie - kroku 5.

Krok 4
Jeżeli na wierzchu stosu nie ma nawiasu otwierającego, to wycofaj ten obiekt ze stosu wpisując go do ciągu wyjściowego, a zaraz za nim wpisz spację i przejdź do wykonywania kroku 4. Jeżeli na wierzchołku stosu jest nawias otwierający, to wycofaj go ze stosu i przejdź do realizacji kroku 1.

Krok 5
W przypadku, gdy priorytet elementu wierzchołkowego stosu jest większy lub równy priorytetowi x, wycofaj element z wierzchołka stosu, wpisz go do ciągu wyjściowego, a potem wpisz za nim znacznik i powtórz krok 5. W przeciwnym razie, połóż x na wierzchołek stosu i wróć do wykonywania kroku 1.

Krok 6
Opróżnij stos po jednym elemencie, wpisując każdy z nich do ciągu wyjściowego i wstawiając między nimi spację; i to już koniec.

Następnie wyrażenie, w Odwrotnej Notacji Polskiej, ,,obliczane'' jest z wykorzystaniem stosu. Wtedy, elementarne podwyrażenia konwertowane są na odpowiadające (zawierające operatory z wyszczególnionej grupy), zgodnie ze zdefiniowanymi w programie szablonami.


Założenia przyjęte w programie

W programie zakładam, że:
- wyrażenie logiczne, podane przez użytkownika, musi być spójne - nie może zawierać białych znaków (np. spacji);
- wyrażenia elementarne mogą składać się z dowolnej pojedynczej małej litery alfabetu, zera lub jedynki;
- obsługiwane są następujące operacje logiczne: negacja (¬), alternatywa (V), koniunkcja (Λ), implikacja (→), równoważność (↔);
- podane wyrażenie logiczne musi być wyrażeniem poprawnym (m.in. musi zawierać prawidłową strukturę nawiasów);
- operator negacji jest jednoargumentowy i ma wyższy priorytet niż pozostałe operatory (dwuargumentowe);
- łączność operatorów, na tym samym poziomie struktury nawiasów, jest lewostronna (zatem: pVqΛr ↔ (pVq)Λr );
- w programie, do wyrażania poszczególnych operatorów logicznych, używamy następujących znaków: negacja (-), alternatywa (|), koniunkcja (&), implikacja (>), równoważność (=);
- wszystkie operatory dwuargumentowe mają ten sam priorytet.


Instrukcja obsługi programu

Program został skompilowany w systemie operacyjnym Linux i musi być uruchamiany w tymże systemie.
Program należy wywołać z dwoma parametrami:
- numerem grupy operatorów, na które będą konwertowane inne operatory;
- wyrażeniem logicznym, które będziemy konwertować; wyrażenie najlepiej otoczyć apostrofami.

Oto przykładowe wywołania programu:

./konwerter 0 '(p&q)>t'

./konwerter 10 '((p=q)>-q)=(p&y)'

./konwerter 5 '((p>1))'

W programie do wyrażania poszczególnych operatorów logicznych, używamy następujących znaków: negacja (-), alternatywa (|), koniunkcja (&), implikacja (>), równoważność (=).

Aby uzyskać listę dostępnych grup operatorów, wystarczy wywołać program bez parametrów:

./konwerter

Oto co zostanie wypisane na ekran (wśród instrukcji obsługi programu można dostrzec numery grup wraz z listą operatorów, na które będzie następować wymiana):

./konwerter nrKlasy wyrazenieLogiczne
    nrKlasy - numer grupy operatorow, na ktore
              beda zastepowane inne operatory:
            grupa 0 zamienia na operator: >
            grupa 1 zamienia na operatory: |-
            grupa 2 zamienia na operatory: &-
            grupa 3 zamienia na operatory: >-
            grupa 4 zamienia na operatory: =>
            grupa 5 zamienia na operatory: &>
            grupa 6 zamienia na operatory: |>
            grupa 7 zamienia na operatory: =>-
            grupa 8 zamienia na operatory: &=-
            grupa 9 zamienia na operatory: |=-
            grupa 10 zamienia na operatory: &>-
            grupa 11 zamienia na operatory: |>-
            grupa 12 zamienia na operatory: &|-
    wyrazenieLogiczne - konwertowane wyrazenie.

przyklady: ./konwerter 0 'p|(p>-q)'
           ./konwerter 1 'r&(t|h)'

Zatem, jeśli wywołamy program w ten sposób (grupa 0):

./konwerter 0 '(p|q)=t'

to wszystkie operatory zostaną zamienione na operator implikacji (→) i na ekran zostanie wypisane poniższe wyrażenie:

(((((p>0)>q)>t)>((t>((p>0)>q))>0))>0)

Kod źródłowy pliku "stos.h":

/* Implementacja stosu.
 */

#ifndef STOS_H
#define STOS_H

void push(char *);
char *pop(char *);
void pushChar(char);
char popChar(void);

#endif

Kod źródłowy pliku "stos.c":

/* Implementacja stosu.
 */
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "stos.h"

#define MAX_STOS 512 /* maksymalny rozmiar stosu */

char *stos[MAX_STOS];

int sp = 0; /* wskaznik kolejnego wolnego miejsca na stosie */

/* Wstawianie elementu na stos. */
void push(char *element)
{
    if (sp < MAX_STOS) {
        stos[sp] = (char *)malloc(strlen(element) + 1);
        strcpy(stos[sp++], element);
    } else
        fprintf(stderr, "push: Przepelnienie stosu!\n");
}

void pushChar(char element)
{
    if (sp < MAX_STOS) {
        stos[sp] = (char *)malloc(2);
        stos[sp][0] = element;
        stos[sp++][1] = '\0';
    } else
        fprintf(stderr, "pushChar: Przepelnienie stosu!\n");
}

/* Pobieranie elementu ze stosu. */
char *pop(char *element)
{
    if (sp > 0) {
        strcpy(element, stos[--sp]);
        free(stos[sp]);
        return element;
    }

    return NULL;
}

char popChar(void)
{
    char z;

    if (sp > 0) {
        z = stos[--sp][0];
        free(stos[sp]);
        return z;
    }

    return 0;
}

Kod źródłowy pliku "konwerter.c":

/*******************************************
 * Konwerter wyrazen logicznych na tozsame *
 *  zawierajace tylko okreslone operatory  *
 *     autor: Sebastian Pawlak, s1222      *
 *******************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stos.h"

enum {
    MAX = 1024,  /* maksymalna dlugosc wyrazenia (OdwNotPl) w znakach */
    MAX_OPERATOROW = 5,
    MAX_KLAS = 13
};

const char operatory[MAX_OPERATOROW] = "-&|>=";
typedef struct {
    char *zastOp; /* operatory, ktorymi zastepujamy inne */
    char *zast[MAX_OPERATOROW]; /* definicje zastapien */
} klasa;
const klasa klasy[MAX_KLAS] =
     /*     -p           p&q             p|q         p>q                p=q       */
 {{">",  {"(p>0)", "((p>(q>0))>0)", "((p>0)>q)",  "(p>q)",     "(((p>q)>((q>p)>0))>0)"}},
  {"|-", {"(-p)",  "(-(-p|-q))",    "(p|q)",      "(-p|q)",    "(-(-(-p|q)|-(-p|q)))" }},
  {"&-", {"(-p)",  "(p&q)",         "(-(-p&-q))", "(-(p&-q))", "(-(p&-q)&-(p&-q))"    }},
  {">-", {"(-p)",  "(-(p>-q))",     "(-p>q)",     "(p>q)",     "(-((p>q)>-(q>p)))"    }},
  {"=>", {"(p>0)", "((p>(q>0))>0)", "((p>0)>q)",  "(p>q)",     "(p=q)"                }},
  {"&>", {"(p>0)", "(p&q)",         "((p>0)>q)",  "(p>q)",     "((p>q)&(q>p))"        }},
  {"|>", {"(p>0)", "((p>(q>0))>0)", "(p|q)",      "(p>q)",     "(((p>q)>((q>p)>0))>0)"}},
  {"=>-",{"(-p)",  "(-(p>-q))",     "(-p>q)",     "(p>q)",     "(p=q)"                }},
  {"&=-",{"(-p)",  "(p&q)",         "(-(-p&-q))", "(-(p&-q))", "(p=q)"                }},
  {"|=-",{"(-p)",  "(-(-p|-q))",    "(p|q)",      "(-p|q)",    "(p=q)"                }},
  {"&>-",{"(-p)",  "(p&q)",         "(-p>q)",     "(p>q)",     "((p>q)&(q>p))"        }},
  {"|>-",{"(-p)",  "(-(p>-q))",     "(p|q)",      "(p>q)",     "(-((p>q)>-(q>p)))"    }},
  {"&|-",{"(-p)",  "(p&q)",         "(p|q)",      "(-p|q)",    "(-(p&-q)&-(p&-q))"    }}};

void konwerterOdwNotPl(char *, char *);
void konwerterOperatorow(char *, int);

int main(int argc, char *argv[])
{
    int i;
    char wyrazenieOdwNotPl[MAX];

    /* obsluga argumentow wywolania */
    if (argc != 3) {
        if (argc > 1)
            fprintf(stderr, "Nalezy podac odpowiednie parametry!\n\n");

        fprintf(stderr, "./konwerter nrKlasy wyrazenieLogiczne\n"
                "    nrKlasy - numer grupy operatorow, na ktore\n"
                "              beda zastepowane inne operatory:\n");
        for (i = 0; i < MAX_KLAS; i++)
            fprintf(stderr, "            grupa %d zamienia na operator%c: %s\n",
                    i, strlen(klasy[i].zastOp) == 1 ? '\0' : 'y', klasy[i].zastOp);
        fprintf(stderr, "    wyrazenieLogiczne - konwertowane wyrazenie.\n\n"
                "przyklady: ./konwerter 0 \'p|(p>-q)\'\n"
                "           ./konwerter 1 \'r&(t|h)\'\n");
        exit(1);
    }

    if (atoi(argv[1]) < 0 || atoi(argv[1]) >= MAX_KLAS) {
        fprintf(stderr, "Numer grupy spoza dopuszczalnego zakresu!\n");
        exit(1);
    }

    konwerterOdwNotPl(argv[2], wyrazenieOdwNotPl);
    konwerterOperatorow(wyrazenieOdwNotPl, atoi(argv[1]));

    return 0;
}

/* Funkcja przeksztalca wyrazenie zapisane w notacji nawiasowej
 * do wyrazenia w Odwrotnej Notacji Polskiej.
 */
void konwerterOdwNotPl(char *s, char *wynik)
{
    char x, y;

    while (x = *s++)  /* krok 1 */
        if ((x >= 'a' && x <= 'z') || x == '0' || x == '1') {  /* krok 2 */
            *wynik++ = x, *wynik++ = ' ';
        } else if (x == '(')  /* krok 3 */
            pushChar('(');
        else if (x == ')')  /* krok 4 */
            while ((y = popChar()) != '(')
                *wynik++ = y, *wynik++ = ' ';
        else {  /* krok 5 */
            while (y = popChar(),
                   y && (y == '-' || (strchr(operatory + 1, y) && x != '-')))
                *wynik++ = y, *wynik++ = ' ';
            pushChar(y);
            pushChar(x);
        }

    while(x = popChar(), (x && (*wynik++ = x, *wynik++ = ' ')) ||
          (*wynik++ = '\0'))  /* krok 6 */
        ;
}

/* Funkcja przeksztalca wyrazenie zapisane w Odwrotnej Notacji Polskiej
 * na tozsame posiadajace jedynie wyszczegolnione operatory.
 */
void konwerterOperatorow(char *s, int n)
{
    char z, op1[MAX], op2[MAX], t[MAX];
    char *p, *w;

    while (sscanf(s, "%c", &z) != -1 && (s += 2))
        if ((z >= 'a' && z <= 'z') || z == '0' || z == '1') /* argument */
            pushChar(z);
        else if ((p = strchr(operatory, z))) { /* operator */
            pop(op1);
            if (strchr(klasy[n].zast[p - operatory], 'q')) {
                strcpy(op2, op1);
                pop(op1); /* wez ze stosu jesli operator dwuargumentowy */
            }
            p = klasy[n].zast[p - operatory];
            t[0] = '\0';
            do {
                w = strpbrk(p, "pq");
                strncat(t, p, w ? w - p : strlen(p));  /* doklej tekst */
                w && strcat(t, *w == 'p' ? op1 : op2); /* doklej argument */
                p = w + 1;
            } while (w);
            push(t);
        } else {
            fprintf(stderr, "Nieznany znak w wyrazeniu logicznym!\n");
            exit(1);
        }

    pop(t);
    printf("%s\n", t);
}
w3cw3c
automatyka przemysłowa