Înregistrarea poloneză inversă: algoritm, metode și exemple

Înregistrarea poloneză inversă a fost odată baza lumii programatorului de calculator. Astăzi nu este atât de bine cunoscut. Prin urmare, ilustrația de benzi desenate care ilustrează cârnații polonezi "inversi" în afara bunului poate fi în continuare înțeles de unii programatori informați. Nu este foarte bine să explicăm glumă, dar în acest caz va fi pe deplin justificată.

Introdus intrare

Toți programatorii și majoritatea studenților sunt familiarizați cu utilizarea operatorilor. De exemplu, în expresia x + y, semnul adițional este utilizat pentru a însuma valorile variabilelor x și y. Mai puțin cunoscut este faptul că această împrumut de la denumirea matematică, numită notație infix, este de fapt o problemă mare pentru mașini. Un astfel de operator ia în considerare două valori scrise în partea stângă și dreapta a acestuia. În programare, notația cu semne de operare este opțională. De exemplu, x + y poate fi scris ca o funcție de adăugat (x, y), la care compilatorul convertește în cele din urmă notația infix. Cu toate acestea, toată lumea știe prea bine matematica să nu folosească expresii aritmetice, care formează un fel de mini-limbă internă în aproape toate limbile de programare.

Traducători de formule

Prima într-adevăr cu succes limbajul de programare Fortran a devenit atât de mare măsură, deoarece expresia aritmetică (de exemplu, formula ..) convertit (difuzare) în codul, de aici numele de ea - FORMULA de traducere. Înainte, trebuiau să fie scrise, de exemplu, sub forma unor funcții de adăugat (a, multiplica (b, c)). În Kobol, problema implementării conversiei automate a formularelor a fost considerată foarte dificilă, deoarece programatorii au trebuit să scrie lucruri ca Add A To B Mutliply de C.

Ce sa întâmplat cu infix?

Problema este că operatorii au proprietăți precum prioritatea și asociativitatea. Din această cauză, definiția funcției infix devine o sarcină netrivială. De exemplu, multiplicarea are prioritate mai mare decât adunare sau scădere, ceea ce înseamnă că expresia 2 + 3 * 4 nu este egal cu suma de 2 și 3, înmulțit cu 4, așa cum ar fi în performanța operatorilor de la stânga la dreapta. De fapt, multiplicați 3 cu 4 și adăugați 2. Acest exemplu ilustrează faptul că evaluarea unei expresii infix necesită adesea o schimbare în ordinea operatorilor și a operanzilor lor. În plus, trebuie să folosim paranteze pentru a face notarea să pară mai clară. De exemplu, (2 + 3) * (4 + 5) nu poate fi scris fără paranteze, deoarece 2 + 3 * 4 + 5 înseamnă că trebuie să înmulțiți 3 cu 4 și să adăugați 2 și 5.

Ordinea în care operatorii trebuie calculați necesită o memorare îndelungată. Din acest motiv, elevii care încep să învețe aritmetică primesc adesea rezultate greșite, chiar dacă de fapt operațiile sunt efectuate corect. Este necesar să învățăm din inimă ordinea acțiunilor operatorilor. Mai întâi, trebuie întreprinse acțiunile în paranteze, apoi multiplicarea și împărțirea și, în final, adăugarea și scăderea. Există însă și alte modalități de scriere a expresiilor matematice, deoarece notația infix este doar una dintre "limbile mici" care pot fi adăugate la cele mai mari.

Prefix și notație postfix

Cele două cele mai populare alternative sunt înregistrarea unui operator înainte sau după operanzii săi. Ele sunt cunoscute ca notații prefix și postfix. Logicianul Jan Lukasevich a inventat primul dintre ei în anii 1920. El a locuit în Polonia, astfel încât înregistrarea este numită poloneză. Versiunea Postfix, respectiv, a fost numită notație polară inversă (ARF). Singura diferență dintre cele două metode este direcția în care se citește înregistrarea (de la stânga la dreapta sau de la dreapta la stânga), deci este suficient să luați în considerare doar unul dintre ele în detaliu. În arrester, operatorul este scris după operanzi. Astfel, expresia AB + este un exemplu de înregistrare poloneză inversă pentru A + B.

Numar nelimitat de operandi

Avantajul imediat al notație este că acesta rezumă operatorul n-adice și notație infixat este într-adevăr funcționează numai cu doi operanzi, t. E. sunt în mod inerent adecvat numai pentru operațiunile binare. De exemplu, ABC @ este inversă expresia poloneză folosind marca triadic care este valoarea maximă a A, B și C. În acest caz, operatorul acționează din partea stângă a trei operandului în sine și corespunde unui apel funcții @ (A, B, C). Dacă încercați să scrie simbolul @ ca un infix, de exemplu A @ BC sau ceva de genul acesta, atunci devine clar că acest lucru nu funcționează.

Prioritatea este dată de ordin

Intrarea inversă în Polonia are un alt avantaj prin faptul că prioritatea operatorilor poate fi reprezentată de ordinea apariției lor. În acest caz, parantezele nu vor fi niciodată necesare, deși pot fi incluse ca simboluri de tranzacție pentru a facilita conversia printr-o notație infix. De exemplu, AB + C * este un echivalent unic (A + B) * C, deoarece multiplicarea nu poate fi calculată până când se face adăugarea, ceea ce dă celui de-al doilea operand pentru operația de multiplicare. Asta este, daca AB + C * este calculat pentru un operator la un moment dat, atunci primim A B + C * -> (A B +) * C -> (A + B) * C.

Algoritmul de calcul

