RPN: algoritmus, metódy a príklady

RPN kedysi tvorili základ počítačového programátora na svete. Dnes to nie je tak dobre známe. Z tohto dôvodu, komediálny ilustrácie, zobrazujúci "Reverse" poľskej klobásy rožky vonku, ale napriek tomu môže byť zle pochopené niektorými znalými programátorov. Nie príliš dobre vysvetliť vtip, ale v tomto prípade to bude úplne oprávnené.

upevniť

Všetci programátori a väčšina študentov sú oboznámení s použitím operátorov. Napríklad výraz x + súčtu hodnoty premenných x a y použité znamienko plus. Menej známy je fakt, že toto je prevzaté z matematiky notácie, nazvaný infixi notácie, v skutočnosti je veľký problém pre stroje. Tento operátor prijíma ako vstup obe hodnoty sú zaznamenané na ľavej a pravej strane. Pri programovaní notácie použité voliteľne s príznakmi operácií. Napríklad, x + y môže byť napísané ako funkcia záhybu (x, y), v ktorom prekladač a nakoniec sa premení infixovou notácie. Avšak, každý vie, že matematika je príliš dobré nepoužívať aritmetických výrazov, ktoré tvoria akýsi vnútorný mini-jazyka v takmer každej programovací jazyk.

vzorec tlmočník

Prvá naozaj úspešný Fortran programovací jazyk stal sa tak do značnej miery preto, že aritmetický výraz (tj vzorec ..) To prevedený (vysielanie) v kóde, preto meno na to - Formula preklade. Predtým museli písať, napríklad, poskladaného do tvaru funkcií (a násobiť (b, c)). V COBOL problém vykonávania automatického prevodu vzorec bol považovaný za veľmi ťažké, pretože programátori museli písať veci, ako je Pridať A do bodu B Mutliply C.

Čo je s infixi zle?

Problém je v tom, že prevádzkovatelia majú také vlastnosti ako Prednosť a asociativita. Z tohto dôvodu je definícia funkcie infixi stáva non-triviálne úloha. Napríklad, násobenie má vyššiu prioritu ako sčítanie alebo odčítanie, čo znamená, že výraz 2 + 3 * 4 nie je rovná súčtu 2 a 3, vynásobený 4, ako by to bolo pri výkone prevádzkovateľov zľava doprava. V skutočnosti, násobiť 3 o 4 a pridať 2. Tento príklad ukazuje, že výpočet výrazu infixi často vyžaduje zmenu poradia operátorov a operandov. Okrem toho, že je nevyhnutné použiť zátvorky vyzerať jasnejšie notácie. Napríklad, (2 + 3) * (4 + 5) nemôže byť zapísaný bez zátvoriek, pretože 2 + 3 * 4 + 5 znamená, že treba vynásobiť 3 o 4 a pridajte 2 a 5.

Poradie, v ktorom chcete vypočítať prevádzkovateľom vyžaduje dlho pamätať. Z tohto dôvodu študenti, ktorí začínajú učiť aritmetiku, často získať zlé výsledky, a to aj v prípade, že skutočné operácie sú vykonávané správne. Je nutné naučiť poradí príkazov akčných naspamäť. Po prvé, akcie musia byť vykonávané v zátvorkách, potom sa násobenie a delenie, a konečne sčítanie a odčítanie. Ale je tu ďalší spôsob, ako písať matematické výrazy ako prípona notácie je len jedným z možných "malých jazykov", ktoré môžu byť pridané do viacerých.

Prefix a postfix notácie

Dvaja z najznámejších alternatív je zaznamenať prevádzkovateľ pred alebo po jeho operandy. Oni sú známi ako predponou a postfix notácie. Logik Yan Lukasevich vynašiel prvý v roku 1920. Žil v Poľsku, takže záznam sa nazýva Polish. Postfix verzie, respektíve s názvom Reverse Polish Notation (ARF). Jediný rozdiel medzi týmito dvoma metódami je smer, v ktorom čítať záznam (zľava doprava alebo sprava doľava), takže stačí uvažovať podrobne iba jeden z nich. Operátor OPN je písaný po jeho operandy. To znamená, že výraz AB + predstavuje príklad RPN pre A + B.

Neobmedzený počet operandov

Bezprostredná výhoda notácie je, že zhŕňa n ADIC operátora a prípona zápis je v skutočnosti iba pracuje s dvoma operandy, t. E. sú prirodzene vhodný iba pre binárne operácie. Napríklad ABC @ je reverznej poľský výraz pomocou triadic značku, ktoré je maximálna hodnota z A, B a C. V tomto prípade operátor pôsobí na ľavej strane tri operandu samotnej a zodpovedá volanie funkcie @ (A, B, C). Ak sa pokúsite zapísať symbol @ ako infixi, napríklad @ pred naším letopočtom, alebo niečo také, je zrejmé, že to jednoducho nefunguje.

Priorita daná poradí

RPN má ďalšiu výhodu v tom, že prioritou operátorov môžu byť reprezentované v poradí podľa ich vzhľadu. Zároveň sa nikdy potrebovať rovnátka, aj keď môžu byť zahrnuté ako znaky operácie s cieľom uľahčiť prechod z infixová notácie. Napríklad, AB + C * - jednoznačný ekvivalent (A + B) * C, takže násobenie nedá vypočítať až pridávanie vykonáva, čo dáva druhý operand pre násobenie. To znamená, že v prípade, že vypočítaná AB + C * jeden pracovník v dobe, dostaneme AB + C * -> (AB +) * C -> (A + B) * C.

algoritmus výpočtu

