Algoritmul de șantiere de marșă
Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de
versiunea revizuită la 3 iunie 2021; verificările necesită
2 modificări .
Algoritmul de triaj este o modalitate de a analiza expresii matematice și/sau logice reprezentate în notație infixă . Poate fi folosit pentru a produce notație poloneză inversă sau ieșire de arbore de sintaxă abstractă . Algoritmul a fost propus de Edsger Dijkstra și numit de acesta „algoritmul de triaj”, deoarece seamănă cu funcționarea unei stații de triaj feroviar .
La fel ca la calcularea valorilor expresiilor în notație poloneză inversă, algoritmul funcționează folosind o stivă . Notația infixă a expresiilor matematice este cea mai des folosită de oameni, exemplele sale sunt 2+4 și 3+6*(3-2). Pentru a converti la notația poloneză inversă, sunt utilizate 2 șiruri de caractere: intrare și ieșire și o stivă pentru a stoca instrucțiunile care nu au fost încă adăugate în coada de ieșire. La conversie, algoritmul citește 1 caracter și efectuează acțiuni în funcție de acest caracter.
Algoritm
- Până când toate jetoanele sunt procesate:
- Citiți simbolul .
- Dacă jetonul este un număr , adăugați-l în coada de ieșire.
- Dacă jetonul este o funcție , atunci împingeți-l pe stivă.
- Dacă simbolul este un separator de argumente ale funcției (de exemplu, o virgulă):
- Atâta timp cât jetonul din partea de sus a stivei nu este o paranteză deschisă:
- Împingeți instrucțiunea din stivă în coada de ieșire.
- Dacă stiva se termină înainte ca simbolul de deschidere a acoladei să fie întâlnit, atunci separatorul de argumente ale funcției (virgulă) este omis din expresia sau acolada de deschidere este omisă .
- Dacă jetonul este un operator op1 , atunci:
- Atâta timp cât există un operator token op2 în partea de sus a stivei, a cărui prioritate este mai mare sau egală cu cea a op1 și dacă prioritățile sunt egale, op1 este la stânga -asociativ :
- Împingeți op2 din stivă în coada de ieșire;
- Împingeți op1 pe stivă.
- Dacă jetonul este o paranteză deschisă , atunci împingeți-l pe stivă.
- Dacă simbolul este o acolade de închidere :
- Atâta timp cât jetonul de deasupra stivei nu este o paranteză deschisă
- Împingeți instrucțiunea din stivă în coada de ieșire.
- Dacă stiva se termină înainte ca simbolul parantezei de deschidere să fie întâlnit , atunci paranteza lipsește din expresie.
- Scoateți paranteza deschisă din stivă, dar nu o adăugați la coada de ieșire.
- Dacă jetonul din partea de sus a stivei este o funcție, împingeți-l în coada de ieșire.
- Dacă nu mai sunt jetoane rămase în intrare:
- Atâta timp cât există jetoane de operator pe stivă:
- Dacă simbolul operator din partea de sus a stivei este o paranteză deschisă , atunci paranteza lipsește din expresie.
- Împingeți instrucțiunea din stivă în coada de ieșire.
Fiecare număr de simbol, funcție sau operator este tipărit o singură dată, iar fiecare funcție de simbol, operator sau paranteză va fi adăugat și eliminat din stivă o dată. Număr constant de operații pe jeton, complexitatea liniară a algoritmului O( n ).
Link -uri