Odwrotna notacja polska: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m →Algorytm obliczenia wartości wyrażenia ONP: kolejność w zapisie konwencjonalnym dostosowana do ONP w przykłądzie |
m WP:SK, drobne techniczne |
||
Linia 1:
{{Wikisłownik|ONP|RPN}}
{{dopracować|źródła=2019-09}}
'''Odwrotna notacja polska''' (ONP, {{ang.|reverse Polish notation, RPN}}) – 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 ([[Notacja infiksowa|zapis infiksowy]]) lub przed operandami jak w zwykłej [[notacja polska|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ń.
Linia 31 ⟶ 32:
'''Przykład'''
: Wyrażenie w zapisie konwencjonalnym: 12+2·(3·4+10/5)
: Wyrażenie ONP: 12 2 3 4 * 10 5 / + * +
: Gdy wczytany element jest liczbą, to zapisuje się ją na stos. W przeciwnym wypadku należy wykonać działanie arytmetyczne na 2 ostatnich liczbach na stosie. Wartość wyrażenia znajduje się na stosie.
:{| class="wikitable" style="text-align: center"
Linia 62 ⟶ 63:
|}
: Wartość wyrażenia: '''40'''
== Algorytm konwersji z notacji infiksowej do ONP (rekurencyjny) ==
Linia 202 ⟶ 203:
* '''+''', '''-''', '''*''', '''/''', '''%, ^'''. Jeżeli priorytet operatora wczytywanego jest wyższy od priorytetu operatora znajdującego się w wierzchołku stosu lub stos jest pusty, to dopisz do stosu operator, a w przeciwnym razie odczytaj i prześlij na wyjście kolejne operatory z wierzchołka stosu o priorytecie większym lub równym priorytetowi wczytanego operatora, po czym wpisz do stosu operator.
Na koniec, gdy wszystkie elementy zostały wczytane należy zdjąć wszystkie operatory ze stosu i przesłać je na wyjście.
; <nowiki>Przykład :</nowiki>
Wyrażenie: '''12 + a * (b * c + d / e)'''
| |||