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.