Notație poloneză inversă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 28 septembrie 2021; verificările necesită 2 modificări .

Notația poloneză inversă (RPN ) este o formă de scriere a expresiilor matematice și logice în care operanzii sunt localizați înaintea semnelor operației . De asemenea, denumită notație inversă fără paranteze , notație postfixă , simbolismul lui Lukasiewicz fără paranteze , notație inversă poloneză , POLIZ .

O mașină de stivă este un algoritm care efectuează calcule folosind notația poloneză inversă (vezi mai jos un exemplu de evaluare a expresiilor ).

Istorie

Notația poloneză inversă (RPN) a fost dezvoltată de filozoful și teoreticianul computerului australian Charles Hamblin la mijlocul anilor 1950, pe baza notației poloneze , care a fost propusă în 1920 de matematicianul polonez Jan Lukasiewicz . Lucrarea lui Hamblin a fost prezentată la o conferință în iunie 1957 și publicată în 1957 și 1962 .

Primele computere care au suportat notația inversă poloneză au fost KDF9 de la English Electric Company , care a fost anunțată în 1960 și lansat (a apărut pentru vânzare) în 1963 , și americanul Burroughs B5000 , anunțat în 1961 , lansat în același 1963. designerii B5000, R. S. Barton , au scris mai târziu că a dezvoltat notația poloneză inversă independent de Hamblin în jurul anului 1958, în timp ce citea o carte despre logica simbolică și înainte de a se familiariza cu opera lui Hamblin.

Friden a adus descărcătorul de supratensiune la calculatoarele desktop cu EC-130 din iunie 1964. Și în 1968, inginerii Hewlett-Packard au dezvoltat calculatorul de birou 9100A cu suport pentru descărcător de supratensiune. Acest calculator a făcut ca notația poloneză inversă să fie populară printre oamenii de știință și ingineri, chiar dacă anunțul 9100A timpuriu nu menționa descărcătorul de supratensiune. În 1972 , calculatorul HP-35 SPD a devenit primul calculator științific de buzunar .

În 1971, a apărut limbajul de programare original Forth , a cărui mașină de limbaj are o structură cu două stive și în care toate calculele sunt efectuate pe stivă . În acest limbaj, OPN este o modalitate naturală de a scrie orice operațiuni de date, deși este posibil, dacă se dorește, să se implementeze notația obișnuită ( infixă ) a operațiilor aritmetice.

Descărcătorul a fost folosit în calculatorul de inginerie sovietic B3-19M (dezvoltat în comun cu RDG), lansat în 1976. Toate microcalculatoarele programabile produse în URSS până la sfârșitul anilor 1980 , cu excepția Elektronika MK-85 și Elektronika MK-90 , foloseau un descărcător - a fost mai ușor de implementat și a făcut posibil să se descurce în calculele de programare cu un dispozitiv mai mic. numărul de comenzi, în comparație cu notația algebrică obișnuită, iar cantitatea de memorie de program din aceste modele a fost întotdeauna o resursă critică. Descărcătorul este utilizat în calculatoarele programabile rusești moderne „ Elektronika MK-152 ” și „ Elektronika MK-161 ”, ceea ce asigură compatibilitatea acestora cu programele scrise pentru calculatoarele sovietice.

Definiție

Pentru a da o definiție inductivă a notației postfixe [1] , să notăm expresii în notație infixă , , , expresiile lor echivalente în notație postfixă , , respectiv; este un operator binar arbitrar, atunci: $E$ $E_1$ $E_2$ $\punct E$ $\dot E_1$ $\dot E_2$ $o$

1. Dacă - o variabilă sau o constantă, adică . $E$ $\punct E$ $E$

2. Dacă este o expresie de forma , adică . $E$ $E_1 sau E_2$ $\punct E$ $\dot E_1 \dot E_2 o$

3. Dacă este o expresie de forma , adică . $E$ $(E_1)$ $\punct E$ $\dot E_1$

Descriere

