RPN: algoritmus, módszerek és példák

RPN egyszer képezte az alapját a számítógép-programozó a világon. Ma már nem annyira ismert. Ezért képregény illusztráció, ábrázol egy „fordított” lengyel kolbász tekercsek kívül, továbbra is félreérthető néhány hozzáértő programozók. Nem nagyon jól magyarázza a vicc, de ebben az esetben ez lesz teljes mértékben indokolt.

behelyez

Minden programozók, és a legtöbb diák tisztában vannak a operátorok használatát. Például, a kifejezés x + összegzése értékeket a változók x és y használt plusz jel. Kevésbé ismert az a tény, hogy ez a kölcsönzött matematika jelölést, az úgynevezett infix jelölés, sőt, egy nagy probléma a gépek. Ez az operátor fogadja a bemeneti két érték van rögzítve a bal és a jobb. A programozási jelöléseket adott esetben jelek műveleteket. Például az x + y felírható függvényében szeres (x, y), ahol a fordító, és végül átalakítja infix jelöléssel. Azonban mindenki tudja, hogy a matematikai túl jó, hogy nem használ aritmetikai kifejezések, amelyek egyfajta belső mininyelv szinte minden programozási nyelv.

formula fordító

Az első igazán sikeres Fortran programozási nyelv annyira főleg azért, mert az aritmetikai kifejezés (azaz képlet ..) Úgy alakítjuk (broadcast) a kódot, innen a név is - Formula fordítás. Ezt megelőzően, meg kellett írni, például hajtogatott formájában funkciók (és szaporodnak (b, c) pont). A COBOL probléma végrehajtási automatikus átváltási képlet tartották nagyon nehéz, mert a programozók kellett írni ilyeneket Add B-Mutliply C.

Mi a baj az infix?

A probléma az, hogy a piaci szereplőknek olyan tulajdonságokat, mint elsőbbséget, és asszociatív. Emiatt, a meghatározása infix funkció nem triviális feladat. Például, a szorzás magasabb részesítendő, mint összeadás vagy a kivonás, ami azt jelenti, hogy a kifejezés 2 + 3 * 4 nem összegével egyenlő a 2 és 3, 4-szerese, mivel ez lenne a teljesítménye az üzemeltetők balról jobbra. Tény, hogy szaporodnak a 3. 4. és adjunk hozzá 2 Ez a példa azt mutatja, hogy a számítás a infix kifejezést gyakran megváltozik a sorrendben szereplők és operandusok. Ezen kívül szükséges használni nadrágtartó, hogy inkább egyértelmű jelöléssel. Például a (2 + 3) * (4 + 5) nem lehet leírni anélkül, hogy a zárójel, mert 2 + 3 * 4 + 5 azt jelenti, hogy meg kell szorozni a 3. 4. és adjunk hozzá 2 és 5.

A sorrend, amelyben szeretnénk számítani a szereplők olyan hosszú emlékezni. Emiatt, a diákok, akik most kezdik tanulni számtani, sokszor a rossz eredmények, akkor is, ha a tényleges tevékenységet helyes végrehajtását. Meg kell tanítani a rendelést tevékenység utasítások fejből. Először is, a keresetet el kell végezni a zárójelben, akkor a szorzás és osztás, és végül az összeadás és kivonás. De van egy másik módja az írás matematikai kifejezések, mint infix jelölés csak az egyik lehetséges „kis nyelvek”, hogy lehet hozzá több.

Prefix és postfix jelölést

Két legismertebb alternatívák rögzíteni az üzemeltető előtt, vagy után operandusok. Ezek az úgynevezett a előtag és a postfix jelöléssel. Logikus Yan Lukasevich feltalálta az elsőt 1920-ban. Élt Lengyelországban, így a rekord az úgynevezett lengyel. Postfix változata, illetve az úgynevezett fordított lengyel jelölés (ARF). Az egyetlen különbség a két módszer között az irányt, ahol olvasni a rekordot (balról jobbra vagy jobbról balra), így elegendő figyelembe venni részletesen csak az egyiket. Az OPN üzemeltető írásbeli után operandusok. Így, az expressziós AB + jelentése egy példát RPN az A + B

Korlátlan számú operandusok

Azonnali előnye jelölést, hogy összefoglalja az n-adikus üzemeltető és infix jelölés valóban csak akkor működik, két operandus, t. E. eredendően alkalmas csak a bináris műveleteket. Például, az ABC @ a fordított lengyel expresszió triadikus jelölést, amely a maximális érték az A, B és C. Ebben az esetben a kezelő hat a bal oldalán a három operandus magát, és megfelel egy függvényhívás @ (A, B, C). Ha megpróbálja írni a @ szimbólumot, mint infix, mint az A @ BC, vagy valami ilyesmi, világossá válik, hogy ez egyszerűen nem működik.

A prioritás által adott megbízás

RPN további előnye, hogy a prioritás a gazdasági szereplők is képviseli a sorrendben a megjelenésüket. Ugyanakkor soha nem kell zárójelek között, bár lehet vonni a karakterek műveletek megkönnyítése konverzió infix jelöléssel. Például, AB + C * - egyértelmű ekvivalens (A + B) * C, így a szorzás nem lehet kiszámítani, amíg a felül végre, amely egy második operandus a szorzás. Azaz, ha a számított AB + C * egy kezelőszemély egy időben, megkapjuk AB + C * -> (AB +) * C -> (A + B) * C.

számítási algoritmus

Az OPN operátor ugyanúgy néz ki, mint egy funkciója, amely paraméterként két értéket írva a bal. Ezen túlmenően, ez egy természetes jelölés használható programozási nyelvek, mint a módja annak kiszámítása megfelel a veremműveletekhez és szükségességét elemzési megszűnik. Például a levezető kifejezés 5 + 6 * 7 fog megjelenni, 5, 6, 7 *, +, és ez lehet számítani egyszerűen szkennelés balról jobbra és írni az értékeket egy verem. Amikor egy közös jele művelet által kiválasztott felső elem 2 a számítógép memóriájában, az üzemeltető használnak, és a kapott eredmény a memóriába. Amikor a végén a számítás eredményét expresszió lesz a verem tetején.

Például:

• S = () 5, 6, 7, *, + 5 helyezni a verem.
• S = (5) 6, 7, *, + 6 helyezni a verem.
• S = (5, 6), 7 *, 7 + helyezze a köteget.
• S = (5, 6, 7), * 2 + válasszon értékeket a verem, használata * és helyezze az eredményt a verem.
• S = (5, 6 * 7) = (5, 42) + 2 kiválasztott értékek a köteget, hogy alkalmazza a + és tegye az eredményt a verem.
• S = (5 + 42) = (47) kiszámítása befejeződött, az eredmény tárolódik a verem tetején.

Ez az algoritmus lehet ellenőrizni RPN többször, de minden egyes alkalommal, hogy működni fog, nem számít, mennyire bonyolult számtani kifejezést.

OPN és halmok szorosan összekapcsolódik. Ez a példa bemutatja, hogyan kell használni a memóriát értékének kiszámításához a fordított lengyel jelölés. Kevésbé nyilvánvaló, hogy tudod használni a verem, konvertáló szabványos infix kifejezést az akut veseelégtelenség.

Példák programozási nyelvek

Pascal RPN rájött, mint ez (mutatja a program része).

Olvasni a számokat és az üzemeltetők a ciklusban nevű eljárást, amely meghatározza, hogy a token számot vagy megjelölés működését. Az első esetben, a tárolt érték a verem, és a második a két felső köteg szám megfelelő cselekvési végzik, és az eredményt tárolja.

toktype: = NUM;

olvasni (s);

ha a C [ '+', '-', '*', '/'] akkor kezdődik

ha eoln majd cn: = '' mást olvasni (CN);

ha cn = „”, akkor

esetén

'+': Toktype: = add; '-': toktype: = sub;

'*': Toktype: = mul; '/': Toktype: = div

vég

máshol kezdődik

ha a = '-', akkor SGN: = -1 mást error: = C <> '+';

A: = cn

vég

végén;

Ha a (nincs hiba), és (toktype = num), akkor getnumber;

ha toktype <> num ezután kezdődik

y = pop; X: = pop;

ha nem, akkor hiba

esetében toktype a

add: z: = x + y; sub: z: = x-y; mul: z: = x * y; div: z: = x / y

vég

push (Z);

C-végrehajtás RPN (lásd a program része):

A (s = strtok (s, w); s; s = strtok (0, w)) {

a = strtod (s, & E);

ha (e> s) push (a);

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

else if (* s == '+') rpnop (a + b);

else if (* s == '-') rpnop (a - b);

else if (* s == '*') rpnop (a * b);

else if (* s == '/') rpnop (a / b);

#undef rpnop

}

hardver eszközök

Azokban a napokban, amikor a számítástechnika nagyon drága volt, úgy gondolták, egy jó ötlet, hogy kényszerítik az embereket, hogy használják túlfeszültség. 1960-es években., Mint most, lehetőség volt, hogy megvásárolja a számológépek, amelyek a munka fordított lengyel jelölés. Hozzáadni a 2. és 3. közülük kell adnia 2, majd 3, majd nyomja meg a „plusz” gombot. Első pillantásra a bemeneti operandusok az üzemeltető úgy tűnt, bonyolult és nehezen megjegyezhető, de egy idő után néhány rabja ennek a gondolkodás, és nem értem, miért a másik ragaszkodik a hülye infix, ami annyira bonyolult, és ezért korlátozott.

Burroughs cég még építettek egy mainframe, ami nem volt más memória, kivéve verem. Az egyetlen dolog, ami miatt a gép - alkalmazta az algoritmusok és módszerek RPN a központi verem. Minden működésének tekintették levezető szolgáltatók, amely vonatkozik a felső n értékeket. Például, a csapat átvette a feladói cím a verem tetején, és így tovább. D. Az architektúra egy ilyen gép volt egyszerű, de nem elég gyors, hogy a versenyt a sokkal gyakoribb architektúrák. Sokan azonban még mindig sajnálom, hogy egy ilyen egyszerű és elegáns megközelítést számítástechnika, ahol minden program kifejeződése volt OPN talált annak folytatását.

Egyszer számológépek RPN népszerűek voltak, és egyesek még mindig nekik előnyben. Ezen túlmenően, hogy kifejlesztett egy halom-orientált nyelv, mint a Forth. Ma már kevéssé használt, de még mindig nosztalgikus származó egykori felhasználók.

Tehát mi a jelentése viccet fordított lengyel kolbászt?

Ha feltételezzük, hogy az üzemeltető a kolbász, a infix jelölés, akkor legyen a henger, mint a hagyományos hot dog. A RPN fekszik két félből készülj közöttük kiszámítása után. Most jön a neheze - mustár. Ő már a kolbász, t. E. már kiszámításra egyoperandusú operátor. Úgy véljük, hogy a mustár is kell kimutatni uncalculated, ezért át kell helyezni a jogot a kolbász ... De lehet, az túlságosan nagy halom ...