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.

Komentarze