Odwrotna Notacja Polska: Definicja, Algorytmy i Przykłady
- Szczegóły
„Odwrotna Notacja Polska” (ONP, ang. Reverse Polish Notation, RPN) to po prostu inny sposób zapisywania wyrażeń arytmetycznych czy też algorytmów. Polega ona w dużym skrócie na prostszym zapisie wyrażeń arytmetycznych bez nawiasów z zachowaniem kolejności wykonywania działań.
Spis treści:
- Definicja Odwrotnej Notacji Polskiej
- Algorytm konwersji wyrażeń z ONP do postaci infiksowej
- Przykład praktyczny konwersji z ONP do INF
- Algorytm obliczania wyrażeń ONP
- Wykorzystanie ONP w języku C++
- Zalety Odwrotnej Notacji Polskiej
Definicja Odwrotnej Notacji Polskiej
W notacji polskiej wyrażeń arytmetycznych, operatory piszemy przed ich argumentami. Ściślej: możemy zapisać wyrażenie arytmetyczne w postaci funkcyjnej, stosując alternatywną notację z początku notatek. Wtedy wyrażenie $2+2$ zapiszemy jako $(2,2)+$, natomiast $a \cdot (2 + b)$ jako $(a, (2, b)+)\cdot$.
Gdy opuścimy te symbole, otrzymamy zapis wyrażenia w odwrotnej notacji polskiej (ONP; ang. Reverse Polish Notation, RPN). Wyrażenia ONP możemy wyliczać tak, jak odpowiadające im postacie funkcyjne.
Odwrotna Notacja Polska (ONP), lub Reverse Polish Notation (RPN), to notacja postfiksowa, która charakteryzuje się umieszczaniem operatora zawsze po jego operandach. Jej fundamentalna siła tkwi w tym, że kolejność wykonywania operacji jest narzucona przez samą kolejność tokenów.
To eliminuje wszelkie niejednoznaczności typowe dla notacji infiksowej, takie jak konieczność zapamiętywania hierarchii priorytetów (* > +) czy stosowania nawiasów w celu wymuszenia kolejności. Przetwarzanie ONP odbywa się sekwencyjnie, od lewej do prawej, a jej natywna zgodność ze strukturą stosu sprawia, że jest to najprostszy format do obliczania przez maszynę.
Przeczytaj także: Sterowniki i usterki ASUS K52J
Geneza ONP, sięgająca pracy polskiego logika Jana Łukasiewicza (Notacja Polska, czyli prefiksowa), została spopularyzowana przez Charlesa Hamblina, który dostrzegł, że notacja postfiksowa (odwrotna) doskonale pasuje do architektury komputerów opartych na stosie, zyskując tym samym przydomek RPN. To historyczne połączenie logiki i informatyki jest dowodem na głębokie teoretyczne podstawy tej metody.
Algorytm Konwersji Wyrażeń z ONP do Postaci Infiksowej
Zwykła konwersja z ONP do postaci infiksowej (używanej na co dzień) nie jest zbytnio skomplikowana. Algorytm konwersji wyrażeń z Odwrotnej Notacji Polskiej do postaci infiksowej w dużym uproszczeniu polega na wczytywaniu pojedynczych znaków z wejścia. Jeżeli wczytaną daną jest liczba, program powinien odłożyć ją na stos i przejść dalej do momentu natrafienia na działanie arytmetyczne. Wtedy należy ściągnąć ze stosu jego argumenty i wypisać na wyjście podziałanie.
Przykład Praktyczny Konwersji z ONP do INF
Rozpatrzmy jako przykład wyrażenie pokazane wyżej, czyli 6/2⋅(2+1)6/2 \cdot (2+1). W ONP wygląda ono następująco: 6 2 / 2 1 + ⋅6 \text{ } 2 \text{ } / \text{ } 2 \text{ } 1 \text{ } + \text{ } \cdot
Algorytm Obliczania Wyrażeń ONP
Wyrażenia ONP możemy wyliczać tak, jak odpowiadające im postacie funkcyjne. Wyliczając wartość operacji w wyrażeniu ONP trzeba znać wartość jego argumentów.
Teraz przetłumaczymy powyższą procedurę na algorytm, którego wejściem jest ciąg tokenów kodujący wyrażenie ONP. Niech w naszym algorytmie liczby z lewej strony kreski będą reprezentowane przez stos (rosnący od lewej, do prawej).
Przeczytaj także: Zastosowanie wężyków do filtra osmozy
Algorytm na wejściu przyjmuje wyrażenie w ONP (dla uproszczenia załóżmy, że mamy je rozdzielone na tablicę poszczególnych symboli). Liczby odkładamy na stos, a trafiając na coś, co nie jest liczbą (operator lub funkcja), odczytujemy ze stosu odpowiednią liczbę elementów. Po obliczeniu wyniku odkładamy go na stos.
Poniżej znajduje się przykład działania algorytmu dla wyrażenia 2 5 + 3 *:
| Wejście | Skanowany symbol | Stos | Komentarz |
|---|---|---|---|
| 2 5 + 3 * | Brak | Pusty | Start |
| 2 5 + 3 * | 2 | 2 | Wrzucamy 2 na stos |
| 5 + 3 * | 5 | 2, 5 | Wrzucamy 5 na stos |
| + 3 * | + | 7 | Zdejmujemy 5 i 2 ze stosu, sumujemy i wrzucamy na stos |
| 3 * | 3 | 7 3 | Wrzucamy 3 na stos |
| * | * | 21 | Zdejmujemy 3 i 7 ze stosu, mnożymy i wrzucamy na stos. |
| Brak | Brak | Pusty | Koniec |
Wykorzystanie ONP w Języku C++
Nawiązując do artykułu o Odwrotna notacja polska chciałbym przedstawić jak można wykorzystać ją w praktyce, na przykładzie języka C++. Nie będę się ponownie rozwodził jak się to wykonuje, bo zostało to już opisane. Cała esencja polega na tym, że nie musimy wyrażenia arytmetycznego przerabiać najpierw na RPN a później obliczać. Wszystko możemy wykonać za jednym zamachem.
W programie wykorzystujemy dwa stosy - jeden na liczby (najlepiej zmiennoprzecinkowe), drugi na znaki arytmetyczne. I teraz od lewej bierzemy dwójkę na stos z liczbami, dalej znak mnożenia na stos ze znakami arytmetycznymi, znowu dwa na stos i dalej znak plus. Na stosie ze znakami jest mnożenie, czyli wyższy priorytet od dodawania. Dalej dwa znowu na stos i koniec.
Argumentem funkcji jak widać jest dana typu string, w której opisane jest równanie. Jest to dość prosty kalkulator, gdyż operuje na następnych znakach arytmetycznych: + - * / (potęga, która też może być pierwiastkowaniem - np.
Przeczytaj także: Odwrócona osmoza: Twój przewodnik
Zalety Odwrotnej Notacji Polskiej
ONP ma sporo zalet nad zwykłą notacją: brak nawiasów, brak priorytetów operatorów (działania można wykonywać od lewej do prawej), łączność operacji jest nieistotna.
Odwrotna notacja polska jest bardzo użyteczną formą zapisu wyrażeń matematycznych, ponieważ pozwala w prosty sposób policzyć ich wynik.
tags: #odwrocona #notacja #polska #definicja
