Odwrotna Notacja Polska (ONP) – Ustrukturyzowany

Definicja i zaawansowane zasady działania ONP

Odwrotna Notacja Polska (ONP), lub Reverse Polish Notation (RPN), to notacja postfiksowa, która charakteryzuje się umieszczaniem operatora zawsze po jego operandach. Jej fundamentalna siła tkwi w tym, że kolejność wykonywania operacji jest narzucona przez samą kolejność tokenów. To eliminuje wszelkie niejednoznaczności typowe dla notacji infiksowej, takie jak konieczność zapamiętywania hierarchii priorytetów (* > +) czy stosowania nawiasów w celu wymuszenia kolejności. Przetwarzanie ONP odbywa się sekwencyjnie, od lewej do prawej, a jej natywna zgodność ze strukturą stosu sprawia, że jest to najprostszy format do obliczania przez maszynę. Każdy napotkany operator po prostu „konsumuje” niezbędne argumenty znajdujące się na szczycie stosu, wykonuje operację i umieszcza wynik z powrotem, gotowy do dalszych obliczeń.

Geneza ONP, sięgająca pracy polskiego logika Jana Łukasiewicza (Notacja Polska, czyli prefiksowa), została spopularyzowana przez Charlesa Hamblina, który dostrzegł, że notacja postfiksowa (odwrotna) doskonale pasuje do architektury komputerów opartych na stosie, zyskując tym samym przydomek RPN. To historyczne połączenie logiki i informatyki jest dowodem na głębokie teoretyczne podstawy tej metody. Zastosowanie ONP w kompilatorach (np. jako wewnętrzna reprezentacja wyrażeń) oraz w architekturach maszyn wirtualnych (jak JVM) podkreśla jej praktyczną wartość, redukując złożoność parsowania z O(N^2) lub O(N log N) (przy konieczności rekurencyjnego sprawdzania priorytetów) do prostego przejścia O(N).

---

Struktura danych: stos jako serce ONP

Szczegółowe operacje stosu i ich związek z ONP

Stos (Stack) jest strukturą danych działającą na zasadzie **LIFO** (Last In, First Out). W kontekście ONP, kluczowe operacje to:

• PUSH: Dodaje element na wierzch stosu. W algorytmie konwersji używany do umieszczania operatorów i nawiasów. W algorytmie obliczania używany do umieszczania operandów i wyników pośrednich.
• POP: Usuwa i zwraca element z wierzchu stosu. W konwersji używany do przenoszenia operatorów na wyjście (B_OUT). W obliczeniach używany do pobierania argumentów dla operatora.
• PEEK/TOP: Odczytuje element z wierzchu bez usuwania go. Niezbędny w algorytmie konwersji do sprawdzania priorytetu operatora na stosie (O₂) przed podjęciem decyzji o jego usunięciu.

Wyjaśnienie wizualizacji stosu:

• Diagram ilustruje, że stos jest dynamiczną listą, w której operacje PUSH i POP modyfikują tylko wierzchołek, co jest podstawą dla LIFO.
• W kontekście ONP, jeśli na stosie znajduje się już element $A$, a my wykonamy PUSH $B$, to $B$ znajdzie się nad $A$.
• Następne POP zawsze zwróci $B$ (LIFO), a dopiero później będziemy mogli uzyskać $A$.
• Ta prosta reguła zapewnia, że w obliczeniach operator zawsze działa na dwóch argumentach, które zostały wprowadzone jako ostatnie, co odpowiada wewnętrznemu zagnieżdżeniu wyrażenia i symuluje grupowanie za pomocą nawiasów.

---

Algorytm konwersji wyrażenia infiksowego na ONP (Algorytm Shunting-Yard)

Algorytm Shunting-Yard (sortownia manewrowa) przekształca wyrażenia infiksowe w postfiksowe, wykorzystując stos operatorów (S_OP) do zarządzania priorytetami i grupowaniem. Wyjście jest gromadzone w Buforze Wyjściowym (B_OUT).

Tabela priorytetów operatorów i łączności

Operator	Priorytet	Łączność (Asocjatywność)
^ (Potęgowanie)	4	Prawostronna (Right-Associative): $a \wedge b \wedge c = a \wedge (b \wedge c)$
*, /	3	Lewostronna (Left-Associative): $a * b * c = (a * b) * c$
+, –	2	Lewostronna (Left-Associative): $a + b + c = (a + b) + c$
(, )	1 (Logiczna)	Nie dotyczy – Służą do grupowania

Wyjaśnienie tabeli priorytetów:

• Priorytety (liczby 2-4) określają, które operacje należy wykonać najpierw. Wyższy numer oznacza wyższy priorytet (np. ^ ma wyższy priorytet niż *).
• Lewostronna łączność (dla +, -, *, /) oznacza, że jeśli na stosie (O₂) i wchodzący (O₁) operator mają ten sam priorytet, operator ze stosu (O₂) musi być usunięty (POP) i dodany do wyjścia przed wciśnięciem O₁.
• Prawostronna łączność (dla ^) oznacza, że jeśli operatory mają ten sam priorytet, operator wchodzący (O₁) jest PUSH-owany bezpośrednio na wierzch stosu, wymuszając grupowanie od prawej do lewej.
• Nawiasy mają najniższy logiczny priorytet na stosie (aby wszystko mogło się nad nimi kumulować) i najwyższy priorytet poza nim (aby wymusić wykonanie operacji wewnątrz).

Przykład konwersji: (A + B) * C ^ D

Token	Akcja (Zasada)	Stos Operatorów (S_OP) [Od dołu do góry]	Bufor Wyjściowy (B_OUT) (ONP)
(	PUSH ‚(‚ (Zasada 3).	(
A	Operand. Dodaj bezpośrednio do B_OUT (Zasada 1).	(	A
+	Operator. PUSH ‚+’ (Zasada 2). Na szczycie jest ‚(‚, ma niższy priorytet logiczny.	(, +	A
B	Operand. Dodaj bezpośrednio do B_OUT (Zasada 1).	(, +	A B
)	Nawias zamykający. POP operatory do ‚(‚ (Zasada 4).	(	A B +
	POP ‚(‚ i odrzuć (Zasada 4).	Pusty	A B +
*	Operator. PUSH ‚*’ (Zasada 2). Stos jest pusty.	*	A B +
C	Operand. Dodaj bezpośrednio do B_OUT (Zasada 1).	*	A B + C
^	Operator. ‚^’ (P=4) ma wyższy priorytet niż ‚*’ (P=3). PUSH ‚^’ (Zasada 2).	*, ^	A B + C
D	Operand. Dodaj bezpośrednio do B_OUT (Zasada 1).	*, ^	A B + C D
Koniec	Koniec wyrażenia. POP resztę operatorów: ‚^’ i ‚*’ (Zasada 5).	Pusty	A B + C D ^ *

Szczegółowe wyjaśnienie konwersji:

• A, B: Operandy są natychmiast przenoszone do bufora B_OUT.
• (: Nawias otwierający idzie na stos, aby rozpocząć nowe grupowanie.
• +: Wchodzi na stos. Jego priorytet jest niższy niż logiczny priorytet ‚(‚ na stosie, więc jest wpychany.
• ): Wyzwala opróżnianie stosu do momentu napotkania ‚(‚. Operator ‚+’ jest POP-owany na B_OUT. Następnie nawias ‚(‚ jest POP-owany i odrzucany, kończąc podwyrażenie (A+B).
• *: Wchodzi na pusty stos.
• ^: Ma wyższy priorytet (4) niż ‚*’ (3), więc jest PUSH-owany na stos nad ‚*’.
• D: Operand. Przeniesiony do B_OUT.
• Koniec: Stos jest opróżniany. Najpierw wychodzi ‚^’ (bo jest na górze), a potem ‚*’ – co odzwierciedla poprawną kolejność: A+B, potem C^D, a na końcu mnożenie wyników.

Algorytm obliczania wyrażenia w ONP – symulacja i przykłady

Obliczanie wyrażenia ONP odbywa się przy użyciu jednego stosu operandów (S_OPD). Operator zawsze działa na dwóch wierzchołkowych elementach stosu.

Przykład obliczania: 10 5 2 + /

Token	Akcja (Zasada)	Stan Stosu Operandów (S_OPD) [Od dołu do góry]	Obliczenie (a, b)
10	PUSH 10 (Zasada 1)	[10]	–
5	PUSH 5 (Zasada 1)	[10, 5]	–
2	PUSH 2 (Zasada 1)	[10, 5, 2]	–
+	Operator. POP b=2, a=5. Oblicz 5+2=7. PUSH 7 (Zasada 2)	[10, 7]	5 + 2 = 7
/	Operator. POP b=7, a=10. Oblicz 10/7. PUSH 1.428… (Zasada 2)	[1.428…]	10 / 7 ≈ 1.428
Koniec	Wynik końcowy (Zasada 3)	[1.428…]	Wynik to 1.428…

Szczegółowe wyjaśnienie obliczeń:

• 10, 5, 2: Liczby są wpychane na stos w kolejności występowania. Stos buduje się od dołu (10) do góry (2).
• +: Napotkanie operatora ‚+’ wyzwala operację:
  • POP 2 (to jest b – drugi argument).
  • POP 5 (to jest a – pierwszy argument).
  • Obliczenie: a + b = 5 + 2 = 7.
  • PUSH 7 z powrotem na stos.
• /: Napotkanie operatora ‚/’ wyzwala operację:
  • POP 7 (to jest b – drugi argument).
  • POP 10 (to jest a – pierwszy argument).
  • Obliczenie: a / b = 10 / 7 ≈ 1.428.
  • PUSH 1.428… z powrotem na stos.
• Koniec: Ostateczna wartość (1.428…) pozostaje na stosie jako wynik całego wyrażenia.

Zastosowanie prawostronnej łączności na przykładzie potęgowania

Prawostronna łączność jest kluczowa dla operatorów takich jak potęgowanie (^), gdzie wyrażenie $A \wedge B \wedge C$ jest interpretowane jako $A \wedge (B \wedge C)$, czyli grupowanie od prawej. W algorytmie Shunting-Yard operator o równym priorytecie (O₂ = O₁) nie jest wypychany, jeśli ma łączność prawostronną – O₁ jest PUSH-owany, wymuszając grupowanie od prawej.

Przykład konwersji: $A \wedge B \wedge C$

Token	Akcja (Zasada)	Stos Operatorów (S_OP)	Bufor Wyjściowy (B_OUT) (ONP)
A	Operand. B_OUT (1).	Pusty	A
^	PUSH ‚^’ (2). Stos pusty.	^	A
B	Operand. B_OUT (1).	^	A B
^	Operator ‚^’ (P=4). O2 jest ‚^’ (P=4). Łączność jest prawostronna. O2 NIE jest wypychany. PUSH ‚^’ (2).	^, ^	A B
C	Operand. B_OUT (1).	^, ^	A B C
Koniec	POP reszty: ‚^’, ‚^’ (5).	Pusty	A B C ^ ^

Szczegółowe wyjaśnienie prawostronności:

• A, B, C: Operandy trafiają bezpośrednio na wyjście.
• Pierwsze ^: Jest PUSH-owane na pusty stos.
• Drugie ^: Napotykamy na stosie operator ‚^’ o równym priorytecie. Ponieważ potęgowanie jest **prawostronnie łączne**, operator na stosie (O₂) **nie jest** wypychany (POP).
• W rezultacie, operator wchodzący (O₁) jest PUSH-owany na stos, co daje stan stosu [^, ^].
• Koniec: Podczas opróżniania stosu, drugi operator ‚^’ (który reprezentuje $B \wedge C$) wychodzi pierwszy, a następnie pierwszy ‚^’ (reprezentujący $A \wedge \text{wynik}$).
• Kolejność **A B C ^ ^** poprawnie wymusza obliczenie $B \wedge C$ przed $A \wedge (\dots)$, co jest poprawne dla prawostronnej łączności.