[Lazarus] Kalkulator wyrażeń logicznych

Projekty użytkowników forum zarówno sprzętowe, jak i związane z programowaniem w dowolnym języku.
Awatar użytkownika
gaweł
Expert
Expert
Posty: 859
Rejestracja: wtorek 24 sty 2017, 22:05
Lokalizacja: Białystok

[Lazarus] Kalkulator wyrażeń logicznych

Postautor: gaweł » wtorek 21 sty 2020, 01:30

Kalkulator wyrażeń logicznych

Domek z karthttps://www.youtube.com/watch?v=uBIqfYda4lU


W praktyce zabawy z układami logicznymi czasami zachodzi konieczność zbudowania kombinacyjnego układu logicznego, takiego na bramkach. Małe piwo jak realizuje on prostą funkcję kombinacyjną. Trochę gorzej przedstawia się, gdy ta funkcja logiczna staje się rozbudowana. Wyobraźmy sobie taki układ:
LOGIC1.png
I teraz rzecz najmniej przyjemna w tym wszystkim. Trzeba zweryfikować poprawność funkcji logicznej. Kto ma ochotę określić wynik funkcji „na piechotę”? Można do tego użyć jakiegoś programu do obróbki cyfrówki, przykładowo program do obróbki układów PLD i sprawdzić (poprzez symulację) generowane wyniki funkcji. Pomijając samą kwestię opisu układu (można go wysmarować w VHLD'u lub narysować), sprowadza się to do ustalenia na wejściach stanów logicznych i (poprzez symulację) uzyskać wynik funkcji logicznej.
Można zrobić inaczej, podążyć moją drogą. Otóż napisałem sobie odpowiedni program do obróbki funkcji logicznych. Łączy on w sumie kilka wątków: algorytmów rekurencyjnych i zagadnień klasy budowy kompilatorów.
Powyższy układ można „podzielić” na mniejsze kawałki i uzyskać następujące równania logiczne.
LOGIC2.png
Mamy:
  • NOT ( A AND B AND C)
  • NOT D
  • E AND F
  • NOT H
  • G AND I AND J
  • NOT (K OR L)
  • cos1 = NOT ( ( NOT ( A AND B AND C)) OR (NOT D) OR (E AND F))
  • cos2 = NOT ( (NOT H) AND (G AND I AND J))
  • cos1 XOR cos2 = (NOT ( ( NOT ( A AND B AND C)) OR (NOT D) OR (E AND F))) XOR (NOT ( (NOT H) AND (G AND I AND J)))
  • NOT ( ((NOT ( ( NOT ( A AND B AND C)) OR (NOT D) OR (E AND F))) XOR (NOT ( (NOT H) AND (G AND I AND J)))) AND (NOT (K OR L)))
No mam nadzieję, że nie pogubiłem nawiasów :-)
Treść tego równania można wkleić do odpowiedniego okienka i ustalić stany logiczne na użytych wejściach. Przez Przed wyrachowaniem wyniku, dokonywana jest analiza wyrażenia. Okazuje się, że nie zgubiłem nawiasów (wszystkie nawiasy mają swoją parę, analizator wyrażenia sprawdza dokładnie postać zapisu i nie da sobie wcisnąć „ciemnoty”).
logic3.png
Klik na przycisk „Oblicz” i mamy wynik:
logic4.png
Można poprzestawiać stany na wejściach i ponowne „Oblicz” da wynik funkcji logicznej.
Jak skonstruowany jest program? Ma wbudowany analizator wyrażenia logicznego (dowolnie skomplikowanego) i je obrabia. Dokładnie tak samo robią to kompilatory, z tym, że w tym przypadku nie jest generowany kod programu (choć to nie jest żaden problem) a zachodzi interpretacja wyrażenia. Interpretacja → czyli program wykonuje nakazane z zapisu wyrażenia logicznego obliczenia i uzyskuje wynik. Całość sprowadza się do dwóch chwytów: notacji BNF (przydatnej w trakcie analizy wyrażenia) oraz notacji Łukasiewicza (zwanej inaczej notacją odwrotna polską, przydatną do rachowania lub generowania kodu dla procka). Ale o tym to już w następnej części.
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.
Ostatnio zmieniony czwartek 23 sty 2020, 22:28 przez gaweł, łącznie zmieniany 2 razy.

Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse

Awatar użytkownika
wojtek
Uber Geek
Uber Geek
Posty: 2147
Rejestracja: piątek 04 wrz 2015, 09:03

Re: [Lazarus] Kalkulator wyrażeń logicznych

Postautor: wojtek » wtorek 21 sty 2020, 04:57

No nieźle :)
Wojtek

Awatar użytkownika
piotrek
User
User
Posty: 118
Rejestracja: niedziela 05 lis 2017, 02:46

Re: [Lazarus] Kalkulator wyrażeń logicznych

Postautor: piotrek » wtorek 21 sty 2020, 09:50

Zapis nawiasowy jest trochę kłopotliwy, nawet w mało złożonym układzie logicznym. Skoro już wspominasz o notacji ONP zastanawia mnie jakby się spisywał zapis w postaci uporządkowanej listy transformującej do drzewa bramek, coś jak: NAND2 XOR2 NOR3 NAND3 NOT AND2 NAND2... czyli jadąc od bramki wyjściowej do dolnej wejściowej

Awatar użytkownika
gaweł
Expert
Expert
Posty: 859
Rejestracja: wtorek 24 sty 2017, 22:05
Lokalizacja: Białystok

Re: [Lazarus] Kalkulator wyrażeń logicznych

Postautor: gaweł » środa 22 sty 2020, 18:49

Rekurencyjna analiza wyrażeń

Notacja BNF. Sięgając do zasobów encyklopedycznych, to:

Notacja Backusa-Naura (ang. Backus-Naur Form, BNF) – metoda zapisu reguł gramatyki bezkontekstowej.
Notacja ta jest powszechnie używana w informatyce do zapisu składni (syntaktyki) języków programowania i protokołów komunikacyjnych. Została wymyślona przez Johna Backusa w latach 50. w czasie prac nad językiem Fortran, a następnie zmodyfikowana przez Petera Naura i użyta do zdefiniowania składni języka ALGOL.
Notacja BNF jest zestawem reguł produkcji o następującej postaci:
<symbol> ::= <wyrażenie zawierające symbole>
Znaczenie użytych tu symboli jest następujące:
  • lewy ogranicznik symbolu: <
  • prawy ogranicznik symbolu: >
  • jest zdefiniowane jako (taki jakby operator przypisania): ::=
  • lub: |

Posłużmy się przykładem. Co to jest liczba całkowita?
W myśl powyższych reguł, liczba całkowita to:
<liczba całkowita>::= <znak liczby> <ciąg cyfr>
gdzie:
<znak liczby> ::= + | - |
(znak liczby to: + lub – lub puste)
gdzie:
<ciąg cyfr> ::= <cyfra> <ciąg cyfr> | <cyfra>
natomiast:
<cyfra> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Tu warto zauważyć, że definicja jest rekurencyjna. <ciąg cyfr> to jest <cyfra> i <ciąg cyfr> lub <cyfra> (rekurencja).
Nie wiem jak was, ale jak mnie uczyli na studiach Pascal'a, to myśmy „katowali” notację BNF do upadu. Wtedy wydawało mi się to bez sensu i do niczego nie przydatne. Dzisiaj widzę to trochę inaczej. Wspomniałem o notacji BNF. Jak by wyglądała definicja wyrażenia logicznego w powyższej notacji?

<wyrażenie logiczne> ::= <wyrażenie proste>
gdzie:
<wyrażenie proste> ::= <operator jednoargumentowy> <składnik> | <wyrażenie addytywne>
<operator jednoargumentowy> ::= NOT |
(jest to NOT lub puste).
Natomiast: <wyrażenie addytywne> ::= <składnik> | <składnik> <operator addytywny> <wyrażenie addytywne>
gdzie <operator addytywny> ::= OR | XOR
<składnik> ::= <czynnik> | <czynnik> <operator multiplikatywny> <czynnik>

gdzie:
<czynnik> ::= <identyfikator> | <stała logiczna> | ( <wyrażenie proste> )
<operator multiplikatywny> ::= AND
<stała logiczna> ::= TRUE | FALSE

Rozumiem, że to wygląda na pop..ne, ale w praktyce daje się realnie zastosować. Wystarczy trochę przemyśleń i staje się jasne i proste. Daleko nie szukając, analiza wyrażenia logicznego ma zdefiniowane symbole:
  • IdentSy – identyfikator
  • LeftParSy – nawias (
  • RightParSy – nawias )
  • LogicAndOpSy – AND – operator logiczny
  • LogicOrOpSy – OR – operator logiczny,
  • LogicExOrOpSy – XOR – operator logiczny
  • LogicNotOpSy – NOT – operator logiczny
  • TrueSy – stała logiczna
  • FalseSy – stała logiczna.
Plus kilka innych elementów leksykalnych, które mają następujące znaczenie:
  • NoSy – coś nieokreślonego, innego niż wyżej wymienione,
  • EoLnSy – osiągnięto koniec analizowanego wiersza.
Mamy podstawową funkcję analizy leksykalnej (ReadSymbol), która „podczepiona” pod string wejściowy podaje kolejne symbole z tego stringu. Ujmując to prościej, funkcja pobiera kolejne znaczki z wejściowego stringu i zwraca symbol wczytanego elementu (dodatkowo w zmiennej Spelling jest treść tego symbolu). Tu warto zauważyć, że oprócz zestawu słów kluczowych, ta funkcja posiłkuje się tablicą znakową, w której również zdefiniowane są symbole (nie ma znaczenia, czy w wyrażeniu wystąpi wyraz „AND” czy znaczek & → jest to rozpoznany operator logiczny.
Wspomniana funkcja ma następującą postać:

Kod: Zaznacz cały

function TLogicExpressionForm.ReadSymbol : SymbolType ;
  var
    CharIndex           : integer ;
    LocalSymbol         : SymbolType ;
    Index               : SymbolType ;
    Ch                  : char ;
    WorkSpelling        : ObjectNameType ;

begin (* TLogicExpressionForm.ReadSymbol *)
  Ch := NextChar ;
  while ( Ch = Space ) and ( CharPosition <= CurrentLineSize ) do
    Ch := NextChar ;
  if Ch = chr ( 0 ) then
  begin (* 1 *)
    Spelling := '<EOLN>' ;
    ReadSymbol := EoLnSy ;
    exit ;
  end (* 1 *) ;
  if Letter ( Ch ) then
  begin (* 1 *)
    LocalSymbol := IdentSy ;
    CharIndex := 1 ;
    Spelling := Ch ;
    WorkSpelling := UpCase ( Ch ) ;
    Ch := NextChar ;
    while AlfaChar ( Ch ) do
    begin (* 2 *)
      CharIndex := succ ( CharIndex ) ;
      if CharIndex <= KeyLength then
      begin (* 3 *)
        Spelling := concat ( Spelling , Ch ) ;
        WorkSpelling := concat ( WorkSpelling , UpCase ( Ch ) ) ;
      end (* 3 *) ;
      Ch := NextChar ;
    end (* 2 *) ;
    CharPosition := pred ( CharPosition ) ;
    for Index := LogicAndOpSy to EndDictSy do
      if WorkSpelling = Keywords [ Index ] then
        LocalSymbol := Index ;
  end (* 1 *)
  else
    if Ch < #127 then
    begin (* 1 *)
      Spelling := Ch ;
      LocalSymbol := CharSymbol [ Ch ] ;
    end (* 1 *)
    else
    begin (* 1 *)
      LocalSymbol := NoSy ;
    end (* 1 *);
  ReadSymbol := LocalSymbol ;
end (* TLogicExpressionForm.ReadSymbol *) ;
Teraz sama analiza wyrażenia, więc wróćmy do definicji
<czynnik> ::= <identyfikator> | <stała logiczna> | ( wyrażenie proste> )
mamy dokładnie to odzwierciedlone w algorytmie (rozróżnienie na stałą logiczną, zmienną logiczną lub wyrażenie proste ujęte w nawiasy):

Kod: Zaznacz cały

      procedure MultiplicativeExpression ;

        var
          TermEntry     : ObjectRecordPtr ;

      begin (* MultiplicativeExpression *)
        if ( Symbol = TrueSy ) or ( Symbol = FalseSy ) then
          IPNLoadLogicConst ( Symbol = TrueSy )
        else
          if Symbol = IdentSy then
          begin (* 1 *)
            TermEntry := FindObject ( Spelling ) ;
            if TermEntry <> nil then
              IPNVariable ( UpperCase ( Spelling ) )
            else
              Error ( UndefinedElementErrorCode ) ;
          end (* 1 *)
          else
          if Symbol = LeftParSy then
          begin (* 1 *)
            Symbol := ReadSymbol ;
            SimpleExpression ;
            if Symbol <> RightParSy then
              Error ( ExpectedRightParErrorCode ) ;
          end (* 1 *)
          else
            Error ( UndefinedElementErrorCode ) ;
        Symbol := ReadSymbol ;
      end (* MultiplicativeExpression *) ;
kolejny element definicji wyrażenia:
<składnik> ::= <czynnik> | <czynnik> <operator multiplikatywny> <czynnik>
ma swoje odzwierciedlenie w algorytmie (funkcja MultiplicativeExpression obrabia <czynnik>):

Kod: Zaznacz cały

    procedure AdditiveExpression ;
      var
        MultOperator    : SymbolType ;

    begin (* AdditiveExpression *)
      MultiplicativeExpression ;
      while ( Symbol = LogicAndOpSy ) do
      begin (* 1 *)
        MultOperator := Symbol ;
        Symbol := ReadSymbol ;
        MultiplicativeExpression ;
        IPNAddOperator ( MultOperator ) ;
      end (* 1 *) ;
    end (* AdditiveExpression *) ;
Kolejny „poziom” wyrażenia odpowiada definicji w notacji BNF:
<wyrażenie proste> ::= <operator jednoargumentowy> <składnik> | <wyrażenie addytywne>
Funkcja AdditiveExpression obrabia <składnik>.

Kod: Zaznacz cały

  procedure SimpleExpression ;
    var
      AddOperator       : SymbolType ;
      LogicNot          : boolean ;
  begin (* SimpleExpression *)
    LogicNot := False ;
    if Symbol = LogicNotOpSy then
    begin (* 1 *)
      LogicNot := True ;
      Symbol := ReadSymbol ;
    end (* 1 *) ;
    AdditiveExpression ;
    if LogicNot then
      IPNAddOperator ( LogicNotOpSy ) ;
    while ( Symbol = LogicOrOpSy ) or ( Symbol = LogicExOrOpSy ) do
    begin (* 1 *)
      AddOperator := Symbol ;
      Symbol := ReadSymbol ;
      AdditiveExpression ;
      IPNAddOperator ( AddOperator ) ;
    end (* 1 *) ;
  end (* SimpleExpression *) ;
A analiza całego wyrażenia to przede wszystkim analiza wyrażenia prostego (dalsza część to „odwrócenie” listy liniowej notacji odwrotnej polskiej, gdyż ta w zastosowanym rozwiązaniu nie tworzy kolejki typu FIFO).

Kod: Zaznacz cały

begin (* TLogicExpressionForm.GetLogicExpression *)
  ExpressionEntry := nil ;
  SimpleExpression ;
  TmpExpression := ExpressionEntry ;
  ExpressionEntry := nil ;
  while TmpExpression <> nil do
  begin (* 1 *)
    Element := TmpExpression ;
    TmpExpression := TmpExpression ^ . FwdLink ;
    Element ^ . FwdLink := ExpressionEntry ;
    ExpressionEntry := Element ;
  end (* 1 *) ;
  GetLogicExpression := ExpressionEntry ;
end (* TLogicExpressionForm.GetLogicExpression *) ;

Tu nie trzeba nic kombinować i „naginać” do rzeczywistości. Jak na początku właściwie podejść do tematu, całość niejako sama się rozwiąże. Prawda, że proste?

Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse

Awatar użytkownika
gaweł
Expert
Expert
Posty: 859
Rejestracja: wtorek 24 sty 2017, 22:05
Lokalizacja: Białystok

Re: [Lazarus] Kalkulator wyrażeń logicznych

Postautor: gaweł » sobota 25 sty 2020, 04:05

Notacja odwrotna polska

Muza wspierającahttps://www.youtube.com/watch?v=Tjwf-iIM17I

Sięgając do encyklopedycznej definicji notacji odwrotnej polskiej:

Odwrotna notacja polska – sposób zapisu wyrażeń arytmetycznych, w którym znak wykonywanej operacji umieszczony jest po operandach (zapis postfiksowy), a nie pomiędzy nimi jak w konwencjonalnym zapisie algebraicznym (zapis infiksowy) lub przed operandami jak w zwykłej notacji polskiej (zapis prefiksowy). Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań.

Notacja ta umożliwia obliczenie wartości wyrażenia (arytmetycznego jak i logicznego) bez użycia nawiasów. Dokładnie tak postępują kompilatory (a przynajmniej te, w których miałem okazję grzebać). Jak jest wspomniane wyżej, cechą charakterystyczną tej notacji jest podanie dwóch argumentów i działania. No nie jest to do końca prawdą, ponieważ tu należy wspomnieć, że są operacje dwuargumentowe oraz jednoargumentowe. Operatory logiczne typu OR, AND czy XOR to rzecz jasna operatory dwuargumentowe (do odpowiednich bramek dochodzą dwa druty). Funkcja logiczna negacji (NOT) jest operatorem jednoargumentowym. Są nawet kalkulatory, które rachują w tej notacji, ale nie są zbytnio popularne. Może to wynika trochę z odmiennej natury, ludzie nie są przyzwyczajeni do takiego podejścia.
Wracając do filozofii tej notacji, to na tą notację można spojrzeć jak na ciąg operacji, który powstaje w wyniku kompilacji wyrażenia. Właściwie to nic nie trzeba kombinować, wychodzi to jako naturalna konsekwencja analizy wyrażenia zapisanej zgodnie z filozofią notacji BNF. Jedynym miejscem, gdzie występuje operator jednoargumentowy to:
<wyrażenie proste> ::= <operator jednoargumentowy> <składnik> | <wyrażenie addytywne>
<operator jednoargumentowy> ::= NOT |
Ma to swoje odbicie w algorytmie:

Kod: Zaznacz cały

procedure SimpleExpression ;
    var
      AddOperator       : SymbolType ;
      LogicNot          : boolean ;

  begin (* SimpleExpression *)
    LogicNot := False ;
    if Symbol = LogicNotOpSy then
    begin (* 1 *)
      LogicNot := True ;
      Symbol := ReadSymbol ;
    end (* 1 *) ;
    AdditiveExpression ;
    if LogicNot then
      RPNAddOperator ( LogicNotOpSy ) ;
    while ( Symbol = LogicOrOpSy ) or ( Symbol = LogicExOrOpSy ) do
    begin (* 1 *)
      AddOperator := Symbol ;
      Symbol := ReadSymbol ;
      AdditiveExpression ;
      RPNAddOperator ( AddOperator ) ;
    end (* 1 *) ;
  end (* SimpleExpression *) ;
W zapisie wyrażenia może wystąpić <operator jednoargumentowy> (przed wyrażeniem, znaczy przed składnikiem) i <składnik>. Dokładnie tak jest w powyższym kawałku programu: w zmiennej typu boolean zapamiętane jest, czy wystąpił jedyny możliwy operator jednoargumentowy NOT. Jeżeli tak, to po obróbce składnika generowana jest operacja negacji logicznej. Nie jest istotne, jak złożona jest budowa składnika (to może być prosta zmienna/sygnał lub dowolnie rozbudowane wyrażenie w nawiasach), istotne jest, że po realizacji wszystkich operacji wymaganych w zapisie składnika, zredukuje się to do jednej wartości logicznej, dla której należy wykonać negację logiczną. Bez względu na to, czy jest operator jednoargumentowy (NOT), czy go nie ma, na „stosie” znajduje się jedna sztuka sygnału logicznego (o stosie napiszę dalej). W dalszej kolejności zapamiętany jest addytywny operator logiczny i następuje analiza wyrażenia, kolejnego składnika. Obróbka składnika (dowolnie skomplikowanego) daje na stosie drugi argument. Mając niejako przygotowane dwa argumenty (operandy do addytywnej funkcji logicznej), generowane jest polecenie obliczenia nowej wartości zgodnie z zapamiętanym operatorem logicznym. To „utylizuje” dwa argumenty i jako wynik pozostawia na stosie jeden argument. Jeżeli w wyrażeniu napotkany jest kolejny addytywny operator, to następuje znów analiza składnika (co daje na stosie drugi argument) i dodane jest wykonanie addytywnej operacji logicznej.
Z kolei analiza składnika, jako ciągu czynników połączonych operatorem multiplikatywnym, wymaga podobnego podejścia. Kawałek softu:

Kod: Zaznacz cały

    procedure AdditiveExpression ;
      var
        MultOperator    : SymbolType ;

    begin (* AdditiveExpression *)
      MultiplicativeExpression ;
      while ( Symbol = LogicAndOpSy ) do
      begin (* 1 *)
        MultOperator := Symbol ;
        Symbol := ReadSymbol ;
        MultiplicativeExpression ;
        RPNAddOperator ( MultOperator ) ;
      end (* 1 *) ;
    end (* AdditiveExpression *) ;
Analiza czynnika (który daje jeden argument), zapamiętanie operatora multiplikatywnego oraz analiza drugiego czynnika (dającego drugi argument). Oba argumenty są „utylizowane” operatorem multiplikatywnym dającym znów jeden argument na stosie. Wystąpienie kolejnego operatora multiplikatywnego wymaga „wciągnięcia” kolejnego czynnika, co (do już istniejącego na stosie argumentu) daje drugi argument. Ta para zostaje „zutylizowana” operatorem multiplikatywnym dając znów na stosie jedną sztukę wartości logicznej.
Tu warto zauważyć, że przy takim podejściu wyższy priorytet mają operacje multiplikatywne (iloczynu) nad operacjami addytywnymi (sumy) bez konieczności wstawiania nawiasów, których użycie może zmienić kolejność wykonywanych działań. Czyli: A or B and C or D zostanie zrealizowana jako: A or ( B and C ) or D, dodanie nawiasów (choć nie są konieczne, ale nie przeszkadzają) nie zmienia kolejności operacji. Kolejność działań jest niejako wkompilowana w algorytm.
Wspomniałem wyżej o stosie. To typowa struktura w swej filozofii identyczna jak stos w prockach, struktura typu LIFO (Last In, First Out). Jak to działa?
Niech będzie wyrażenie:
(A or B or C) and (D or E) and (F or G)
Analiza tego wyrażenia wygeneruje:
A B or C or D E or and F G or and
Interpretując ten zapis (wykonując występujące operacje) mamy:
  • A B or C or D E or and F G or and → A na stos {stos[1] to A},
  • B or C or D E or and F G or and → B na stos {stos[1] to A, stos[2] to B},
  • or C or D E or and F G or and → zdjąć ze stosu dwa argumenty, wykonać operację or i wynik włożyć na stos {stos[1] to wynik A or B},
  • C or D E or and F G or and → C na stos {stos[1] to wynik A or B, stos[2] to C},
  • or D E or and F G or and → zdjąć ze stosu dwa argumenty, wykonać operację or i wynik włożyć na stos {stos[1] to wynik A or B or C},
  • D E or and F G or and → D na stos {stos[1] to wynik A or B or C, stos[2] to D},
  • E or and F G or and → E na stos {stos[1] to wynik A or B or C, stos[2] to D, stos[3] to E},
  • or and F G or and → zdjąć ze stosu dwa argumenty, wykonać operację or i wynik włożyć na stos {stos[1] to wynik A or B or C, stos[2] to D or E},
  • and F G or and → zdjąć ze stosu dwa argumenty, wykonać operację and i wynik włożyć na stos {stos[1] to wynik (A or B or C)and (D or E)},
  • F G or and → F na stos {stos[1] to wynik (A or B or C)and (D or E), stos[2] to F},
  • G or and → G na stos {stos[1] to wynik (A or B or C)and (D or E), stos[2] to F, stos[3] to G},
  • or and → zdjąć ze stosu dwa argumenty, wykonać operację or i wynik włożyć na stos {stos[1] to wynik (A or B or C)and (D or E), stos[2] to F or G},
  • and → zdjąć ze stosu dwa argumenty, wykonać operację and i wynik włożyć na stos {stos[1] to wynik (A or B or C)and (D or E)and(F or G)}.
Po wykonaniu wszystkich operacji zapisanych w notacji odwrotnej polskiej, na stosie musi znajdować się jeden argument → wynik.
Wyjaśniony wyżej algorytm to:

Kod: Zaznacz cały

function TLogicExpressionForm.CalculateLogicExpression ( Expression : ReversePolishNotationElemPtr ) : boolean ;
  var
    ObjEntry            : ObjectRecordPtr ;
    Element             : ReversePolishNotationElemPtr ;
    Arguments           : array [ 0 .. 15 ] of boolean ;
    Arg1                : boolean ;
    Arg2                : boolean ;
    Index               : integer ;
    ErrorFlag           : boolean ;

  procedure PutArg ( ArgValue : boolean ) ;
  begin (* PutArg *)
    if Index >= 0 then
    begin (* 1 *)
      Arguments [ Index ] := ArgValue ;
      Index := Index + 1 ;
    end (* 1 *)
    else
      ErrorFlag := True ;
  end (* PutArg *) ;

  function GetArg : boolean ;
  begin (* PutArg *)
    if Index > 0 then
    begin (* 1 *)
      Index := Index - 1 ;
      GetArg := Arguments [ Index ] ;
    end (* 1 *)
    else
    begin (* 1 *)
      ErrorFlag := True ;
      GetArg := Arguments [ 0 ] ;
    end (* 1 *) ;
  end (* PutArg *) ;

begin (* TLogicExpressionForm.CalculateLogicExpression *)
  ErrorFlag := False ;
  Index := 0 ;
  Element := Expression ;
  while Element <> nil do
  begin (* 1 *)
    case Element ^ . Operation of
      LocadConst       :
        PutArg ( Element ^ . ConstValue ) ;
      LoadVar          :
        begin (* 2 *)
          ObjEntry := FindObject ( Element ^ . ObjectName ) ;
          if ObjEntry = nil then
            PutArg ( False )
          else
            PutArg (  ObjEntry ^ . Value ) ;
        end (* 2 *);
      LogicAnd         :
        begin (* 2 *)
          Arg1 := GetArg ;
          Arg2 := GetArg ;
          PutArg ( Arg2 and Arg1 ) ;
        end (* 2 *) ;
      LogicOr          :
        begin (* 2 *)
          Arg1 := GetArg ;
          Arg2 := GetArg ;
          PutArg ( Arg2 or Arg1 ) ;
        end (* 2 *) ;
      LogicExOr        :
        begin (* 2 *)
          Arg1 := GetArg ;
          Arg2 := GetArg ;
          PutArg ( Arg2 xor Arg1 ) ;
        end (* 2 *) ;
      LogicNot         :
        begin (* 2 *)
          Arg1 := GetArg ;
          Arg2 := not Arg1 ;
          PutArg ( Arg2 ) ;
        end (* 2 *) ;
    end (* case *) ;
    Element := Element ^ . FwdLink ;
  end (* 1 *) ;
  if Index <> 1 then
    ErrorFlag := True ;
  if ErrorFlag then
    CalculateLogicExpression := False
  else
    CalculateLogicExpression := GetArg ;
end (* TLogicExpressionForm.CalculateLogicExpression *) ;
A takie wyrażenia:
A or (B or (C or (D or (E or (F or G)))))
W myśl definicji wyrażenia mamy wyrażenie proste [A] i wyrażenie proste [(B or (C or (D or (E or (F or G)))))] połączone operatorem or. Daje to w notacji odwrotnej polskiej element A, element (B or (C or (D or (E or (F or G))))) oraz operator or. Jednak zanim do notacji trafi operator or, wcześniej zostanie rozpracowane wyrażenie proste. Oczywista, zajdzie rekurencja. Finalnie wyjdzie:
A B C D E F G or or or or or or
A jego interpretacja zostanie zrealizowana następująco:
logic5.png
Nie masz wymaganych uprawnień, aby zobaczyć pliki załączone do tego posta.

Prawdziwe słowa nie są przyjemne. Przyjemne słowa nie są prawdziwe.
Lao Tse


Wróć do „DIY”

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 3 gości