Shunting-yardalgoritme

Het shunting-yardalgoritme (rangeerstationalgoritme) is een methode om een mathematische uitdrukking geschreven in infixnotatie te verwerken. Het algoritme is uitgevonden door de Nederlandse wetenschapper Edsger Dijkstra. De metafoor met het rangeerstation vindt zijn oorsprong daarin dat de werking van het algoritme lijkt op het samenstellen van treinstellen in een rangeerstation.

Het shunting-yardalgoritme is een stack-based algoritme. De infixuitdrukkingen zijn het meest gangbaar in wiskundige kringen, zoals 3 + 4 of 3 + 4 × (2 − 1). De conversie naar de postfixnotatie gebeurt door middel van een input- en een outputtekst die beide in een stack zitten. Een derde stack houdt de operators bij die nog niet aan de output zijn toegevoegd. Om de omzetting door te voeren, leest het programma elk symbool in en voegt dit, afhankelijk van het symbool, toe op de juiste stack.

Een eenvoudige omzetting

Grafische presentatie van het algoritme, gebruikmakend van een driewegsspoorwegkruispunt. De input wordt symbool voor symbool verwerkt. Als een variabele of een getal gevonden wordt, wordt deze direct naar de output geschreven: (b), (d), (f), (h). Als het symbool een operator is, wordt dit op de operator stack gezet: (c), (e). Als de voorrang echter minder is dan die van de bovenste op de stack of gelijk is aan de voorrang, en het nieuwe element is links associatief, dan wordt het element van de stack gehaald en op de output stack gezet (g). Tot slot worden de laatste operators op de output stack gezet.

Input: 3+4

1. Stop 3 in de output stack (als er een nummer gelezen wordt, steeds in de output)
2. Push + op de operator stack
3. Stop 4 in de output
4. Na het geheel gelezen te hebben, pop alle elementen van de stack en zet ze op de output.
5. In deze situatie is er maar één operator.
6. Output 3 4 +

Dit eenvoudige voorbeeld geeft al meteen een beeld van enkele regels:

• Alle nummers worden rechtstreeks op de output gezet
• Op het einde van de inputexpressie worden alle operators op de output stack gezet.

Het algoritme in details

• Zolang er nog tokens te lezen zijn:
  • Lees een token
  • Is de token een getal of variabele, zet het op de output
  • Is de token een functie, zet die dan op de operator stack
  • Is de token een functieargumentseparator (bijvoorbeeld een komma):
    • Pop operators van de stack op de output tot er een linker haakje gevonden wordt. Als er geen linker haakje gevonden wordt, was er een fout in de uitdrukking.
  • Is de token een operator o₁, dan:
    • zolang er een operator o₂ bovenaan op de stack ligt en:
      • of o₁ is links associatief en zijn voorrang is kleiner of gelijk aan die van o₂
      • of o₁ is rechts associatief en zijn voorrang is kleiner dan o₂,
    • haal o₂ van de operator stack en zet die die op output
    • zet o₁ op de operator stack
  • Is de token een linker haakje, zet het dan op de stack
  • Is de token een rechter haakje:
    • Tot de token op de top van de stack een linker haakje is, haal operators van de stack en zet ze op de output.
    • Pop het linker haakje van de stack, maar zet het niet op de output!
    • Als de token op de top van de stack nu een functie is, pop het op de output.
    • Als de stack leeg loopt zonder een linker haakje te vinden, dan zit er een fout in de formule.
• Als er geen tokens meer over zijn:
  • Zolang er nog operators op de stack staan
    • Als de operator token een haakje is, dan zit er een fout in de formule.
    • Zet de operator op de output que
• Stop

Gedetailleerd voorbeeld

Input: 3 + 4 * 2 / ( 1 − 5 ) ^ 2 ^ 3

operator	voorrang	associativiteit
^	4	Rechts
*	3	Links
/	3	Links
+	2	Links
−	2	Links

Token	Actie	Output (in RPN)	Operator stack	Opmerking
3	Token toevoegen aan output	3
+	Push token op stack	3	+
4	Token toevoegen aan output	3 4	+
*	Push token op stack	3 4	* +	* heeft hogere voorrang dan +
2	Token toevoegen aan output	3 4 2	* +
/	Pop stack op output	3 4 2 *	+	/ en * hebben dezelfde voorrang
	Push token op stack	3 4 2 *	/ +	/ heeft hogere voorrang dan +
(	Push token op stack	3 4 2 *	( / +
1	Token toevoegen aan output	3 4 2 * 1	( / +
−	Push token op stack	3 4 2 * 1	− ( / +
5	Token toevoegen aan output	3 4 2 * 1 5	− ( / +
)	Pop stack op output	3 4 2 * 1 5 −	( / +	Herhaald tot ( wordt gevonden
	Pop stack	3 4 2 * 1 5 −	/ +	Overeenkomstige haakjes weggooien
^	Push token op stack	3 4 2 * 1 5 −	^ / +	^ heeft hogere voorrang dan /
2	Token toevoegen aan output	3 4 2 * 1 5 − 2	^ / +
^	Push token op stack	3 4 2 * 1 5 − 2	^ ^ / +	^ wordt van links naar rechts geëvalueerd
3	Token toevoegen aan output	3 4 2 * 1 5 − 2 3	^ ^ / +
einde	Volledige stack op de output zetten	3 4 2 * 1 5 − 2 3 ^ ^ / +