|
|
Dijkstras vigesporsalgoritme
Dijkstras vigesporsalgoritme bruges til at omskrive et udtruk i almindelig infixnotation til postfixnotation. Algoritmen bruger en stak til omskrivningen. Stakken bruges som et vigespor for operatorerne i uudtrykket. Tallene i udtrykket står i sammen 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
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 en ny operand 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:
- 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.
Denne artikel er fra Wikipedia. Læs artiklen hos Wikipedia.
|
|