O caracteristică distinctivă a notației poloneze inverse este că toate argumentele (sau operanzii ) sunt plasați înaintea semnului operației. În general, înregistrarea arată astfel:

O înregistrare de set de operații constă dintr-o secvență de operanzi și semne de operație. Operanzii dintr-o expresie sunt separați prin spații atunci când sunt scrisi.
Expresia se citește de la stânga la dreapta. Atunci când într-o expresie apare un semn de operator, operația corespunzătoare este efectuată asupra ultimilor doi operanzi care apar înaintea acesteia, în ordinea în care sunt scrise. Rezultatul operației înlocuiește succesiunea operanzilor săi și semnul acesteia în expresie, după care expresia este evaluată în continuare după aceeași regulă.
Rezultatul evaluării expresiei este rezultatul ultimei operații evaluate.

De exemplu, luați în considerare evaluarea unei expresii 7 2 3 * −(expresia echivalentă în notație infixă: 7 − 2 * 3).

Primul semn al operației este „*”, deci operația de înmulțire se realizează mai întâi pe operanzii 2 și 3 (sunt ultimii înaintea semnului). Expresia este apoi convertită în formă 7 6 −(rezultatul înmulțirii - 6 - înlocuiește triplul "2 3 *").
Al doilea caracter al operației este „−”. O operație de scădere este efectuată pe operanzii 7 și 6.
Calcul finalizat. Rezultatul ultimei operații este 1, acesta este rezultatul evaluării expresiei.

O extensie evidentă a notației poloneze inverse la operații unare, ternare și cu orice alt număr de operanzi: atunci când se utilizează semnele unor astfel de operații în evaluarea unei expresii, operația este aplicată numărului corespunzător de ultimii operanzi întâlniți.

Caracteristicile notației poloneze inverse sunt următoarele:

Ordinea de execuție a operațiilor este specificată fără ambiguitate de ordinea semnelor de operație din expresie, deci nu este nevoie să folosiți paranteze și să introduceți prioritățile și asociativitatea operațiilor.
Spre deosebire de notația infix, nu este posibil să folosiți aceleași caractere pentru a scrie operații unare și binare. Deci, în notația infixă, expresia 5 * (−3 + 8)folosește semnul minus ca simbol al unei operații unare (schimbarea semnului unui număr), iar expresia (10 − 15) * 3folosește același semn pentru a desemna o operație binară (scădere). Operația specifică este determinată de poziția personajului. Notația poloneză inversă nu permite acest lucru: notația 5 3 − 8 + *(analogul condiționat al primei expresii) va fi interpretată ca eronată, deoarece este imposibil să se determine că „minus” după 5 și 3 nu înseamnă o scădere; ca urmare, se va încerca să se calculeze mai întâi 5 − 3, apoi 2 + 8, după care se dovedește că nu sunt destui operanzi pentru operația de înmulțire. Pentru a scrie în continuare această expresie, va trebui fie să o reformulați (de exemplu, prin scrierea expresiei în loc de − 3expresia 0 − 3), fie să introduceți o denumire separată pentru operația de schimbare a semnului, de exemplu, „±”: 5 3 ± 8 + *.
La fel ca și în notație infixă, în OPN unul și același calcul poate fi scris în mai multe versiuni diferite. De exemplu, o expresie (10 − 15) * 3din OPN poate fi scrisă ca 10 15 − 3 *, sau o puteți scrie ca3 10 15 − *
Din cauza lipsei parantezelor, notația poloneză inversă este mai scurtă decât infix. Din acest motiv, atunci când se calculează pe calculatoare, viteza de lucru a operatorului crește (numărul de taste apăsate este redus), iar în dispozitivele programabile, volumul acelor părți ale programului care descriu calculele este redus. Acesta din urmă poate fi important pentru dispozitivele de calcul portabile și încorporate care au limitări severe ale cantității de memorie.

Calcule stive

Ordine generală

