Shunting-yardalgoritme

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

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-basedalgoritme. 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[bewerken]

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[bewerken]

  • 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 o1, dan:
      • zolang er een operator o2 bovenaan op de stack ligt en:
        • of o1 is links associatief en zijn voorrang is kleiner of gelijk aan die van o2
        • of o1 is rechts associatief en zijn voorrang is kleiner dan o2,
      • haal o2 van de operator stack en zet die die op output
      • zet o1 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[bewerken]

Input: 3 + 4 * 2 / ( 1 − 5 ) ^ 2 ^ 3
operator voorrang associatieviteit
^ 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 ^ ^ / +
end Volledige stack op de output zetten 3 4 2 * 1 5 − 2 3 ^ ^ / +