Järjestyspihan algoritmi
Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 3.6.2021 tarkistetusta
versiosta . tarkastukset vaativat
2 muokkausta .
Järjestämispistealgoritmi on tapa jäsentää matemaattisia ja/tai loogisia lausekkeita, jotka esitetään infix-merkinnällä . Voidaan käyttää tuottamaan käänteistä puolalaista notaatiota tai abstraktia syntaksipuutulostetta . Algoritmin ehdotti Edsger Dijkstra , ja hän nimesi sen "järjestelypiha-algoritmiksi", koska se muistuttaa rautatien järjestelypihan toimintaa .
Samoin kuin lausekkeiden arvojen laskeminen käänteisessä puolan merkinnässä, algoritmi toimii pinon avulla . Useimmiten ihmiset käyttävät matemaattisten lausekkeiden infix-merkintää, sen esimerkkejä ovat 2+4 ja 3+6*(3-2). Käänteiseen puolalaiseen merkintään muunnettaessa käytetään kahta merkkijonoa: tuloa ja lähtöä sekä pinoa sellaisten lauseiden tallentamiseen, joita ei ole vielä lisätty tulostusjonoon. Muunnettaessa algoritmi lukee 1 merkin ja suorittaa toimintoja tämän merkin mukaan.
Algoritmi
- Kunnes kaikki tunnukset on käsitelty:
- Lue tunnus .
- Jos tunnus on numero , lisää se tulosjonoon.
- Jos merkki on funktio , työnnä se pinoon.
- Jos tunnus on funktion argumenttien erotin (esimerkiksi pilkku):
- Niin kauan kuin pinon päällä oleva merkki ei ole avoin sulkumerkki:
- Työnnä käsky pinosta tulostusjonoon.
- Jos pino päättyy ennen kuin avausalkasulke kohdataan, funktion argumenttierotin (pilkku) jätetään pois lausekkeesta tai avausalkumerkki jätetään pois .
- Jos tunnus on op1 - operaattori , niin:
- Niin kauan kuin pinon yläosassa on token- operaattori op2, jonka ensisijaisuus on suurempi tai yhtä suuri kuin op1, ja jos prioriteetit ovat samat, op1 on vasen -assosiatiivinen :
- Työnnä op2 pinosta lähtöjonoon;
- Työnnä op1 pinoon.
- Jos merkki on avoin sulkumerkki , työnnä se pinoon.
- Jos merkki on sulkeva aaltosulje :
- Niin kauan kuin pinon päällä oleva merkki ei ole avoin sulkumerkki
- Työnnä käsky pinosta tulostusjonoon.
- Jos pino päättyy ennen kuin avaava sulkumerkki löytyy , sulku puuttuu lausekkeesta.
- Nosta avoimet sulut pois pinosta, mutta älä lisää sitä tulostusjonoon.
- Jos pinon yläosassa oleva merkki on funktio, työnnä se tulosjonoon.
- Jos syötteessä ei ole enää tunnuksia:
- Niin kauan kuin pinossa on operaattoritunnuksia:
- Jos pinon yläosassa oleva operaattoritunnus on avoin sulkumerkki , sulku puuttuu lausekkeesta.
- Työnnä käsky pinosta tulostusjonoon.
Jokainen tunnusnumero, funktio tai operaattori tulostetaan vain kerran, ja jokainen merkkifunktio, operaattori tai sulku lisätään ja poistetaan pinosta kerran. Vakio operaatioiden määrä vuoromerkkiä kohti, algoritmin O( n ) lineaarinen monimutkaisuus.
Linkit