algorytm.org

Odwrotna Notacja Polska

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Odwrotna Notacja Polska
Ocena użytkowników:***** / 19
SłabyŚwietny 
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:
  • 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
Po zakończeniu wczytywania wyrażenia wypisujemy ze stosu wszystko, co na nim zostało.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiAda
.ada
.ada
***** / 2
MarianC/C++C++
.cpp
.cpp
***** / 36
Michał KnasieckiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 5
Tomasz LubińskiJava
.java
.java
***** / 10
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 maja 2010 22:26
Komentarze
photo
0 # 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ć
photo
+8 # mateo 2011-10-10 17:56
a nie powinno byc na odwrot z ta dwojka i trojka?!
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz