Marshalling yard algoritme
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den
version , der blev gennemgået den 3. juni 2021; checks kræver
2 redigeringer .
Rangergårdsalgoritmen er en måde at analysere matematiske og/eller logiske udtryk repræsenteret i infix-notation . Kan bruges til at producere omvendt polsk notation eller abstrakt syntakstræoutput . Algoritmen blev foreslået af Edsger Dijkstra og af ham kaldt "rangerpladsalgoritmen", da den minder om driften af en rangerbanegård .
Ligesom at beregne værdierne af udtryk i omvendt polsk notation, fungerer algoritmen ved hjælp af en stak . Infiksnotationen af matematiske udtryk bruges oftest af mennesker, dens eksempler er 2+4 og 3+6*(3-2). For at konvertere til omvendt polsk notation, bruges 2 strenge: input og output, og en stak til at gemme udsagn, der endnu ikke er tilføjet til outputkøen. Ved konvertering læser algoritmen 1 tegn og udfører handlinger afhængigt af denne karakter.
Algoritme
- Indtil alle tokens er behandlet:
- Læs token .
- Hvis tokenet er et tal , skal du tilføje det til outputkøen.
- Hvis tokenet er en funktion , så skub det ind på stakken.
- Hvis tokenet er en funktionsargumentseparator (f.eks. et komma):
- Så længe tokenet på toppen af stakken ikke er en åben parentes:
- Skub sætningen fra stakken til outputkøen.
- Hvis stakken slutter, før åbningsparentesen er stødt på, udelades funktionen argumentseparator (komma) fra udtrykket , eller åbningsparentesen udelades .
- Hvis tokenet er en op1- operator , så:
- Så længe der er en token - operator op2 i toppen af stakken, hvis forrang er større end eller lig med op1, og hvis prioriteterne er ens, er op1 venstre -associativ :
- Skub op2 fra stakken til outputkøen;
- Skub op1 på stakken.
- Hvis tokenet er en åben parentes , så skub den ind på stakken.
- Hvis tokenet er en lukkebøjle :
- Så længe tokenet på toppen af stakken ikke er en åben parentes
- Skub sætningen fra stakken til outputkøen.
- Hvis stakken slutter før åbningsparentesen token er stødt på , så mangler parentesen i udtrykket.
- Pop den åbne parentes ud af stakken, men føj den ikke til outputkøen.
- Hvis tokenet i toppen af stakken er en funktion, skal du skubbe det til outputkøen.
- Hvis der ikke er flere tokens tilbage i inputtet:
- Så længe der er operatør-tokens på stakken:
- Hvis operatortokenet i toppen af stakken er en åben parentes , mangler parentesen i udtrykket.
- Skub sætningen fra stakken til outputkøen.
Hvert token-nummer, hver funktion eller operator udskrives kun én gang, og hver token-funktion, operator eller parentes tilføjes og fjernes fra stakken én gang. Konstant antal operationer pr. token, lineær kompleksitet af algoritmen O( n ).
Links