Automatizarea evaluării expresiilor în notație poloneză inversă se bazează pe utilizarea unei stive . Algoritmul de calcul pentru mașina de stivă este elementar:

Procesarea simbolurilor de intrare
- Dacă un operand este dat ca intrare, acesta este împins în partea de sus a stivei.
- Dacă intrării i se dă un semn de operație, atunci operația corespunzătoare este efectuată pe numărul necesar de valori ieșite din stivă, luate în ordinea adunării. Rezultatul operației efectuate este plasat în partea de sus a stivei.
Dacă setul de caractere introdus nu este complet procesat, treceți la pasul 1.
După ce setul de caractere de intrare a fost complet procesat, rezultatul evaluării expresiei se află în partea de sus a stivei.

Implementarea unei mașini de stivă, atât în software cât și în hardware, este extrem de simplă și poate fi foarte eficientă. Notația poloneză inversă este complet unificată - practic scrie operații unare, binare, ternare și orice alte operațiuni, precum și apeluri de funcții în același mod, ceea ce permite să nu complice proiectarea dispozitivelor de calcul în timp ce extinde setul de operațiuni acceptate. Acesta a fost motivul pentru utilizarea notației poloneze inverse în unele calculatoare științifice și programabile.

Exemplu de evaluare a expresiei

O expresie infixă într-un GRE poate fi scrisă astfel: $(1 + 2)\ori 4 + 3$ 1 2 + 4 × 3 +

Calculul se face de la stânga la dreapta, intrarea este interpretată așa cum este indicat în tabelul de mai jos (este indicată starea stivei după operație, partea de sus a stivei este evidențiată cu roșu ):

Intrare	Operațiune	Grămadă
unu	pus pe stivă	unu
2	pus pe stivă	1, 2
+	plus	3
patru	pus pe stivă	3, 4
*	multiplicare	12
3	pus pe stivă	12, 3
+	plus	cincisprezece

Rezultatul, 15, este în vârful stivei la sfârșitul calculului.

Tasta „Enter” (notată pe calculatoare ca „Enter” sau simbolul „↑”) acționează ca un separator de operanzi atunci când doi operanzi sunt imediat adiacenți unul celuilalt. Dacă operandul este urmat de semnul operației , atunci apăsarea acestuia nu este necesară, aceasta reduce numărul de acțiuni care trebuie efectuate pentru a obține rezultatul.

Convertirea din notația infixă

Edsger Dijkstra a inventat un algoritm pentru conversia expresiilor din notația infixă în IPV. Algoritmul a fost denumit „centre de triaj”, pentru asemănarea operațiunilor sale cu ceea ce se întâmplă la stațiile de triaj feroviar. Notația infixă este forma de notație matematică pe care o folosesc majoritatea oamenilor (de exemplu, 3 + 4sau 3 + 4 * (2 − 1)). La fel ca algoritmul de calcul SPV , algoritmul de triaj se bazează pe o stivă. Există două variabile de text implicate în conversie: șiruri de intrare și de ieșire. Procesul de conversie folosește o stivă care stochează operațiuni care nu au fost încă adăugate la șirul de ieșire. Programul de conversie citește șirul de intrare caracter cu caracter în secvență (un caracter nu este neapărat o literă), efectuează unele acțiuni la fiecare pas, în funcție de caracterul citit.

Un exemplu simplu

Intrare:3 + 4

Adăugați 3la linia de ieșire (dacă este citit un număr, acesta este adăugat imediat la linia de ieșire).

Împingeți +(sau identificatorul acestuia) pe stiva de operații.

Adăugați 4la linia de ieșire.

Am citit întreaga expresie, acum împingem toate operațiunile rămase pe stivă la linia de ieșire. În exemplul nostru, stiva conține doar +.

Linie de ieșire:3 4 +

În acest exemplu, apar câteva reguli: toate numerele sunt transferate pe linia de ieșire imediat după citire; când expresia este citită complet, toate operațiunile rămase pe stivă sunt împinse la linia de ieșire.

