Reverse Polish Notation - elegáns alternatíva matematikai kifejezések kiértékeléséhez

A matematikai kifejezések leírásának számos módja létezik. A leginkább elterjedt az infix notáció, ahol az operátorok a operandusok között helyezkednek el, mint például az A + B vagy (C * D) - E. Bár ez a notáció intuitívnak tűnhet számunkra, emberek számára, a számítógépek és számológépek számára nem feltétlenül a legoptimálisabb megoldás. Ebben a cikkben egy kevésbé ismert, de annál elegánsabb alternatívát, a Reverse Polish Notation (RPN), vagy magyarul fordított lengyel notációt, más néven postfix notációt fogunk megvizsgálni.

Mi is az a Reverse Polish Notation?

Az RPN egy olyan matematikai notáció, ahol az operátorok az operandusok után következnek. Ahelyett, hogy A + B-t írnánk, RPN-ben A B +-ként jelöljük. Első pillantásra talán szokatlannak tűnhet, de hamar megértjük az előnyeit.

Az RPN koncepciója Jan Łukasiewicz lengyel matematikus nevéhez fűződik, aki az 1920-as években fejlesztette ki a prefix notációt (lengyel notációt), ahol az operátorok az operandusok előtt állnak. A postfix notáció ennek egy variánsa, és Charles Hamblin ausztrál számítógép-tudós fejlesztette tovább az 1950-es években, egyszerűsítve a számítógépes feldolgozást.

Miért jó az RPN?

Az RPN legfőbb előnye a kétértelműség kiküszöbölése és a számítási hatékonyság. Az infix notációban zárójelekre van szükségünk a műveletek sorrendjének egyértelművé tételéhez, és a számítógépeknek bonyolult elemzési algoritmusokra van szükségük a műveleti sorrend (precedencia) helyes kezeléséhez. Az RPN-ben viszont nincs szükség zárójelekre, és a műveletek sorrendje a kifejezés felépítéséből automatikusan adódik.

Ez különösen a korai számítógépek és zsebszámológépek esetében volt kritikus fontosságú, ahol a hardver erőforrások korlátozottak voltak. Az RPN-t alkalmazó számológépek egyszerűbb és gyorsabb számításokat tudtak végezni.

Történelmi érdekesség: Az RPN notációt először a Hewlett-Packard (HP) cég tette népszerűvé az 1960-as és 70-es években. Az HP-9100A asztali számológép (1968) volt az egyik első kereskedelmi forgalomban kapható számológép, amely RPN-t használt. Később a legendás HP-35 (1972), az első tudományos zsebszámológép is az RPN-t alkalmazta, és ez a módszer a HP professzionális számológépeinek védjegyévé vált hosszú időre. Az RPN-t használó számológépek híresek voltak a gyors és pontos számításaikról, és a mérnökök, tudósok és pénzügyi szakemberek körében nagy népszerűségre tettek szert.

Az RPN Működése

Nézzünk egy példát, hogyan működik az RPN. Vegyük az infix kifejezést: (3 + 4) * 2 - 5.

Először konvertáljuk ezt RPN-be. A konverzióhoz figyelembe kell vennünk a műveletek sorrendjét. Ebben az esetben először az összeadást végezzük el a zárójelben, majd szorzunk kettővel, végül kivonunk ötöt. Az RPN kifejezés a következő lesz: 3 4 + 2 * 5 -.

Most nézzük meg, hogyan értékeljük ki ezt az RPN kifejezést egy verem (stack) segítségével. A verem egy olyan adatszerkezet, amelybe elemeket helyezhetünk (push) és kivehetünk (pop), mindig a legutoljára behelyezett elemet véve ki először (LIFO - Last-In, First-Out).

Az RPN kifejezés kiértékelése lépésről lépésre:

1. 3: Olvassuk be a 3-at. Ez egy operandus, helyezzük a verembe. Verem állapota: [3]
2. 4: Olvassuk be a 4-et. Ez is operandus, helyezzük a verembe. Verem állapota: [3, 4]
3. +: Olvassuk be a + operátort. Vegyünk ki két operandust a veremből (először a 4-et, majd a 3-at). Végezzük el az összeadást: 3 + 4 = 7. Helyezzük az eredményt (7) vissza a verembe. Verem állapota: [7]
4. 2: Olvassuk be a 2-t. Operandus, verembe helyezzük. Verem állapota: [7, 2]
5. *: Olvassuk be a * operátort. Vegyünk ki két operandust a veremből (először a 2-t, majd a 7-et). Végezzük el a szorzást: 7 * 2 = 14. Helyezzük az eredményt (14) vissza a verembe. Verem állapota: [14]
6. 5: Olvassuk be az 5-öt. Operandus, verembe helyezzük. Verem állapota: [14, 5]
7. -: Olvassuk be a - operátort. Vegyünk ki két operandust a veremből (először az 5-öt, majd a 14-et). Végezzük el a kivonást: 14 - 5 = 9. Helyezzük az eredményt (9) vissza a verembe. Verem állapota: [9]

Mivel az RPN kifejezés végére értünk, és a veremben csak egy elem maradt, ez az elem a végeredmény. Tehát az (3 + 4) * 2 - 5 kifejezés értéke RPN-ben kiértékelve 9.

Hogyan konvertáljunk infix kifejezést RPN-é?

A legelterjedtebb algoritmus az infix kifejezések RPN-re történő átalakítására az Shunting-yard algoritmus, amelyet Edsger Dijkstra fejlesztett ki. Ez az algoritmus egy vermet és egy kimeneti sort (ami gyakorlatban lehet egyszerű lista is) használ a konverzióhoz.

Az Shunting-yard algoritmus lépései:

1. Tokenizálás: Bontsuk fel az infix kifejezést tokenekre (számok, operátorok, zárójelek).
2. Inicializálás: Hozzunk létre egy üres vermet operátorok tárolására és egy üres kimeneti sort az RPN kifejezés építéséhez.
3. Tokenek feldolgozása: Iteráljunk végig a tokeneken:
   • Szám: Ha a token szám, adjuk hozzá a kimeneti sorhoz.
   • Operátor: Ha a token operátor (op1):
     • Miközben a verem tetején operátor (op2) van, és:
       • op2 precedenciája nagyobb vagy egyenlő, mint op1 precedenciája, ÉS
       • op1 balról asszociatív (a mi példánkban minden operátor balról asszociatív),
     • Vegyük le op2-t a veremből, és adjuk hozzá a kimeneti sorhoz.
     • Toljuk op1-et a verembe.
   • Bal zárójel (: Toljuk a vermbe.
   • Jobb zárójel ):
     • Miközben a verem tetején nem bal zárójel van:
       • Vegyük le az operátort a veremből, és adjuk hozzá a kimeneti sorhoz.
     • Ha a verem tetején bal zárójel van, vegyük le a veremből (de ne adjuk hozzá a kimeneti sorhoz - a zárójelek nem kerülnek az RPN kifejezésbe).
     • Ha a verem tetején nem bal zárójel van a jobb zárójel feldolgozása után, akkor a zárójelezés hibás.
4. Verem ürítése: Ha már nincsenek több tokenek, vegyük le a veremből az összes operátort, és adjuk hozzá a kimeneti sorhoz.
5. Eredmény: A kimeneti sor tartalmazza az RPN kifejezést.

Precedencia és Asszociativitás:

Fontos a műveletek precedenciájának és asszociativitásának ismerete. A szokásos precedencia sorrend (magasabbtól alacsonyabbig):

• Szorzás (*), Osztás (/)
• Összeadás (+), Kivonás (-)

Mind a négy alapművelet balról asszociatív, ami azt jelenti, hogy az azonos precedenciájú operátorok balról jobbra értékelődnek ki (pl. a - b - c = (a - b) - c).

Példa az infix (3 + 4) * 2 - 5 RPN-re konvertálására Shunting-yard algoritmussal:

Token	Kimeneti sor (Queue)	Verem (Stack)	Megjegyzés
(		(	Bal zárójel a verembe.
3	3	(	Szám a kimeneti sorhoz.
+	3	(, +	Operátor a verembe.
4	3, 4	(, +	Szám a kimeneti sorhoz.
)	3, 4, +	(	Jobb zárójel - operátorok a veremből a kimeneti sorba, amíg bal zárójel nem jön. Bal zárójel levétele a veremből.
*	3, 4, +	*	Operátor a verembe (magasabb precedencia).
2	3, 4, +, 2	*	Szám a kimeneti sorhoz.
-	3, 4, +, 2, *	-	Operátor a verembe (alacsonyabb precedencia, de a * precedenciája magasabb, ezért nem kerül levételre a veremből).
5	3, 4, +, 2, *, 5	-	Szám a kimeneti sorhoz.
Vége	3, 4, +, 2, *, 5, -		Verem ürítése a kimeneti sorhoz.

Tehát az infix (3 + 4) * 2 - 5 RPN formája: 3 4 + 2 * 5 -.

Összefoglalás

A Reverse Polish Notation egy elegáns és hatékony módszer matematikai kifejezések leírására és kiértékelésére. Bár az infix notációhoz képest kevésbé intuitívnak tűnhet elsőre, az RPN számos előnnyel rendelkezik, különösen a számítógépes feldolgozás szempontjából. Megszünteti a kétértelműséget, nincs szükség zárójelekre, és hatékonyan kiértékelhető egy egyszerű verem segítségével. Az infix kifejezések RPN-re történő átalakítására az Shunting-yard algoritmus egy széles körben használt és hatékony módszer.

Történelmi jelentősége vitathatatlan, hiszen a korai zsebszámológépekben fontos szerepet játszott, és a mai napig releváns koncepció a számítástechnikában, például a fordítóprogramokban és a virtuális gépekben is alkalmazzák. Bár a mindennapi felhasználásban kevésbé elterjedt, az RPN egy értékes eszköz és gondolkodásmód, amely mélyebb megértést biztosít a matematikai kifejezések és a számítógépes műveletek kapcsolatáról. A cikkben bemutatott Python kód segítségével pedig gyakorlati tapasztalatot is szerezhetünk az RPN működésével és alkalmazásával kapcsolatban.