Lengyel forma (Postfix expression)

Aritmetikai kifejezés:

Az aritmetikai kifejezésben lehetnek matematikai műveleti jelek (operátorok), kerek zárójelek, operandusok (változók, konstansok). Például $a = b + 1$ vagy $c = d * 2$.

Aritmetikai kifejezés alakjai:

infix: $A + B$, az egyes műveleti jelek az operandusaik között helyezkednek el
postfix: $AB+$, az egyes műveleti jelek az operandusaik mögött helyezkednek el
prefix: $+AB$, az egyes műveleti jelek az operandusaik előtt helyezkednek el

Az emberek számára kényelmes és könnyen átlátható az infix alak, de a fordítóprogramoknak egy olyan alakra van szükségük, amelyekből a műveletek elvégzésének a sorrendje egyértelműen adódik.

A lengyel forma az aritmetikai kifejezés postfix alakja.

Lengyel forma jellemzői:

A lengyel forma az aritmetikai kifejezés postfix alakja. Nincsenek benne zárójelek, a kiértékelés mégis egyértelmű. Operandusok sorrendje nem változik. Operátorok sorrendje az elvégzésük sorrendjében szerepel, tehát balról jobbra. Minden operátort közvetlen megelőznek az operandusai, (az operandus lehet változó, konstans, de lehet postfix kifejezés is).

Operátorok precedenciája (elsősége):

Legkisebb precedenciájútól a legnagyobbig a sorrend a következő:

$=$
$+$ és $-$ (azonos rangúak)
$*$ és $/$ (azonos rangúak)
^

Balról jobbra típusú (bal asszociatív) operátorok: $+$, $-$, $*$, $/$

Jobbról balra típusú (jobb asszociatív) operátorok: $=$, ^

Lengyel forma (postfix alak) előállítása:

A bemenet egy helyesen zárójelezett aritmetikai kifejezés. A kimenet maga a lengyel forma. Az inputot szekvenciálisan dolgozzuk fel, és egy verem segítségével állítjuk elő a lengyelformát.

Ha a soron következő karakter operandus (karakter, szám, stb.), kiírjuk a kimenetre. Ha a soron következő karakter operátor ($+$, $-$, $*$, $/$, $=$, ^), bekerül a verembe. Minden beolvasott operátor bekerül a verembe. De mielőtt bekerülne a verembe meg kell vizsgálni magát az operátort, amit bele szeretnék helyezni a verembe és meg kell vizsgálni a már veremben lévő operátorokat is precedencia szerint. (A verem tetején lévő operátort és a beolvasott operátorokat hasonlítjuk össze.)

azonos rangúak $\implies$ kiírjuk a verem tetején lévő operátort a kimenetre (ezzel együtt ki is vesszük a veremből), feltéve, hogy balról jobbra típusú, ha jobbról balra, akkor nem történik semmi, mehet bele a verembe a beolvasott operátorunk
beolvasott operátor magasabb precedenciájú $\implies$ berakjuk a verembe
beolvasott operátor alacsonyabb precedenciájú $\implies$ kiírjuk a verem tetején lévő operátort és megvizsgáljuk az újdonsült verem tetején lévő elemet

nyitó zárójel $\implies$ a verembe kerül
csukó zárójel $\implies$ a nyitó zárójelig mindent kiírunk a veremből sorrendben, a zárójelek nem kerülnek kiírásra, csak eldobjuk őket

Amikor az input végére értünk, a veremben levő összes maradék operátort kivesszük és kiírjuk a kimenetre.

$LengyelForma()$

$V : Stack$
	$read(x)$
	$Operandus(x)$	$x = '('$	$x = ')'$		$Operátor(x)$
	$write(x)$	$V.push(x)$		$V.top() \neq '('$	$BalJobbOperátor(x)$
				$write(V.pop())$		$\neg V.IsEmpty() \land V.top() \neq '('$ $\land pr(V.top()) \geq pr(x)$		$\neg V.IsEmpty() \land V.top() \neq '('$ $\land pr(V.top()) > pr(x)$
			$V.pop()$			$write(V.pop())$		$write(V.pop())$
					$V.push(x)$		$V.push(x)$
	$\neg V.IsEmpty()$
	$write(V.pop())$

Példák:

$a + b \implies ab+$
$a * b + c \implies ab * c+$
$a + b * c \implies abc * +$
$a * (b + c) \implies abc + *$
$a + b - c \implies ab+c-$
$a / b * c \implies ab / c *$
$a$ ^ $b$ ^ $c$ $\implies$ $abc$^^

Lengyel forma kiértékelése (teljesen zárójelezett alak előállítása):

A bemenet egy postfix alakú aritmetikai kifejezés (lengyel forma), a kimenet pedig egy teljesen zárójelezett infix aritmetikai kifejezés. Az inputot szekvenciálisan dolgozzuk fel, és egy verem segítségével értékeljük ki a lengyelformát.

Ha a soron következő karakter operandus (karakter, szám, stb.), verembe rakjuk. Ha a soron következő karakter operátor ($+$, $-$, $*$, $/$, $=$, ^), kivesszük a veremből az operátor aritásának megfelelő számú elemet, azaz annyi elemet veszünk, ahány operandusa van egy adott operátornak. (Pl.: az összeadás 2 operandusú művelet, 2 számot adunk össze. A többi is, amiket láttunk korábban, hasonlóan 2 aritású operátorok, de vannak 1 aritású operátorok is, pl.: $++, --$). Miután ez megtörtént visszarakjuk őket az operátorral és a zárójelekkel együtt a verembe, pl.: $(x_1 + x_2)$ kerül a verembe. Végül a veremben csak a teljesen zárójelezett alak lesz.

$LengyelKiertekeles(S)$

$V:Stack$
$x := read(S)$
	$x \neq \varepsilon$
	$Operator(x)$	$Operandus(x)$
	$jobb := V.pop()$	$V.push(x)$
	$bal:= V.pop()$
	$V.push(bal \otimes jobb)$
	$x := read(S)$
$write(V.pop())$

Példák:

$ab*c+ \implies ((a*b)+c)$
$ab + c * d - \implies 17$, ha ($a=2, b=4, c=3, d=1$)

Gyakorlati alkalmazása:

A fordítóprogramoknál használják, ugyanis a fordítóprogramoknak egy olyan alakra van szükségük, amelyekből a műveletek elvégzésének a sorrendje egyértelműen, könnyen adódik.

Animáció

Struktogram

$LengyelForma()$

$V : Stack$
	$read(x)$
	$Operandus(x)$	$x = '('$	$x = ')'$		$Operátor(x)$
	$write(x)$	$V.push(x)$		$V.top() \neq '('$	$BalJobbOperátor(x)$
				$write(V.pop())$		$\neg V.IsEmpty() \land V.top() \neq '('$ $\land pr(V.top()) \geq pr(x)$		$\neg V.IsEmpty() \land V.top() \neq '('$ $\land pr(V.top()) > pr(x)$
			$V.pop()$			$write(V.pop())$		$write(V.pop())$
					$V.push(x)$		$V.push(x)$
	$\neg V.IsEmpty()$
	$write(V.pop())$

Animáció

Struktogram

$LengyelForma()$

$V : Stack$
	$read(x)$
	$Operandus(x)$	$x = '('$	$x = ')'$		$Operátor(x)$
	$write(x)$	$V.push(x)$		$V.top() \neq '('$	$BalJobbOperátor(x)$
				$write(V.pop())$		$\neg V.IsEmpty() \land V.top() \neq '('$ $\land pr(V.top()) \geq pr(x)$		$\neg V.IsEmpty() \land V.top() \neq '('$ $\land pr(V.top()) > pr(x)$
			$V.pop()$			$write(V.pop())$		$write(V.pop())$
					$V.push(x)$		$V.push(x)$
	$\neg V.IsEmpty()$
	$write(V.pop())$

Feladatok

Az alábbi feladatok a gyakorlatokon elvégzendő kötelező, illetve gyakorló feladatok.