Algoritm

Deși există mai multe personaje de citit:

Citim următorul personaj.
Dacă caracterul este un număr sau o funcție postfix (de exemplu, ! - factorial ), adăugați-l la șirul de ieșire.
Dacă simbolul este o funcție de prefix (de exemplu, sin - sinus ), împingeți-l pe stivă.
Dacă personajul este o paranteză deschisă, împingeți-l pe stivă.
Dacă caracterul este o paranteză de închidere:

Până când elementul superior al stivei este paranteza de deschidere, scoateți elementele din stivă pe șirul de ieșire. Aceasta elimină acolada de deschidere din stivă, dar nu o adaugă la șirul de ieșire. Dacă stiva sa încheiat înainte de a întâlni paranteza de deschidere, aceasta înseamnă că fie delimitatorul este plasat incorect în expresie, fie parantezele nu sunt potrivite.

Dacă există diferite tipuri de paranteze, apariția unui parantez nepotrivit indică, de asemenea, o eroare. Dacă unele paranteze sunt funcții în același timp (de exemplu, [x] este o parte întreagă ), adăugăm simbolul acestei funcție la șirul de ieșire.

Dacă simbolul este operația binară o1 , atunci:

1) în timp ce în partea de sus a stivei este o funcție de prefix... … SAU operațiunea din partea de sus a stivei are o prioritate mai mare sau același nivel de prioritate ca o1 … SAU operația de vârf a stivei este asociativă stângă cu prioritate ca o1 ... împingeți elementul superior al stivei către șirul de ieșire; 2) împingeți operația o1 pe stivă.

Când șirul de intrare se termină, treceți toate caracterele din stivă în șirul de ieșire. Numai simbolurile operațiunii trebuiau să rămână pe stivă; dacă nu este, atunci expresia nu se potrivește între paranteze.

Limitări și modificări

Algoritmul presupune că șirul sursă este corect (nu toate erorile sunt verificate), iar toate funcțiile de prefix/postfix sunt unare.

Consultați articolul principal pentru o modificare pentru funcțiile cu mai multe locuri cu un număr fix de argumente .

Pentru operațiuni precum -x care sunt atât binare, cât și unare, este necesară o modificare: atunci când se găsește o astfel de operație, sistemul se uită la caracterul anterior și determină dacă minusul este o operație binară sau o funcție unară. În consecință, stiva și NPV au nevoie de simboluri diferite pentru minusul binar și unar.

Exemplu complex

Prioritati :

cea mai mare: expresii cuprinse între paranteze ( )
înalt: ^
in medie: * /
scăzut: + −

