Fordított lengyel jelölés

„3+4” összeadás fordított lengyel jelöléssel

Ha egy aritmetikai műveletben az operátor az operandusok után áll, akkor posztfix, vagy fordított lengyel jelölésről beszélhetünk. A változók sorrendje az infix és prefix jelölésben megegyezik, a műveleti jelek sorrendje azonban nem mindig azonos. A fordított lengyel jelölésben a műveleti jelek olyan sorrendben szerepelnek, amilyen sorrendben azok végrehajtódnak a kifejezés kiértékelésekor.

Az eredeti lengyel jelölési forma a lengyel logikatudós Jan Łukasiewicz után kapta a nevét, aki 1920-ban kimutatta ennek a módszernek az előnyeit a prefix, vagy éppen a hagyományos infix jelölésekkel szemben. A fordított lengyel jelölést ennek analógiáján az ausztrál filozófus, és számítógéptudós Charles Hamblin dolgozta ki az 1950-es évek közepén.

Előnyei

A fordított lengyel jelölésnek számos előnye van az infix jelöléssel szemben algebrai kifejezések esetén. Először is, minden formula kifejezhető zárójel nélkül. Ezen kívül kényelmesen kiértékelhetők a formulák számítógéppel verem használatával. Az infix operátorokra elsőbbségi szabály vonatkozik, amely tetszőleges és nem kívánatos. Például, tudjuk, hogy az $a * b + c$ jelentése $(a * b) + c$ és nem $a * (b + c)$, mivel a szorzás nagyobb prioritású művelet, mint az összeadás. A számítástechnikában használt műveletek esetén azonban bizonyos esetekben nem állapítható meg prioritás teljesen különböző műveletek között sem. Például a balra léptetés (SHL), valamint a logikai ÉS művelet között nem tudunk ilyen egyértelmű sorrendet felállítani. A fordított lengyel jelölés kiküszöböli ezt a kellemetlenséget.

Infix	Fordított lengyel jelölés
A + B * C	ABC * +
A * B + C	AB * C +
A * B + C * D	AB * CD * +
(A +B)/(C - D)	AB + CD - /
((A + B ) * C + D) / (E + F + G)	AB + C * D + EF + G + /

Formulák kiértékelése

Lépés	A maradék formula	ASM utasítás	Verem tartalma
1	8 2 5 * + 1 3 2 * + 4 - /	BIPUSH 8	8
2	2 5 * + 1 3 2 * + 4 - /	BIPUSH 2	8, 2
3	5 * + 1 3 2 * + 4 - /	BIPUSH 5	8, 2, 5
4	* + 1 3 2 * + 4 - /	IMUL	8, 10
5	+ 1 3 2 * + 4 - /	IADD	18
6	1 3 2 * + 4 - /	BIPUSH 1	18, 1
7	3 2 * + 4 - /	BIPUSH 3	18, 1, 3
8	2 * + 4 - /	BIPUSH 2	18, 1, 3, 2
9	* + 4 - /	IMUL	18, 1, 6
10	+ 4 - /	IADD	18, 7
11	4 - /	BIPUSH 4	18, 7, 4
12	- /	ISUB	18, 3
13	/	IDIV	6

A fordított lengyel jelölés ideális formulák számítógépes kiértékelésére verem használatával. A formula n jelből áll, mindegyik vagy operandus, vagy műveleti jel (operátor). Az algoritmus rendkívül egyszerű: Olvassuk a formulát balról jobbra! Ha az operandushoz érünk, akkor rakjuk a verembe. Ha az aktuális jel műveleti jel, akkor hajtsuk végre a megfelelő műveletet a veremben lévő két legfelső számmal.

példa: (8 + 2 * 5) / (1 + 3 * 2 - 4); fordított lengyel jelöléssel: 8 2 5 * + 1 3 2 * + 4 - /

Fontos, hogy az osztás és a kivonás esetében a verem tetején lévő operandus a jobb, és nem pedig a bal operandus, mivel ezek a műveletek nem kommutatívak. Más szóval az IDIV (osztás assembly utasítása) esetében először az osztandót kell a verembe tenni, majd az osztót, és ez után kell elvégezni a műveletet, hogy helyes eredményt kapjunk. Így balról jobbra olvasva csak arra kell figyelni, hogy ha a jel konstans vagy változó, akkor olyan utasítást kell kiadni, amely azt a verembe teszi; ha pedig műveleti jel, akkor a műveletet megvalósító utasítást kell kiadni.