Järnvägsalgoritmen

Järnvägsalgoritmen (the shunting-yard algorithm) är en algoritm för att parsa ett uttryck givet i infixnotation. Den används ofta för att generera ett ekvivalent uttryck i omvänd polsk notation eller ett abstrakt syntaxträd (AST). Infixnotation är helt enkelt när man skriver matematiska uttryck på det sättet de flesta är vana vid, till exempel 3+4 eller 3+4*(2-1). Algoritmen uppfanns av Edsger Dijkstra och namnet kommer från att symbolerna i ett uttrycks "växlas" in på rätt "spår" (dvs en stack).

Järnvägsalgoritmen är stackbaserad och påminner om algoritmen för att evaluera ett AST. När man omvandlar uttryck med hjälp av järnvägsalgoritmen används två stycken textvariabler, indata och utdata. För att lagra operatorer som ännu inte lags till utdatan används en stack. Programmet läser varje symbol i uttrycket, i tur och ordning, och gör något beroende på vad det är för symbol.

En enkel omvandling 

Indata: 3+4
 Lägg till 3 i slutet av utdatakön (Alla tal som läses läggs till i utdatakön direkt)
 Lägg till "+" överst i operatorstacken
 Lägg till 4 i slutet av utdatakön
 När hela uttrycket har lästs in, läs operatorerna från operatorstacken och lägg till dem till utdatavariabeln.
 I det här fallet finns där bara "+"
 Utdata: 3 4 +

Detta enkla exempel visar på två regler:
 Alla tal som läses läggs till direkt i slutet av utdatavariabeln
 När hela uttrycket har lästs in så läggs de kvarvarande operatorerna på operatorstacken till i slutet av utdatavariabeln

Hur algoritmen fungerar 

 Så länge det finns symboler att läsa:
 Läs en symbol.
 Om symbolen är ett tal, lägg till den i slutet av utdatakön.
 Om symbolen är en funktionssymbol, lägg till den på stacken.
 Om symbolen är en avskiljare för funktionsargument (vanligtvis ett komma):
 Hämta operatorer från stacken och lägg till utdatakön tills symbolen högst upp på stacken är en vänsterparentes. Om ingen vänsterparentes hittas så var avskiljaren felplacerad eller så matchar inte uttryckets parenteser varandra.
 Om symbolen är en operator, o1:
 Medan det finns en operator, o2, högst upp på stacken och antingen:
 o1 är associativ eller vänsterassociativ och dess prioritet är lägre än eller lika med o2s prioritet, eller
 o1 är högerassociativ och dess prioritet är mindre än o2s,
 hämta o2 från stacken och lägg den på utdatakön
 lägg o1 på stacken.
 Om symbolen är en vänsterparentes, lägg den på stacken.
 Om symbolen är en högerparentes:
 Tills den översta symbolen på stacken är en vänsterparentes, hämta operatorer från stacken och lägg dem i utdatakön.
 Hämta vänsterparentesen från stacken, men lägg den inte i utdatakön.
 Om symbolen högst upp på stacken är en funktionssymbol, lägg den i utdatakön.
 Om stacken tar slut och ingen vänsterparentes har hittats så matchar inte parenteserna i uttrycket varandra.
 När alla symboler har lästs in:
 Medan det finns operatorsymboler på stacken:
 Om operatorsymbolen högst upp på stacken är en parentes så matchar inte uttryckets parenteser varandra.
 Lägg operatorn i utdatakön
 Slut.

Komplexitet 
Algoritmens tidskomplexitet är O(n), linjär med storleken på indatat, eftersom:
 Varje symbol läses endast en gång
 Varje siffra, funktion eller operator bara skrivs ut en gång
 Varje funktion operator eller parentes bara läggs på stacken och hämtas från stacken en enda gång
Det maximala antalet operationer per symbol är alltså konstant.

Ett utförligt exempel

Se även 
 Operatorprioritet
 Postfixnotation
 Edsger Dijkstra

Externa länkar 
 Information om parsning och järnvägsalgoritmen (på svenska) © Jonas Wallgren, Linköpings Universitet
 Java-applet som demonstrerar järnvägsalgoritmen (engelskspråkig sida)
 Parsing Expressions by Recursive Descent (engelskspråkig sida) Theodore Norvell (C) 1999–2001. Access data September 14, 2006.
 Infix till RPN-algoritm (engelskspråkig sida) 
 Första beskrivningen av järnvägsalgoritmen, Dijkstra 1961 (engelskspråkig sida)
 En utökning av järnvägsalgoritmen för att tillåta ett varierande antal funktionsargument (engelskspråkig sida)

Källor 

Algoritmer