Fordított Lengyel-forma

A Programozás Wiki wikiből
(Lengyel-forma szócikkből átirányítva)

A lengyel forma, matematikai kifejezések olyan megadása, ahol a megszokottól eltérően, a bináris operátorok, nem az operandusok között, hanem azok után helyezkednek el. Ennek pl. egy kifejezés kiértékelésénél több jótékony hatása is van.

  • Lengyel formában felírt kifejezések nem tartalmaznak zárójeleket, vagy műveleti sorrendet, amik bonyolíthatnák egy kifejezés kiértékelését (Természetesen, ezekkel egy kifejezés lengyel formában való felírásnál kell foglalkozni)
  • Egy egyszerű, vermet használó algoritmussal kiértékelhető a kifejezés.


BNF:

kifejezés    := <operandus> <operandus> <operator>
operator     := "+" | "-" | "*" | "/" ...
operandus    := <szám> | <kifejezés>

példák[szerkesztés]

  • 1 * 2 lengyel formája: 1 2 *
  • 1 * 2 + 3 lengyel formája: 1 2 * 3 +. Ez még egyszerű.
  • 1 * 2 + 3 / 4 lengyel formája: 1 2 * 3 4 / +

Látható, hogy itt a műveleti sorrend sokat bonyolít az átíráson.

  • 1 * (2 + 3) / 4 lengyel formája: 1 2 3 + * 4 /

És a zárójel, még rátesz erre egy lapáttal.


Elsőre idegen lehet ennek a formának a felírása, értelmezése. Zárójelezzük be az utolsó példát: ((1 (2 3 +) *) 4 /) így már látható, hogy valóban az 1 * (2 + 3) / 4 kifejezés az.