Wpisany przez Michał Knasiecki,
26 lipca 2005 23:39
Notacja infiksowa to notacja, którą posługujemy się na co dzień. Składa się ona z dwóch operand (liczb, zmiennych) oraz operatora, który znajduje się między nimi np: 2+4 albo x*7 itd. W tak zapisanym wyrażeniu ważny jest priorytet operatora a nie jego kolejność. Oto priorytety w notacji infiksowej:
1). Nawias
2). Dodawanie i odejmowanie
3). Mnożenie i dzielenie
W Odwrotnej Notacji Polskiej jest inaczej. Nie jest ważny priorytet operatora, a jego kolejność. Jest to bardzo przydatne w realizacji translatorów, które zdejmują kolejne operandy ze stosu, wykonują operacje i wynik odkładają na stosie. 2+4 w ONP wygląda następująco: 2 4 +. Widać, że operator poprzedzony jest operandami. Uwaga! Zrozumienie algorytmu wymaga zapoznania się ze strukturą stosu. A oto sposób zamiany wyrażenia zapisanego w notacji infiksowej na ONP: Czytamy wyrażenie od lewej strony i jeżeli natrafimy w nim na:
1). Nawias
2). Dodawanie i odejmowanie
3). Mnożenie i dzielenie
W Odwrotnej Notacji Polskiej jest inaczej. Nie jest ważny priorytet operatora, a jego kolejność. Jest to bardzo przydatne w realizacji translatorów, które zdejmują kolejne operandy ze stosu, wykonują operacje i wynik odkładają na stosie. 2+4 w ONP wygląda następująco: 2 4 +. Widać, że operator poprzedzony jest operandami. Uwaga! Zrozumienie algorytmu wymaga zapoznania się ze strukturą stosu. A oto sposób zamiany wyrażenia zapisanego w notacji infiksowej na ONP: Czytamy wyrażenie od lewej strony i jeżeli natrafimy w nim na:
- liczbę lub zmienną - wypisujemy ją na wyjściu
- nawias otwierający - kładziemy go na stosie
- operator - zdejmujemy ze stosu i wypisujemy na wyjściu wszystkie operatory priorytecie niemniejszym niż ten wczytany. Następnie kładziemy wczytany operator na stosie
- nawias zamykający - zdejmujemy ze stosu i wypisujemy na wyjściu wszystkie działania aż do napotkania nawiasu otwierającego, którego nie wypisujemy
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | Ada | .ada | .ada | ***** / 2 | |
Marian | C/C++ | C++ | .cpp | .cpp | ***** / 49 |
Michał Knasiecki | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 5 |
Tomasz Lubiński | Java | .java | .java | ***** / 12 |
Poprawiony: 26 maja 2010 22:26
Komentarze
+2
#
Bartek
2010-01-25 17:26
No wszystko fajnie, ale to nie jest kompletny algorytm. Szukam algorytmu, który będzie obsługiwał operatory prawostronnie i lewostronnie łączne (chodzi mi o takie jak silnia \'!\' i potęga \'^\'), oraz funkcje z różną ilością parametrów.
Odpowiedz | Odpowiedz z cytatem | Cytować
+10
#
mateo
2011-10-10 17:56
a nie powinno byc na odwrot z ta dwojka i trojka?!
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz