Przeczytaj

Odwrotna notacja polska

Zapis wyrażenia algebraicznego, w którym między dwoma operandamioperandoperandami umieszczamy operator, nazywamy zapisem infiksowymzapis infiksowyzapisem infiksowym.

Oto przykładowe działanie dodawania w zapisie infiksowym:

$2 + 3$

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:

$+2\ \ 3$

Taki sposób zapisu nazywamy też prefiksowymzapis prefiksowyprefiksowym.

Tematem tego e‑materiału jest jednak odwrotna notacja polska, inaczej nazywana zapisem postfiksowymzapis postfiksowyzapisem 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:

$2\ \ 3+$

Zastosowanie odwrotnej notacji polskiej

Sposoby zapisu wyrażeń, takie jak notacja polska lub odwrotna notacja polskaodwrotna 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.

$(2+3)\div5\cdot(2+7)$

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:

$2\ \ 3+5\div2\ \ 7+\cdot$

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 stosstosstos, 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:

a + b - c = (a + b) - c

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:

a^{b^{c}} = a^{(b^{c})}

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.

Krok 1. Jeśli jest element wyrażenia infiksowy do odczytania, wykonuj (jeśli nie, przejdź do kroku 7):

Krok 2. Jeśli element jest liczbą/zmienną, przekaż go na standardowe wyjście. Jeśli nie, przejdź do kroku 3.

Krok 3. Jeśli element jest operatorem, wykonuj (jeśli nie, przejdź do kroku 4):

Krok 3.1. Jeśli na szczycie stosu znajduje się operator, wykonuj (jeśli nie, przejdź do kroku 3.2):

Krok 3.1.1. Jeśli odczytany operator ma łączność lewostronną oraz priorytet nie większy niż priorytet operatora na szczycie stosu lub jeśli operator ma łączność prawostronną oraz priorytet mniejszy od priorytetu operatora na szczycie stosu, zdejmij operator ze szczytu stosu, umieść go na standardowym wyjściu i przejdź do kroku 3.1.

Krok 3.2. Umieść odczytany operator na szczycie stosu.

Krok 4. Jeśli element jest nawiasem otwierającym, umieść go na szczycie stosu. Jeśli nie, przejdź do kroku 5.

Krok 5. Jeśli element jest nawiasem zamykającym, wykonuj (jeśli nie, przejdź do kroku 6):

Krok 5.1. Jeśli na szczycie stosu nie znajduje się nawias otwierający, wykonuj (jeśli tak, przejdź do kroku 5.2):

Krok 5.1.1. Zdejmij operator z góry stosu, umieść go na wyjściu i wróć do kroku 5.1.

Krok 5.2. Zdejmij nawias otwierający. Nie przekazuj go na wyjście. Przejdź do kroku 6.

Krok 6. Wróć do kroku 1.

Krok 7. Zdejmij wszystkie operatory ze stosu i przekaż je kolejno na standardowe wyjście.

Słownik

odwrotna notacja polska

inaczej: zapis postfiksowy; sposób zapisu wyrażeń arytmetycznych, w którym operator umieszczany jest po operandach

operand

liczba, na której wykonywane jest działanie

stos

struktura danych, w której dane są odkładane na szczyt stosu i z niego zdejmowane, co oznacza, że bezpośrednio ze stosu możemy pobrać tylko ostatni odłożony element

zapis infiksowy

sposób zapisu wyrażeń, w którym operator jest stawiany między operandami, na których chcemy wykonać daną operację

zapis postfiksowy

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

zapis prefiksowy

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

Wprowadzenie

Prezentacja multimedialna

Odwrotna notacja polska

Zastosowanie odwrotnej notacji polskiej

Konwersja wyrażenia zapisanego sposobem klasycznym na zapis w odwrotnej notacji polskiej

Słownik