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

Algoritm

Under­klass till	algoritm
Inda­ta­mängd	Infixnotation
Pro­du­ce­rar	omvänd polsk notation

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

1. Lägg till 3 i slutet av utdatakön (Alla tal som läses läggs till i utdatakön direkt)
2. Lägg till "+" överst i operatorstacken
3. Lägg till 4 i slutet av utdatakön
4. När hela uttrycket har lästs in, läs operatorerna från operatorstacken och lägg till dem till utdatavariabeln.
5. I det här fallet finns där bara "+"
6. 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, o₁:
    • Medan det finns en operator, o₂, högst upp på stacken och antingen:
      • o₁ är associativ eller vänsterassociativ och dess prioritet är lägre än eller lika med o₂s prioritet, eller
      • o₁ är högerassociativ och dess prioritet är mindre än o₂s,
    • hämta o₂ från stacken och lägg den på utdatakön
    • lägg o₁ 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

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

Symbol	Behandling	Utdata (i omvänd polsk notation)	Operatorstack	Anteckning
3	Lägg till symbol i utdata	3
+	Lägg symbol på stacken	3	+
4	Lägg till symbol i utdata	3 4	+
*	Lägg symbol på stacken	3 4	* +	* har högre prioritet än +
2	Lägg till symbol i utdata	3 4 2	* +
/	Lägg översta i stacken i utdata	3 4 2 *	+	/ och * har samma prioritet
	Lägg symbol på stacken	3 4 2 *	/ +	/ har högre prioritet än +
(	Lägg symbol på stacken	3 4 2 *	( / +
1	Lägg till symbol i utdata	3 4 2 * 1	( / +
-	Lägg symbol på stacken	3 4 2 * 1	- ( / +
5	Lägg till symbol i utdata	3 4 2 * 1 5	- ( / +
)	Lägg översta i stacken i utdata	3 4 2 * 1 5 -	( / +	Upprepas tills ett "(" hittas
	Ta bort översta elementet på stacken	3 4 2 * 1 5 -	/ +	Kasta bort den matchande parentesen
^	Lägg symbol på stacken	3 4 2 * 1 5 -	^ / +	^ har högre prioritet än /
2	Lägg till symbol i utdata	3 4 2 * 1 5 - 2	^ / +
^	Lägg symbol på stacken	3 4 2 * 1 5 - 2	^ ^ / +	^ läses från höger till vänster
3	Lägg till symbol i utdata	3 4 2 * 1 5 - 2 3	^ ^ / +
slut	Lägg hela stacken i utdata	3 4 2 * 1 5 - 2 3 ^ ^ / +

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

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia.