# 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

    Input: 3+4
* Stop 3 in de output stack (als er een nummer gelezen wordt, steeds in de output)
* Push + op de operator stack
* Stop 4 in de output
* Na het geheel gelezen te hebben, pop alle elementen van de stack en zet ze op de output.
* In deze situatie is er maar één operator.
* 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$_1$, dan:
*** zolang er een operator o$_2$ bovenaan op de stack ligt en:
**** of o$_1$ is links associatief en zijn voorrang is kleiner of gelijk aan die van o$_2$
**** of o$_1$ is rechts associatief en zijn voorrang is kleiner dan o$_2$,
*** haal o$_2$ van de operator stack en zet die die op output
*** zet o$_1$ 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 ^ ^ / + | | |