Intrare: 3 + 4 * 2 / (1 - 5)^2 Citim "3" Adăugați „3” la șirul de ieșire Ieșire: 3 Citim „+” Pune „+” pe stivă Ieșire: 3 Stivă: + Citim "4" Adăugați „4” la șirul de ieșire Ieșire: 3 4 Stivă: + Noi citim "*" Apăsați „*” pe stivă Ieșire: 3 4 Stivă: + * Citim "2" Adăugați „2” la șirul de ieșire Ieșire: 3 4 2 Stivă: + * Noi citim "/" Apăsați „*” din stivă în șirul de ieșire, apăsați „/” pe stivă Ieșire: 3 4 2 * Stivă: + / Noi citim "(" Apăsați „(” pe stivă Ieșire: 3 4 2 * Stivă: + / ( Citim "1" Adăugați „1” la șirul de ieșire Ieșire: 3 4 2 * 1 Stivă: + / ( Noi citim "-" Apăsați „-” pe stivă Ieșire: 3 4 2 * 1 Stivă: + / ( − Citim "5" Adăugați „5” la șirul de ieșire Ieșire: 3 4 2 * 1 5 Stivă: + / ( - Noi citim ")" Apăsați „−” din stivă în șirul de ieșire, apăsați „(” Ieșire: 3 4 2 * 1 5 − Stivă: + / Citim „^” Pune „^” pe stivă Ieșire: 3 4 2 * 1 5 − Stivă: + / ^ Citim "2" Adăugați „2” la șirul de ieșire Ieșire: 3 4 2 * 1 5 − 2 Stivă: + / ^ Sfârșitul expresiei Păstrarea tuturor elementelor din stivă într-un șir Ieșire: 3 4 2 * 1 5 − 2 ^ / +

Optimizarea expresiei

Dacă scrieți un interpret, atunci șirul de ieșire obținut după conversia expresiei originale în notație poloneză inversă poate fi stocat în locul expresiei originale pentru interpretare ulterioară. Notația poloneză inversă permite, de asemenea, computerului să simplifice expresiile.

Un exemplu de algoritm de simplificare a expresiei

Luați în considerare un algoritm care realizează precalcularea constantelor dintr-o expresie. O expresie este dată în OPN. Avem nevoie de o stivă pentru a stoca date mixte (numere și operatori).

Algoritmul este similar cu cel folosit pentru evaluarea expresiilor. Scanăm expresia de la stânga la dreapta.

Atâta timp cât există personaje de citit:

Citim următorul personaj.
Dacă caracterul este un număr, împingeți-l pe stivă.
Dacă caracterul este o variabilă, presupunând că variabila este null , împingeți caracterul în stivă.
Dacă simbolul este un operator:
1) (dacă toate argumentele operatorului de pe stivă au o altă valoare decât null ) scoateți argumentele operatorului din stivă și împingeți rezultatul operației pe stivă;
2) (dacă cel puțin unul dintre argumente este null ) presupunând că rezultatul operației este null , punem simbolul operatorului pe stivă.

După ce întreaga expresie a fost examinată, ceea ce rămâne pe stivă este expresia optimizată (instrucțiunile expresiei sunt în ordine inversă pe stivă).

Un exemplu despre cum funcționează algoritmul

Expresie Notație infixă: exp(-1/2*x) Notație poloneză inversă: -1 2 / x * exp Citire: „-1” Apăsați „-1” pe stivă Stivă: -1 Citire: „2” Apăsați „2” pe stivă Stivă: -1 2 Noi citim: "/" Calculăm coeficientul, punem rezultatul pe stivă Stivă: -0,5 Citire: „x” Apăsați „x” pe stiva cu o valoare nulă Stivă: -0,5x (null) Noi citim: "*" Apăsați „*” pe stiva cu valoarea nulă Stivă: -0,5 x(null) *(null) Citim "exp" Apăsați „exp” pe stiva cu o valoare nulă Stivă: -0,5 x(null) *(null) exp(null) Rezultat optimizare: -0,5 x * exp

Această metodă, evident, nu include toate metodele posibile de optimizare.

Exemple de implementare

Articolul „ Notația poloneză inversă: exemple de implementare ” conține exemple de implementare a notației poloneze inverse în diferite limbaje de programare.

Implementări practice

Ca aplicație practică a acestei tehnici, putem cita organizarea configurațiilor bytecode ale soluțiilor de aplicație ale sistemului 1C:Enterprise . 1C nu oferă confirmare oficială , dar utilizatorii acestui sistem pe forumuri specializate oferă dovezi și algoritmi care permit decompilarea textelor sursă.

Literatură

T. Pratt, M. Zelkowitz. Limbaje de programare: proiectare și implementare = Terrence W. Pratt, Marvin V. Zelkowitz. Limbaje de programare: proiectare și implementare. - editia a 4-a. - Petru, 2002. - 688 p. — (Clasice ale informaticii). - 4000 de exemplare. - ISBN 5-318-00189-0 .

Note

↑ A. V. Aho, R. Seti, D. D. Ulman. Compilatoare: principii, tehnologii și instrumente. M .: „Williams”, 2003. S. 51.

Vezi și

Limbaje de programare care folosesc OPN ca principal:

Mai departe
factor
postscriptum
Limbajul foii de stil BibTeX