Odwrotna Notacja Polska

pytanie zadane 21 października 2018 w Matematyka, fizyka, logika przez Szymon137 Nowicjusz (180 p.)

Przejrzałem już dosyć dużo różnych stron i filmików na youtube ale dalej nie rozumiem ONP. Macie jakieś dobre wytłumaczenie tego zagadnienia?

2 odpowiedzi

odpowiedź 21 października 2018 przez Chess Szeryf (76,710 p.)
edycja 21 października 2018 przez Chess

Odwrotna notacja polska:

Najpierw są jakieś liczby, a później jest znak, który mówi nam, jakie jest wykonywane działanie.

Zapis, którego używamy na co dzień:

2 + 1 + 2 * 3

Zapis odwrotnej notacji polskiej:

2 1 + 2 3 * +

Jeśli są obok siebie dwa operatory, np. jak w tym przypadku * +, to ...

Pierwszy operator (*), który stoi najbliżej liczb stojących po lewo wykonuje działanie, czyli 2 * 3. Następnie dodawane jest wyrażenie, które stoi na samym początku, czyli 2 + 1. Końcowy rezultat, to 9.

(6/2)-3+5+(1*3)

6 2 / 3 5 + - 1 3 * +

reverse polish notation

Dzięki tej grafice, łatwo powinieneś dostrzec analogię. To co jest z prawej ma być z lewej strony, a to co jest z lewej ma być z prawej strony.

Gdybyś np. programował w Common Lisp, to byś zauważył, że to jest coś podobnego z tym operacjami matematycznymi.

Przykład z Common Lisp (notacja polska):

W Common Lisp trzeba używać nawiasów, które pomagają zrozumieć i zobaczyć jak powinno obliczać się takie wyrażenia matematyczne.

(+ 4 2 (* 1 0) (- 10 3)) => (+ 4 2 0 7) => 13

Najpierw obliczyć trzeba najbardziej zagnieżdżone nawiasy, a na końcu obliczyć całe wyrażenie.

komentarz 21 października 2018 przez Hiskiel Pasjonat (22,830 p.)

Na kija Polacy stworzyli tego potwora?

komentarz 21 października 2018 przez Chess Szeryf (76,710 p.)

ONP bardzo ułatwia wykonywanie na komputerze obliczeń z nawiasami i zachowaniem kolejności działań. Zarówno algorytm konwersji notacji konwencjonalnej (infiksowej) na odwrotną notację polską (postfiksową), jak i algorytm obliczania wartości wyrażenia danego w ONP są bardzo proste i wykorzystują stos.

Źródło: Wikipedia.

ONP - Odwrotna Notacja Polska

komentarz 21 października 2018 przez criss Mędrzec (172,590 p.)

@Hiskiel
Bo jeśli założymy, że parser dostaje wyrażenie w takiej postaci, to napisanie parsera staje się dużo prostsze. Dzięki ONP (lub RPN w ang.) pisząc parser nie musimy brać pod uwagę ani nawiasów ani kolejności wykonywania działań. A w zamian wystarczy tylko napisać konwerter wyrażeń w tradycyjnej postaci na postać RPN.