Prefix- en suffixnotatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Prefixnotatie is een vorm van wiskundige notatie waarbij alle operatoren voor hun argumenten geschreven worden. Prefixnotatie is gebruikelijk bij functies: we schrijven doorgaans f(x , y) in plaats van x f y. Een uitzondering geldt eigenlijk alleen voor de klassieke functies zoals optelling, deze worden infix geschreven worden: x + y. In prefixnotatie zou een optelling geschreven worden als +(x, y). Gaat men ervan uit dat een optelling altijd precies twee argumenten heeft ( +(x, y, z) mag dus niet), dan kan het ook zonder haakjes: + x y.

Suffixnotatie is het tegenovergestelde van prefixnotatie: het achteraan schrijven van de operator.

Prefixnotatie is omstreeks 1920 uitgevonden door de Poolse logicus Jan Łukasiewicz als notatie voor de propositielogica. Men spreekt daarom ook wel van Poolse notatie. Suffixnotatie heet dan ook wel Omgekeerde Poolse notatie (of RPN, reversed Polish notation). Poolse notatie sloeg in het oorspronkelijke toepassingsgebied niet aan.

Voorbeeld[bewerken]

Een voorbeeld: in Poolse notatie wordt de uitdrukking (a + b) × c geschreven als:

× + a b c

en in omgekeerde Poolse notatie als

a b + c ×

Voert men de vermenigvuldiging eerst uit, dus a + (b × c), dan wordt het

+ a × b c

en

a b c × +

Volgorde van operanden en operators[bewerken]

Merk op dat de volgorde van de operanden a, b en c niet verandert. Alleen de plaatsing van de operatoren is anders.

Overbodige haakjes[bewerken]

Het voordeel van Poolse notatie is dat alle uitdrukkingen zonder haakjes eenduidig zijn. Wel is het nodig dat alle operatoren een vaste ariteit hebben - er zijn dus verschillende operatoren nodig voor aftrekken en negatie. Verder is het nodig dat getallen van elkaar gescheiden worden: er is verschil tussen + 3 58 en + 35 8.

Implementatie[bewerken]

De HP-35, de eerste zakcalculator van Hewlett-Packard, gebruikte omgekeerde Poolse notatie

Omgekeerde Poolse notatie is gemakkelijk te implementeren met behulp van een stack en werd lang gebruikt in wetenschappelijke calculators van het merk Hewlett-Packard. De stack heeft bij deze machines ruimte voor vier getallen, wat weinig lijkt, maar voor haast alle toepassingen voldoende is. Deze rekenmachines hadden geen haakjestoetsen en ook geen "="-toets om het resultaat van een berekening te tonen, maar wel een "Enter"-toets waarmee een getal op de stack werd geplaatst en die tevens diende als scheiding tussen twee getallen. Om bijvoorbeeld de berekening (27 x 38) / 13 uit te voeren, drukte men achtereenvolgens in 27 [enter] 38 × 13 ÷.

Een compiler van programmeertalen zet vaak eerst de uitdrukkingen om naar Poolse notatie omdat dat door een computer gemakkelijker te verwerken is.

De programmeertaal Lisp wordt volledig in prefixnotatie geschreven. Forth en daarvan afgeleide talen zoals PostScript gebruiken suffixnotatie.