Dijkstras vigesporsalgoritme
Fra Wikipedia, den frie encyklopædi
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.
[redigér] 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
- Det aktuelle symbol køres ud på vigesporet
- Det nærmeste symbol køres tilbage fra vigesporet
- Det aktuelle symbol og symbolet på vigesporet ophæver hinanden, og begge fjernes
- Stop udtrykket er omskrevet
- Stop der var fejl i det oprindelige udtryk
Hvad, der skal ske fremgår af dette skema:
| 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.
[redigér] Eksempel
Omskrivning af udtrykket = 2 + 3 * 4 = sker på denne måde:
- Det første = kommer på vigesporet. Udtryk: 2 + 3 * 4 = Vigespor: = Postfix:
- Tallet flyttes over. Udtryk: + 3 * 4 = Vigespor: = Postfix: 2
- + kommer på vigesporet. Udtryk: 3 * 4 = Vigespor: = + Postfix: 2
- Tallet flyttes over. Udtryk: * 4 = Vigespor: = + Postfix: 2 3
- * kommer på vigesporet. Udtryk: 4 = Vigespor: = + * Postfix: 2 3
- Tallet flyttes over. Udtryk = Vigespor: = + * Postfix: 2 3 4
- * hentes fra vigesporet. Udtryk: = Vigespor: = + Postfix: 2 3 4 *
- + hentes fra vigesporet. Udtryk: = Vigespor: = Postfix: 2 3 4 * +
- = fjernes fra vigesporet, og udtrykket er omsat.
