artykuły

Interpreter równań - czyli Odwrotna Notacja Polska i sposób konwersji zapisu infiksowego na postfiksowy

20:49
pon, 22 wrzesień 2008
Czy nie zastanawiałeś się nigdy jak działają rozbudowane, zaawansowane kalkulatory, w których wystarczy wprowadzić równanie w całości, a one od razu dają jego wynik? Jeśli tak, odpowiedź na to jak działa taki kalkulator znajdziesz w tym artykule.

Wstęp

Chyba każdy z młodych programistów zastanawiał się kiedyś jak działają rozbudowane, zaawansowane kalkulatory, w których działania podaje się w całości, w postaci równania, a one to po prostu obliczają. Jak obliczyć równanie podane w postaci ludzkiej (czyli w tzw. zapisie infiksowym), przykładowo takie:

    3+4+8*(3*2)=55

Co oznacza zapis infiksowy, a co postfiksowy?

Zapis infiksowy to nic innego jak znany nam (ludziom) zapis wyrażeń matematycznych w postaci równania, gdzie operatory (znaki dodawania, mnożenia, itp.) stoją pomiędzy operandami (liczbami).
Główną różnicą jaką można zauważyć na pierwszy rzut oka, jest fakt, że w zapisie postfiksowym operatory stoją po operandach. Przykład już za chwilę.

Trochę więcej szczegółów

Jeśli interesuje Cię napisanie programu wykorzystującego podane tu metody, radzę pisać taki program w dwóch częściach. Najlepiej najpierw napisać program który zinterpretuje i obliczy równanie zapisane odwrotną notacją polską (RPN), a gdy już ten moduł będzie działać, należy napisać procedurę która odwróci zapis ludzki na odwrotną notację, a tą z kolei poda do funkcji obliczającej odwrotną notację polską (która będzie Ci już działała). Takie postępowanie pozwala zaoszczędzić mnóstwo czasu na szukanie trudnych do wykrycia błędów.
Ze swojej strony powiem, że sposób podany w tym artykule jest bardzo wygodny jeśli obliczamy równanie iteracyjnie. Jest bardzo szybki, wykorzystuje stos (na którym odkłada elementy do przeprowadzenia operacji) i jego implementacja pochłania ok. 1 strony A4 kodu (może troszkę więcej). Troszkę gorzej jest z zamianą normalnego ludzkiego zapisu na zapis w odwrotnej notacji polskiej, ale również i to postaramy się ujarzmić w tym artykule.

Pokaże Ci przykład działania. Dwa wyrażenia - jedno zapisane normalnie, drugie w odwrotnej notacji polskiej:

Mamy równanie:

3+4+8*(3*2)=55

Sposób konwersji zwykłego wyrażenia na Odwrotną Notację Polską

W odwrotnej notacji będzie to wyglądało tak:

Tabela 1.0 - Sposób konwersji na Odwrotną Notację Polską
Przebieg Wejście Stos Wyjście
1 3 # 3
2 + +,#
3 4 +,# 4
4 + +,# +
5 8 +,# 8
6 * *,+,#
7 ( (,*,+,#
8 3 (,*,+,# 3
9 * *,(,*,+,#
10 2 *,(,*,+,# 2
11 ) *,+,# *
12 +,# *
13 # +

Jak to zrobiłem? Czytam równanie od lewej do prawej, operatory odkładam na stos, a liczby na wyjście. Jeśli natrafię na liczbę - nie przejmuje się niczym i odkładam ją na wyjście, jeśli natomiast natrafię na operator to mam dwa przypadki:

  1. Jeśli ostatnim operatorem na stosie jest operator o niższym priorytecie (np. dodawanie ma priorytet niższy niż mnożenie) to odkładam operator na stos.
  2. Jeśli ostatnim operatorem na stosie jest operator o wyższym lub takim samym priorytecie to przenoszę operatory ze stosu na wyjście do momentu w którym natrafię na niższy operator. Jeśli wreszcie natrafiłem na niższy operator (albo na koniec stosu) to odkładam go wreszcie na stos i idę dalej.

Jest jeszcze kwestia z nawiasami. To osobna grupa operatorów, którą dotyczą trochę inne prawa. Mianowicie, jeśli napotkam nawias otwierający "(" to choćby nie wiem co - odkładam go na stos. Jeśli natomiast napotkam nawias zamykający ")" to NIE odkładam go na stos, ale przenoszę ze stosu na wyjście wszystkie operatory do momentu w którym nie napotkam na jakikolwiek nawias otwierający "(". OK. Tyle.

Teraz przepisujemy ów rozłożone powyżej w tabelce wyrażenie od góry do dołu:

3  4 + 8  3  2 * * +

no i tym sposobem mamy zamienione równanie w zapisie ludzkim na zapis odwrotnej notacji polskiej. Dzięki odwrotnej notacji polskiej komputer nie musi skakać po równaniu i patrzyć który nawias jest najważniejszy, który jest drugi w kolejności itp... po prostu aby to teraz policzyć należy wykonać zapis krok po kroku pamiętając o kilku rzeczach (odsyłam do Wikipedii). Najlepsze w tym wszystkim jest to, że gdyby ludzie używali odwrotnej notacji polskiej, to nie istniałoby zapotrzebowanie na nawiasy ! Tak, one są zbędne w tym zapisie! Kolejność wykonywania działań jest z góry ustalona i jednoznaczna.

Obliczyłem to przy okazji na szybko:

3  4 + 8  3  2 * * + = 7  8  3  2 * * + = 7  8  6  *  + = 7  48  + = 55

Jak to zrobiłem - czyli (obliczenia krok po kroku) - [obliczanie odwrotnej notacji polskiej]

3  4  +  8  3  2  *  *  +

Reguła jest taka: jeśli spotykamy liczby to odkładamy je na stos, a jeśli napotykamy operator to zdejmujemy tyle liczb ile obsługuje operator ( w wypadku +,-,/,* są to dwie liczby, ponieważ wymienione operatory są dwuargumentowe), a wynik odkładamy na stos. Więc...

  1. Odkładamy kolejne liczby na stos dopóki nie spotkamy operatora (u nas pierwszym napotkanym jest +) więc na stosie mamy liczby 3 i 4, z kolei kursor naszego wyrażenia stanął przy operatorze + (a trzeba pamiętać, że jest to OPERATOR DWUARGUMENTOWY! ), dlatego zabieramy ze stosu dwa argumenty (nasze liczby 3 i 4) i wykonujemy operację zadaną przez operator +, czyli dodawanie i wynik odkładamy na stos. Na stosie mamy liczbę 7. Idziemy dalej...
  2. Odkładamy na stos liczby 8, 3 oraz 2 i napotykamy operator * - jest on dwuargumentowy, więc zdejmujemy ze stosu dwie ostatnie liczby ( w naszym wypadku są to liczby 2 oraz 3) i wykonujemy mnożenie (wychodzi 6), wynik odkładamy na stos. Na stosie mamy liczby 7, 8 i 6. (liczba 8 pozostała, ponieważ operacja mnożenia w niniejszym kroku wymagała jedynie dwóch liczb: 3 i 2, więc 8 zostało na stosie)
  3. Znowu napotykamy operator * - jest on dwuargumentowy, więc zdejmujemy ze stosu dwie ostatnie liczby (6 oraz 8) i wykonujemy mnożenie. Obliczony wynik (48) umieszczamy na stosie. Na stosie mamy teraz liczby 7 i 48.
  4. Napotykamy operator + - jest on dwuargumentowy, więc zdejmujemy ze stosu dwie ostatnie liczby (7 i 48) i wykonujemy operacje dodawania. Otrzymujemy wynik 55 i umieszczamy go na stosie.
  5. Na stosie jest teraz jedna liczba będąca rozwiązaniem równania.

Zakończenie

Starałem się aby opisać zagadnienie przystępnie. Jeśli jednak coś nie jest dla Was zrozumiałe - piszcie. Na zakończenie podam tylko adresy stron, z których możecie dowiedzieć się jeszcze więcej:

12345
Interpreter równań - czyli Odwrotna Notacja Polska i sposób konwersji zapisu infiksowego na postfiksowy Autor opinii: Czytelnicy, data przesłania: 5

Skomentuj

Aby zamieścić komentarz, proszę włączyć JavaScript - niestety roboty spamujące dają mi niezmiernie popalić.






Komentarze czytelników

    • Adam C.
    • wto, 2 luty 2010, 15:27
    • Gdyby internet składał się z tekstów na takim poziomie świat byłby lepszy.

      Dzięki wielkie.
    • Adam
    • nie, 8 listopad 2009, 20:20
    • Bardzo przystępnie kolego. Dzięki.
    • Damian
    • pią, 23 październik 2009, 2:36
    • Kolego, dziękuję. Właśnie czegoś takiego szukałem.
    • Lukas
    • śro, 4 luty 2009, 17:46
    • Słuszna uwaga.
    • Olek
    • śro, 17 grudzień 2008, 14:07
    • Świetny artykuł, dzięki niemu zrobiłem spory projekt kalkulatora do liczenia wyrażeń w C#, który mam zamiar wykorzystać w programie liczącym pole pod wykresem dowolnej funkcji, i przedstawiającym to pole graficznie. Pasowało by dodać coś o minusie przed liczbami, bo zapis -3+6 na pewno nie zadziała dobrze w tej wersji, trzeba zamieniać na (0-3)+6. Bardzo rozbudowanym tematem jest też kontrola wejścia...
Dexter