ONP - co to jest i jak działa
Odwrotna notacja polska
Zapis wyrażenia algebraicznego, w którym między dwoma operandamioperandami umieszczamy operator, nazywamy zapisem infiksowymzapisem infiksowym.
Oto przykładowe działanie dodawania w zapisie infiksowym:
W 1920 r. polski logik i matematyk Jan Łukasiewicz opracował notację polską, czyli sposób zapisu, w którym na początku stawiamy znak, a następnie operandy. Dzięki takiemu zapisywaniu wyrażeń, nie ma już konieczności używania nawiasów, w celu zmiany kolejności wykonywania działań.
Oto ta sama operacja dodawania, ale zapisana za pomocą notacji polskiej:
Taki sposób zapisu nazywamy też prefiksowymprefiksowym.
Tematem tego e‑materiału jest jednak odwrotna notacja polska, inaczej nazywana zapisem postfiksowymzapisem postfiksowym. Wyrażenia zapisujemy w taki sposób, że znak stawiamy na końcu.
Oto przykładowa operacja dodawania, zapisana za pomocą odwrotnej notacji polskiej:
Zastosowanie odwrotnej notacji polskiej
Sposoby zapisu wyrażeń, takie jak notacja polska lub odwrotna notacja polskaodwrotna notacja polska (ONP), używane są głównie w informatyce. Jest to związane z optymalizacją pracy komputera – zachowanie kolejności wykonywania działań, bez wykorzystania nawiasów, znacznie ułatwia obliczenia.
Przedstawione wyrażenie zapisane jest klasycznym sposobem infiksowym.
W celu zmiany kolejności wykonywania działań użyto nawiasów. W odwrotnej notacji polskiej nie są one potrzebne. To samo wyrażenie w ONP wygląda następująco:
Konwersja wyrażenia zapisanego sposobem klasycznym na zapis w odwrotnej notacji polskiej
W jaki sposób dokonać konwersji wyrażenia w zapisie klasycznym na postać w odwrotnej notacji polskiej?
W algorytmie będziemy wykorzystywali stosstos,, na którym umieścimy operatory i nawiasy z wyrażenia. Niezbędne okażą się także informacje na temat łączności danego operatora (czy jest lewostronny, czy prawostronny), a także ich priorytety. Informacje te przedstawia następująca tabela:
Operator | Łączność | Priorytet |
|---|---|---|
| prawostronna | 3 |
| lewostronna | 2 |
| lewostronna | 1 |
Operator ^ oznacza operację potęgowania.
Priorytet operatora oznacza, które działanie jest ważniejsze i powinno zostać wykonane jako pierwsze. Operacja potęgowania ma priorytet 3, co oznacza, że ma pierwszeństwo przed mnożeniem, dzieleniem, dodawaniem i odejmowaniem.
W przypadku, gdy w wyrażeniu występują operatory o tym samym priorytecie, łączność operatorów pomaga w zinterpretowaniu kolejności wykonywania działań. Łączność lewostronna oznacza, że działania w zapisie infiksowym powinny być wykonywane od lewej do prawej:
Operatory dodawania i odejmowania mają ten sam priorytet i łączność lewostronną, wykonujemy zatem najpierw działanie dodawania, a następnie odejmowania.
W przypadku łączności prawostronnej wykonujemy działania od strony prawej:
Algorytm konwersji wyrażenia w zapisie klasycznym, na postać w odwrotnej notacji polskiej, przedstawia się w kilku krokach.
Specyfikacja problemu:
Dane:
infiksowy– łańcuch znaków; zapis infiksowy wyrażenia arytmetycznego
Wynik:
Wyrażenie infiksowy zapisane w odwrotnej notacji polskiej.
Słownik
inaczej: zapis postfiksowy; sposób zapisu wyrażeń arytmetycznych, w którym operator umieszczany jest po operandach
liczba, na której wykonywane jest działanie
struktura danych, o dostępie jednostronnym. Dane są odkładane na wierzchołek i z niego zdejmowane, co oznacza, że bezpośrednio ze stosu możemy pobrać tylko ostatni odłożony element. Mówimy, że dostęp do stosu jest typu LIFO: Last In First Out.
sposób zapisu wyrażeń, w którym operator jest stawiany między operandami, na których chcemy wykonać daną operację
sposób zapisu wyrażeń, w którym operator jest stawiany po operandach, na których chcemy wykonać daną operację; w tej notacji nie stosuje się nawiasów
sposób zapisu wyrażeń, w którym operator jest stawiany przed operandami, na których chcemy wykonać daną operację; w tej notacji nie stosuje się nawiasów