Jakub Piecuch kl. IIIc / nr 16
ODWROTNA NOTACJA POLSKA (ONP)
1. Co to jest ONP?
Jest to sposób zapisywania operacji logicznych i arytmetycznych, wywodzący się z Notacji
Polskiej, zaprezentowanej w 1920r. przez polskiego logika, matematyka i filozofa Jana
A
ukasiewicza.  Zwykła Notacja Polska jest zapisem prefixowym tj. przedrostkowym, co oznacza,
że znak operatora jest przed argumentami operacji:
* 8 / 10 + 4 - 2 1
Powyższy zapis oznacza:
POMNÓŻ 8 i wynik DZIELENIA 10 przez SUM
4 i RÓŻNICY 2 i 1
8*(10/(4+(2-1)))
Co jest bardzo istotne, zarówno w NP jak i w ONP (o czym również za chwilę) istotna jest
kolejność argumentów: - 2 1 != - 1 2.
Czym więc ONP różni się od NP?
Jak sama nazwa wskazuje, ONP to Odwrotna NP, to znaczy - argumenty operacji są przed
znakami operatorów. Dla przykładu - powyżesz wyrażenie zapisane w ONP będzie wyglądało
następująco:
2 1 - 4 + 10 / 8 *
Jest to zapis postfiksowy - gdzie operator jest zapisany po argumentach.
2. Obliczanie wartości wyrażenia zapisanego w ONP
Operacje przekształcania wyrażeń na ONP (bądz
odwrotnie) są oparte na strukturze danych zwanej
stosem. Można sobie łatwo wyobrazić, na czym polega stos - wez
my kilka książek ułożonych na
sobie i ustalmy, że za każdym razem możemy wykonać tylko jedną z takich dwóch operacji:
możemy zabrać jedną książkę z wierzchu bądz
dołożyć na wierzch jedną. W ten sposób właśnie
działa stos.
W jaki więc sposób obliczać wartość wyrażenia zapisanego w ONP?
Jako przykładowe wyrażenie wez
my to z punktu 1. Najpierw obliczmy jego wartość:
8*(10/(4+(2-1)))=8*(10/(4+1))=8*2=16
Sam algorytm na obliczanie wartości wyrażenia w ONP można opisać następująco:
Odczytujemy kolejne elementy wyrażenia w ONP. Jeżeli dany element jest
liczbą, odkładamy go na stos; jeżeli jest operatorem, bierzemy ze stosu
dwie liczby i wykonujemy na nich daną operację, a wynik odkładamy na
stosie.
Najłatwiej zobaczyć o co chodzi za pomocą tabelki. Obliczymy wartość wyrażenia
2 1 - 4 + 10 / 8 *
Krok Wejście Stos
1 2 2
2 1 1 2
3 - 1
4 4 4 1
5 + 5
6 10 10 5
7 / 2
8 8 8 2
9 * 16
Żródła:
1) Wikipedia
2) http://edu.i-lo.tarnow.pl/inf/utils/010_2010/0410.php
3) http://edu.i-lo.tarnow.pl/inf/alg/001_search/0102.php