Järnvägsalgoritmen
Järnvägsalgoritmen
| Underklass till | algoritm  | |
|---|---|---|
| Indatamängd | Infixnotation | |
| Producerar | omvänd polsk notation | |
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
[redigera | redigera wikitext]- 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
[redigera | redigera wikitext]- 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.
- Medan det finns en operator, o2, högst upp på stacken och antingen:
- 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
- Medan det finns operatorsymboler på stacken:
- Slut.
Komplexitet
[redigera | redigera wikitext]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
[redigera | redigera wikitext]| 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
[redigera | redigera wikitext]Externa länkar
[redigera | redigera wikitext]- 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
[redigera | redigera wikitext]- Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia.