RPN: algorithm, metodat dhe shembuj

RPN sapo formuar bazën e një programues kompjuterik në botë. Sot ajo nuk është e njohur aq mirë. Prandaj, ilustrim komik, që përshkruan një "kundërt" rrotullon suxhuk polak jashtë, mund ende të jetë keqkuptuar nga disa programuesit njohuri. Jo shumë mirë shpjeguar shaka, por në këtë rast ajo do të jetë plotësisht i justifikuar.

infiks

Të gjithë programuesit, dhe shumica e studentëve janë të njohur me përdorimin e operatorëve. Për shembull, vlera shprehja x + përmbledhje për variablat x dhe y të përdorura shenjë plus. më pak i njohur është fakti se kjo është huazuar nga matematika simbol, i quajtur infiks simbol, në fakt, është një problem i madh për makinat. Ky operator merr si input dy vlera janë të regjistruar në të majtë dhe të djathtë. Në programimin simbol përdoret në mënyrë opsionale me operacionet shenja. Për shembull, x + y mund të shkruhet si një funksion i dele (x, y), në të cilën përpiluesit dhe përfundimisht konverton Infiks simbol. Megjithatë, të gjithë e dinë matematikë është shumë e mirë të mos përdorin shprehje aritmetikore, të cilat formojnë një lloj mini-gjuhës së brendshme në pothuajse çdo gjuhë programimi.

formula translator

para gjuha me të vërtetë i suksesshëm programimit Fortran është bërë kështu kryesisht për shkak shprehja aritmetike (p.sh. formula ..) Është konvertuar (transmetim) në kodin, kështu emrin e saj - Formula përkthim. Para kësaj, ata kishin për të shkruar, për shembull, palosur në formën e funksioneve (dhe të shumohen (b, c)). Në problemin COBOL e zbatimit të formulës automatike konvertimit është konsideruar si shumë e vështirë për shkak se programuesit kishte për të shkruar gjëra të tilla si Shtoni A në B Mutliply nga C.

Çfarë është e gabuar me Infiks?

Problemi është, se operatorët kanë prona të tilla si përparësi dhe associativity. Për shkak të kësaj, përkufizimi i funksionit Infiks bëhet detyrë jo të parëndësishëm. Për shembull, shumëzimit ka përparësi më të lartë se mbledhjen ose zbritjen, që do të thotë se shprehja 2 + 3 * 4 nuk është i barabartë me shumën e 2 dhe 3, shumëzuar me 4, pasi ajo do të jetë në kryerjen e operatorëve nga e majta në të djathtë. Në fakt, shumohen 3 nga 4 dhe shtoni 2. Ky shembull ilustron se llogaritja e shprehjes Infiks shpesh kërkon një ndryshim në rendin e operatorëve dhe operandëve. Përveç kësaj, ajo është e nevojshme për të përdorur formatimin e teksteve për të parë simbol më të qartë. Për shembull, (2 + 3) * (4 + 5) nuk mund të shkruhet pa kllapa, sepse 2 + 3 * 4 + 5 do të thotë se ju duhet të shumohen 3 me 4 dhe të shtoni 2 dhe 5.

Rendi në të cilën ju dëshironi për të llogaritur operatorët kërkon një kohë të gjatë të kujtuar. Për shkak të kësaj, studentët që të fillojnë të mësojnë aritmetikën, shpesh të marrë rezultatet më të gabuar, edhe nëse operacionet aktuale janë kryer në mënyrë korrekte. Është e nevojshme për të mësuar rendin e deklaratave të veprimit nga zemra. Së pari, veprimi duhet të kryhet në kllapa, pastaj shumëzimit dhe pjesëtimit, dhe në fund mbledhjes dhe të zbritjes. Por ka një mënyrë tjetër e të shkruarit shprehjeve matematikore si Infiks simbol është vetëm një nga të mundshme "gjuhëve të vogla", që mund të shtohet për më shumë.

Prefix dhe postfix simbol

Dy nga alternativat më të njohura është për të regjistruar operatorin para ose pas operandëve saj. Ata janë të njohur si prefiksin dhe postfix simbol. Logician Yan Lukasevich shpiku një të parë në vitin 1920. Ai jetoi në Poloni, kështu që të dhënat quhet polake. Postfix version, respektivisht, i quajtur Reverse Anglisht simbol (ARF). I vetmi ndryshim midis këtyre dy metodave është drejtimi në të cilin për të lexuar të dhënat (nga e majta në të djathtë apo të djathta në të majtë), kështu që mjafton të marrin në konsideratë në detaje vetëm një prej tyre. Operatori OPN është shkruar pas operandëve saj. Kështu, shprehja AB + përfaqëson një shembull RPN per A + B

Numër të pakufizuar të operandëve

Avantazhi i menjëhershëm i simbol është se ajo përmbledh operatorin n-adic dhe Infiks simbol është me të vërtetë vetëm punon me dy operandëve, t. E. janë në thelb të përshtatshme vetëm për operacione binare. Për shembull, ABC @ është shprehja kundërta polake duke përdorur shenjën triadic i cili është vlera maksimale e A, B dhe C. Në këtë rast operatori vepron në të majtë të tre operandit vetë dhe korrespondon me një funksion thirrje @ (A, B, C). Nëse ju provoni të shkruani simbol @ si infiks, të tilla si A @ pes ose diçka të tillë, bëhet e qartë se ajo thjesht nuk funksionon.

Prioriteti i dhënë nga ana e rendit

RPN ka një avantazh në se prioritet i operatorëve mund të përfaqësohet me urdhër të paraqitjes së tyre. Në të njëjtën kohë nuk duhet formatimin e teksteve, edhe pse ata mund të përfshihen si operacionet karaktere për të lehtësuar konvertimin nga Infiks simbol. Për shembull, AB + C * - ekuivalent i qartë (A + B) * C, kështu që shumëzimit nuk mund të llogaritet deri shtimin e kryer, e cila jep një operand dytë për shumëzim. Kjo është, në qoftë se llogaritur AB + C * nga një operator në një kohë, ne të merrni AB + C * -> (AB +) * C -> (A + B) * C.

Llogaritja algorithm

Operatori OPN duket e njëjtë si një funksion që merr si argumente dy vlera të shkruar në të majtë të saj. Përveç kësaj, ajo është një simbol natyral për përdorim në gjuhë programimi, si mënyrën e llogaritjes së tij korrespondon me operacionet rafte dhe nevoja për analizë gramatikore është eliminuar. Për shembull, xixëve në shprehjen 5 + 6 * 7 do të duket si 5, 6, 7 * +, dhe kjo mund të llogaritet thjesht nga skanimi nga e majta në të djathtë dhe të shkruajnë vlerat në një pirg. Kurdo që një shenjë e zakonshme e operacionit, të zgjedhur nga elementi sipërme 2 të memories kompjuterike, operatori është përdorur dhe rezultati u kthye në kujtesë. Kur rezultati përfundimtar i llogaritjes së shprehjes do të jetë në krye të rafte.

Për shembull:

• S = () 5, 6, 7, *, + 5 vendosen në pirg.
• S = (5) 6, 7, *, + 6 vendosen në pirg.
• S = (5, 6), 7 *, 7 + zhvillohet grumbull.
• S = (5, 6, 7), * 2 + zgjedhur vlerat nga pirg, përdorimi * dhe vendin e rezultatit ne grumbullin.
• S = (5, 6 * 7) = (5, 42) + 2 vlerat e zgjedhura nga pirg, për të zbatuar + dhe vihet rezultatin ne grumbullin.
• S = (5 + 42) = (47) llogaritja është e përfunduar, rezultati është ruajtur në krye të rafte.

Kjo algorithm mund të kontrollohet në mënyrë të përsëritur RPN, por çdo herë ajo do të punojë, pa marrë parasysh se sa kompleks shprehje aritmetike.

OPN dhe oxhaqet janë të lidhura ngushtë. Ky shembull tregon se si të përdorin kujtesën për të llogaritur vlerën e simbol kundërt polak. Më pak e qartë është se ju mund të përdorni rafte, konvertimin shprehje standarde infiks në dështim akute renale.

Shembuj të gjuhëve të programimit

Pascal RPN realizuar si kjo (tregon një pjesë të programit).

Për të lexuar numrat dhe operatorët në ciklin e quajtur procedurën, e cila përcakton nëse numri apo shenjë simbolike operacion. Në rastin e parë, vlera e ruajtur në rafte, dhe e dyta e dy numrave sipërme rafte veprim përkatës është kryer dhe rezultati është ruajtur.

toktype: = num;

lexuar (s);

nëse c në [ '+' - '*' / '] pastaj fillojnë

nëse eoln pastaj CN: = '' tjetër lexuar (CN);

nëse CN = '', atëherë

rasti i një

'+': Toktype: = shtesë; '-': toktype: = sub;

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

fund

tjetër fillojnë

nëse a = '-' atëherë sgn: = -1 tjetër gabim: = c <> '+';

me: = CN

fund

fund;

në qoftë se (jo gabim) dhe (toktype = num) atëherë getnumber;

nëse toktype <> num pastaj të fillojë

y = pop; x: = pop;

nëse jo, atëherë gabim

Rasti toktype e

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

fund

shtytje (z);

C-zbatimi RPN (pjesa e dukshme e programit):

për (a = strtok (s, w); S; s = strtok (0, w)) {

a = strtod (s, dhe e);

në qoftë se (e> s) shtytje (a);

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

përndryshe nëse (* s == '+') rpnop (a + b);

përndryshe nëse (* s == '-') rpnop (a - b);

përndryshe nëse rpnop (* s == '*') (a * b);

përndryshe nëse (* s == '/') rpnop (a / b);

rpnop #undef

}

Implementimi hardware

Në ato ditë, kur teknologjia kompjuterike ishte shumë e shtrenjtë, u mendua një ide e mirë për të detyruar njerëzit që të përdorin arresters rritje. Në 1960-ta., Si tani, ishte e mundur për të blerë calculators, të cilat punojnë në simbol kundërt polak. Për të shtuar 2 dhe 3 prej tyre duhet të hyjë në 2, pastaj 3, dhe shtypni "plus" button. Në shikim të parë, operandët dhëna për operatorin dukej e komplikuar dhe e vështirë për të kujtuar, por pas një kohë disa janë të varur në këtë mënyrë të të menduarit dhe nuk mund të kuptoj pse të tjerët insistojnë në Infiks trashë, e cila është aq e komplikuar dhe kështu është i kufizuar.

Kompania Burroughs edhe ndërtuar një mainframe, i cili nuk kishte asnjë kujtim tjetër, me përjashtim të rafte. E vetmja gjë që e bën makinën - aplikuar Algoritmet dhe metodat e RPN me rafte qendrore. Të gjitha operacionet e saj janë konsideruar si operatorët arresters, e cila vlen për vlerat e sipërme n. Për shembull, ekipi mori Return Adresa nga maja e rafte, dhe kështu me radhë. D. Arkitektura e një makinë të tillë ishte e thjeshtë, por jo të shpejtë të mjaftueshme për të konkurruar me arkitektura më të zakonshme. Shumë, megjithatë, ende keqardhje fakti se një qasje e tillë e thjeshtë dhe elegante për informatikë ku çdo program ishte një shprehje e OPN, gjetur vazhdimin e saj.

Një calculators kohë me RPN ishin të njohura, dhe disa njerëz ende për t'u dhënë atyre përparësi. Përveç kësaj, ata zhvilluan një pirg të orientuar gjuhë, të tilla si me radhë. Sot ajo është pak e përdorur, por ende nostalgji nga ish përdoruesit e tij.

Pra, çfarë është shaka Kuptimi në lidhje me sallam Reverse polak?

Në qoftë se ne supozojmë se operatori i sallamit, i infiks simbol, ajo duhet të jetë në kuadër të rrokulliset si në qen konvencionale të nxehtë. RPN është e vendosur të drejtë në dy gjysmat marrë ndermjet tyre të gatshme pas llogaritjes. Tani vjen pjesa e vështirë - mustardë. Ajo është tashmë në sallam, t. E. Tashmë llogaritet si një operator unary. Besohet se mustardë gjithashtu duhet të tregohet si uncalculated dhe për këtë arsye duhet të zhvendoset në të djathtë e sallamit ... Por është e mundur, kjo do të kërkonte pirg shumë të madhe të ...