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 (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.