Prevádzkovateľ OPN vyzerá rovnako ako funkcia, ktorá berie ako argumenty dve hodnoty napísané na jej ľavej strane. Okrem toho sa jedná o prírodné notácie pre použitie v programovacích jazykoch, ako spôsob jeho výpočtu zodpovedá zásobníku operácie a nutnosť vykonávania syntaktické analýzy sú eliminované. Napríklad zvodič vo výraze 5 + 6 * 7 sa objaví ako 5, 6, 7 *, +, a to môže byť vypočítaná jednoducho skenovaním zľava doprava a zapíšte hodnoty v stohu. Kedykoľvek je spoločným znakom prevádzky zvolí horný prvok 2 z pamäte počítača, operátor sa používa a výsledok sa vrátil do pamäti. Keď sa konečný výsledok expresie výpočtu bude v hornej časti zásobníka.

napríklad:

• S = () 5, 6, 7, *, + 5 umiestnený v zásobníku.
• S = (5), 6, 7, *, + 6 umiestnený v zásobníku.
• S = (5, 6), 7 *, 7 + umiestnite stoh.
• S = (5, 6, 7), * 2 + vybrať hodnoty zo stohu, použitie * a výsledok v stohu.
• S = (5, 6 * 7) = (5, 42) a 2 hodnoty vybrané zo stohu, aplikovať + a dať výsledok v stohu.
• S = (5 + 42) = (47), výpočet je dokončený, výsledok je uložený v hornej časti zásobníka.

Tento algoritmus možno skontrolovať RPN opakovane, ale zakaždým, keď to bude fungovať, bez ohľadu na to, ako zložité aritmetický výraz.

OPN a komíny sú úzko späté. Tento príklad ukazuje, ako používať pamäť pre výpočet hodnoty reverznej poľskej notácie. Menej jasné je, že môžete použiť balík, prestavovať štandardné infixovou výraz v akútnym zlyhaním obličiek.

Príklady programovacích jazykov

Pascal RPN uvedomil takhle (ukazuje časť programu).

Čítať čísla a operátormi v cykle s názvom postup, ktorý určuje, či token číslo alebo znamenie prevádzky. V prvom prípade sa hodnota uložená v zásobníku, a druhý z oboch horných čísla zásobníka príslušná akcia sa vykonáva, a výsledok je uložený.

toktype: = číslo;

čítanie (s);

ak c v [ '+', '-', '*', '/'] potom začne

ak eoln potom CN: = '' else čítať (KN);

ak cn =, 'potom

prípad

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

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

koniec

else begin

v prípade, že = '-', potom SGN: = -1 iný chyba: = c <> '+';

s: = CN

koniec

skončiť;

if (nie je chyba) a (toktype = číslo), potom getnumber;

ak toktype <> num potom začne

y = pop; x: = pop;

pokiaľ nie je chyba potom

Prípad toktype of

ni: z: = x + y; Sub: z: = x-y; mul: z: = x * y; div: z: = x / y

koniec

tlak (z);

C-realizácia RPN (zobrazené súčasťou programu):

pre (y = strtok (s, w), S, S = strtok (0, w)) {

A = strtod (s, e);

if (e> y) tlak (a);

# Define rpnop (x) printf ( "% c:", * s), b = pop (), a = pop (), tlačidlo (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

}

hardvérové realizácie

V tých dňoch, keď výpočtová technika bola veľmi drahá, to bola myšlienka ako dobrý nápad prinútiť ľudí, aby používali zvodičov prepätia. V roku 1960-tych rokoch., Rovnako ako dnes, bolo možné kúpiť kalkulačky, ktoré pracujú v opačnom poľskej notáciu. Ak chcete pridať 2 a 3 z nich je potrebné zadať 2, potom 3, a stlačte tlačidlo "plus". Na prvý pohľad vstupný operandmi na prevádzkovateľa zdalo zložité a ťažko zapamätateľné, ale po chvíli niektoré z nich sú závislé na tento spôsob myslenia a nemohol pochopiť, prečo iní trvajú na stupídny infixi, ktorý je tak zložitý a tak je obmedzený.

spoločnosť Burroughs dokonca postavil sálový počítač, ktorý mal žiadnu inú pamäť, okrem zásobníka. Jediná vec, ktorá robí stroj - použila algoritmy a metódy RPN do centrálneho zásobníka. Všetky jej operácie boli považované za zvodiča operátormi, ktoré sa vzťahujú k hornej hodnoty n. Napríklad tím vzal spiatočnej adresy z vrcholu zásobníka, a tak ďalej. D. Architektúra taký stroj bol jednoduchý, ale nie dosť rýchlo, aby súťažiť s viacerými rozšírené architektúry. Mnohí však stále mrzí, že taký jednoduchý a elegantný prístup k práci na počítači, kde každý program bol výrazom OPN, našiel jeho pokračovanie.

Jednorazové kalkulačky s RPN boli populárne, a niektorí ľudia stále dávajú im prednosť. Okrem toho vyvinula stoh orientované jazyky, ako je Forth. Dnes je málo používaný, ale stále nostalgicky z jeho bývalých používateľov.

Takže aký je význam vtipy o Reverse Polish klobásu?

Ak budeme predpokladať, že prevádzkovateľ salámy sa infixi notácie, by malo byť v rámci role, ako v bežnom párok v rožku. RPN sa nachádza priamo na dve polovice pripravte nimi po výpočte. Teraz prichádza to najťažšie - horčice. Je už na údeniny, t. E. Už počítané ako unárne. Predpokladá sa, že horčica by mali byť tiež uvedené ako nepredvídateľných a preto by mal byť presunutý do pravej časti salámy ... Ale je to možné, by to vyžadovalo príliš veľkú hromadu ...