Dijkstras vigesporsalgoritme

Dijkstras vigesporsalgoritme bruges til at omskrive et udtryk i almindelig infixnotation til postfixnotation. Algoritmen bruger en stak til omskrivningen. Stakken bruges som et vigespor for operatorerne i udtrykket. Tallene i udtrykket står i samme rækkefølge som i infixnotation, men operatorerne får nye placeringer.

Algoritmen

• Udtrykket pakkes ind i start- og sluttegn som f.eks. '='
• Alle tal kører forbi vigesporet efterhånden som omskrivningen når frem til dem
• Det første = køres ud på vigesporet
• Herefter er der følgende muligheder

1. Det aktuelle symbol køres ud på vigesporet
2. Det nærmeste symbol køres tilbage fra vigesporet
3. Det aktuelle symbol og symbolet på vigesporet ophæver hinanden, og begge fjernes
4. Stop udtrykket er omskrevet
5. Stop der var fejl i det oprindelige udtryk

Hvad, der skal ske fremgår af dette skema:

Omsætningstabel

Symbol på vigesporet	Aktuelt symbol
	=	+	-	*	/	(	)
=	4	1	1	1	1	1	5
+	2	2	2	1	1	1	2
-	2	2	2	1	1	1	2
*	2	2	2	2	2	1	2
/	2	2	2	2	2	1	2
(	5	1	1	1	1	1	3

Skemaet skal både bruges når der er et nyt symbol i udtrykket og når der er tilføjet eller fjernet et symbol på vigesporet.

Eksempel

Omskrivning af udtrykket = 2 + 3 * 4 = sker på denne måde:

1. Det første = kommer på vigesporet. Udtryk: 2 + 3 * 4 = Vigespor: = Postfix:
2. Tallet flyttes over. Udtryk: + 3 * 4 = Vigespor: = Postfix: 2
3. + kommer på vigesporet. Udtryk: 3 * 4 = Vigespor: = + Postfix: 2
4. Tallet flyttes over. Udtryk: * 4 = Vigespor: = + Postfix: 2 3
5. * kommer på vigesporet. Udtryk: 4 = Vigespor: = + * Postfix: 2 3
6. Tallet flyttes over. Udtryk = Vigespor: = + * Postfix: 2 3 4
7. * hentes fra vigesporet. Udtryk: = Vigespor: = + Postfix: 2 3 4 *
8. + hentes fra vigesporet. Udtryk: = Vigespor: = Postfix: 2 3 4 * +
9. = fjernes fra vigesporet, og udtrykket er omsat.