Aritmetični izrazi v obrnjenem poljskem zapisu

Iz MaFiRaWiki

Za aritmetične izraze oblike 2 + 3 pravimo, da so zapisani v infiksni ali vmesni obliki, saj je operacija zapisana med operandoma. Izraze pa lahko pišemo tudi tako, da je operacija zapisana za operandoma: 2 3 + . Takemu zapisu pravimo postfiksna ali obrnjena poljska notacija (ime je dobila po poljskem matematiki Janu Łukasiewiczu, ki je vpeljal ravno obraten zapis, to je prefiksna ali poljska notacija - operatorji se pišejo pred operandi: + 2 3 ).

Računanje izraza v obrnjenem poljskem zapisu

Računanje izraza v obrnjenem poljskem zapisu poteka takole:

  1. Vsak operand, na katerega naletimo, ko beremo izraz iz leve proti desni, se doda na konec seznama, ki je na začetku prazen.
  2. Če naletimo na dvomesten operator, se zadnja dva elementa v seznamu izbrišeta in nato se na konec seznama doda rezultat operacije (analogno lahko računamo tudi z n-členimi operacijami).
  3. Število, ki po pregledu celega izraza ostane v seznamu, je rezultat celotnega izraza (to število je enolično določeno z izrazom, če je ta bil pravilno zapisan).

Ker moramo v postopku računanja vrednosti nekje hraniti in potem spreminjamo tiste, ki smo jih nazadnje shranili, je najbolje, da računamo z uporabo podatkovne strukture sklad.

Primer:

Računanje izraza 3 5 6 4 - * 6 + * 2 a / ("a" predstavlja enomestno operacijo "-", ki je potrebna za podajanje negativnih števil) v obrnjeni poljski notaciji bi potekalo takole:

3
3, 5
3, 5, 6
3, 5, 6, 4
3, 5, 2 ( 6 in 4 sta zamenjani s 6 - 4 = 2 )
3, 10 ( 5 in 2 sta zamenjani s 5 * 2 = 10 )
3, 10, 6
3, 16 ( 10 in 6 sta zamenjani z 10 + 6 = 16 )
48 ( 3 in 16 sta zamenjani s 3 * 16 = 48 )
48, 2
48, -2 ( 2 je zamenjana z -2 )
24 ( 48 in 2 sta zamenjana z 48 / 2 = 24 )

Ena izmed glavnih prednost obrnjenega poljskega zapisa je, da nam ni potrebno zaznamovati prednosti operacij, kar pomeni, da lahko vsak izraz zapišemo brez uporabe oklepajev.

Primer:

Izraz, ki se v vmesni obliki zapiše kot

( ( 3 + 5 ) / ( 7 - 2 ) + 4 / ( 8 - 5 ) ) / ( 3 + 5 * ( 4 / ( 7 - 2 ) ) ) ,

se v obrnjeni poljski notaciji zapiše kot

3 5 + 7 2 - / 4 8 5 - / + 3 5 4 7 2 - / * + / .

Zaradi tega večina programskih jezikov pred kakršnokoli obdelavo interno prevede vse aritmetične izraze v obrnjen poljski zapis.

Povezave

Glej tudi

Osebna orodja