În OPN, operatorul arată ca o funcție care ia ca argumente două valori scrise în partea stângă a acestuia. În plus, aceasta este o notație naturală pentru utilizarea în limbile de programare, deoarece cursul calculelor sale corespunde operațiilor de stivă și nu este necesară parsarea. De exemplu, în ARS, expresia 5 + 6 * 7 va arăta ca 5, 6, 7 *, + și poate fi calculată pur și simplu prin scanarea de la stânga la dreapta și scrierea valorilor în stivă. De fiecare dată când se întâlnește semnul de operare, se selectează primele 2 elemente din memoria aparatului, operatorul este aplicat și rezultatul este returnat în memorie. După terminarea expresiei, rezultatul calculului va fi în partea de sus a stivei.

De exemplu:

• S = () 5, 6, 7, *, + pune 5 pe teancul.
• S = (5) 6, 7, *, + pune 6 pe stivă.
• S = (5, 6) 7, *, + pune 7 pe stivă.
• S = (5, 6, 7) *, + selectați 2 valori din stiva, aplicați * și puneți rezultatul pe teancul.
• S = (5, 6 * 7) = (5, 42) + selectați 2 valori din stiva, aplicați + și puneți rezultatul pe stivă.
• S = (5 + 42) = (47) calculul este complet, rezultatul fiind în partea de sus a stivei.

Acest algoritm al înregistrării inverse poloneze poate fi verificat de mai multe ori, dar de fiecare dată va funcționa, indiferent cât de complexă este expresia aritmetică.

Arresterul și stivele sunt strâns legate. Exemplul de mai sus demonstrează modul în care memoria poate fi utilizată pentru a calcula valoarea în notația inversă poloneză. Este mai puțin evident că puteți folosi stiva prin convertirea expresiilor infix standard în arrester.

Exemple în limbile de programare

În limba Pascal, înregistrarea poloneză inversă este implementată aproximativ în felul acesta (o parte a programului este dată).

Pentru a citi numerele și operatorii într-o buclă, se numește o procedură care determină dacă tokenul este un semn sau o operație. În primul caz, valoarea este înscrisă în stivă, în timp ce în al doilea caz, acțiunea corespunzătoare este efectuată pe primele două numere ale stivei și rezultatul este salvat.

toktype: = num;

citiți (c);

dacă în [`+`, `-`, `*`, `/`] începe apoi

dacă eoln apoi cn: = `` altceva citit (cn);

dacă cn = `atunci

caz cu

`+`: toktype: = add- `-`: toktype: = sub;

`*`: toktype: = mul- `/`: toktype: = div

capăt

altceva începe

dacă c = `-` atunci sgn: = -1 altă eroare: = s <> "+";

cu: = cn

capăt

se încheie;

dacă (nu eroare) și (toktype = num) atunci getnumber;

dacă toktype <> num. atunci începe

y: = roorx: = rop;

dacă nu eroare atunci

cazul toktype din

adăugați: z: = x + y-sub: z: = x-y-mul: z: = x * y-div:

capăt

împinge (z);

Implementarea C a înregistrării inverse poloneze (o parte a programului este dată):

pentru (s = strtok (s, w) -s-s = strtok (0, w)) {

a = strtod (s, e);

dacă (e> s) împingeți (a);

#define rpnop (x) printf ("% s:", * s), b = pop (), a = pop ()

altfel dacă (* s == `+`) rpnop (a + b);

altfel dacă (* s == `-`) rpnop (a - b);

altfel dacă (* s == `*`) rpnop (a * b);

altfel dacă (* s == `/`) rpnop (a / b);

#undef rpnop

}

Implementări hardware

În acele zile, când tehnologia informatică era foarte scumpă, a fost o idee bună să forțezi oamenii să folosească OPN. În anii 1960, ca și astăzi, a fost posibil să cumpărați calculatoare care să funcționeze în înregistrare poloneză inversă. Pentru a adăuga 2 și 3 în ele, introduceți 2, apoi 3 și apăsați butonul plus. La prima vedere, operanzii de intrare operatorului părea complicat și dificil de reținut, dar după un timp unele sunt dependent de acest mod de a gândi și a nu putea înțelege de ce ceilalți insista pe infixat prost, care este atât de complicat și așa este limitată.

Burroughs a construit chiar un mainframe care nu avea nicio altă memorie RAM, cu excepția stivei. Singurul lucru pe care mașina la făcut a fost să aplice algoritmi și metode pentru a inversa înregistrarea poloneză în teancul central. Toate operațiunile sale au fost considerate operatori OPN, ale căror acțiuni s-au extins la n valori superioare. De exemplu, comanda Return a preluat o adresă din partea de sus a stivei etc. Arhitectura acestei mașini a fost simplă, dar nu suficient de rapidă pentru a concura cu arhitecturi mai generale. Cu toate acestea, mulți regretă faptul că o astfel de abordare simplă și elegantă a calculului, în care fiecare program era o expresie a OPN, nu și-a găsit continuitatea.

La un moment dat, calculatoarele cu înregistrare poloneză inversă erau populare, iar altele le preferă. În plus, s-au dezvoltat limbi orientate spre stack, cum ar fi Forth. Astăzi este puțin folosită, dar cauzează nostalgie din partea foștilor utilizatori.

Deci, care este scopul glumelor despre cârnații polonezi de întoarcere?

Dacă luați în considerare operatorul de cârnați, apoi în notația infix, ar trebui să fie în interiorul ruloului, ca și în cazul unui hot dog normal. În înregistrarea poloneză inversă, se află în partea dreaptă a celor două jumătăți, gata să se lovească între ele după calcul. Acum începe partea cea mai dificilă - muștar. Acesta este deja pe cârnați, adică a fost deja calculat ca un operator unar. Există o opinie că muștarul ar trebui să fie arătat ca nedefinit și, prin urmare, ar trebui să fie mișcat în dreapta cârnaților ... Dar poate că va lua prea multă stivă ...