RPN: algoritmus, metody a příklady

RPN kdysi tvořily základ počítačového programátora na světě. Dnes to není tak dobře známé. Z tohoto důvodu, komediální ilustrace, zobrazující „Reverse“ polské klobásy rohlíky venku, ale přesto může být špatně pochopeno některými znalými programátory. Nepříliš dobře vysvětlit vtip, ale v tomto případě to bude zcela oprávněné.

upevnit

Všichni programátoři a většina studentů jsou obeznámeni s použitím operátorů. Například výraz x + sumační hodnoty proměnných x a y použité znaménko plus. Méně známý je fakt, že toto je převzato z matematiky notace, nazvaný infix notace, ve skutečnosti je velký problém pro stroje. Tento operátor přijímá jako vstup obě hodnoty jsou zaznamenány na levé a pravé straně. Při programování notace použity volitelně s příznaky operací. Například, x + y může být psáno jako funkce záhybu (x, y), v němž překladač a nakonec se přemění infixovou notace. Nicméně, každý ví, že matematika je příliš dobré nepoužívat aritmetických výrazů, které tvoří jakýsi vnitřní mini-jazyka v téměř každé programovací jazyk.

vzorec tlumočník

První opravdu úspěšný Fortran programovací jazyk stal se tak do značné míry proto, že aritmetický výraz (tj vzorec ..) To převeden (vysílání) v kódu, proto jméno na to - Formule překladu. Předtím museli psát, například, poskládaného do tvaru funkcí (a násobit (b, c)). V COBOL problém provádění automatického převodu vzorec byl považován za velmi obtížné, protože programátoři museli psát věci, jako je Přidat A do bodu B Mutliply C.

Co je s infix špatně?

Problém je v tom, že provozovatelé mají takové vlastnosti jako Přednost a asociativita. Z tohoto důvodu je definice funkce Infix stává non-triviální úkol. Například, násobení má vyšší prioritu než sčítání nebo odčítání, což znamená, že výraz 2 + 3 * 4 není rovna součtu 2 a 3, vynásobený 4, jak by to bylo při výkonu provozovatelů zleva doprava. Ve skutečnosti, násobit 3 o 4 a přidat 2. Tento příklad ukazuje, že výpočet výrazu Infix často vyžaduje změnu pořadí operátorů a operandů. Kromě toho, že je nezbytné použít závorky vypadat jasnější notace. Například, (2 + 3) * (4 + 5) nemůže být zapsán bez závorek, protože 2 + 3 * 4 + 5 znamená, že je třeba vynásobit 3 o 4 a přidejte 2 a 5.

Pořadí, ve kterém chcete vypočítat provozovatelům vyžaduje dlouho pamatovat. Z tohoto důvodu studenti, kteří začínají učit aritmetiku, často získat špatné výsledky, a to i v případě, že skutečné operace jsou prováděny správně. Je nutné naučit pořadí příkazů akčních zpaměti. Za prvé, akce musí být prováděny v závorkách, pak se násobení a dělení, a konečně sčítání a odčítání. Ale je tu další způsob, jak psát matematické výrazy jako přípona notace je pouze jedním z možných „malých jazyků“, které mohou být přidány do více.

Prefix a postfix notace

Dva z nejznámějších alternativ je zaznamenat provozovatel před nebo po jeho operandy. Oni jsou známí jako předponou a postfix notace. Logik Yan Lukasevich vynalezl první v roce 1920. Žil v Polsku, takže záznam se nazývá Polish. Postfix verze, respektive s názvem Reverse Polish Notation (ARF). Jediný rozdíl mezi těmito dvěma metodami je směr, ve kterém číst záznam (zleva doprava nebo zprava doleva), takže stačí uvažovat podrobně pouze jeden z nich. Operátor OPN je psán po jeho operandy. To znamená, že výraz AB + představuje příklad RPN pro A + B.

Neomezený počet operandů

Bezprostřední výhoda notace je, že shrnuje n adic operátora a přípona zápis je ve skutečnosti pouze pracuje se dvěma operandy, t. E. jsou přirozeně vhodný pouze pro binární operace. Například ABC @ je reverzní polský výraz pomocí triadic značku, které je maximální hodnota z A, B a C. V tomto případě operátor působí na levé straně tři operandu samotné a odpovídá volání funkce @ (A, B, C). Pokud se pokusíte zapsat symbol @ jako infix, například @ před naším letopočtem, nebo něco takového, je zřejmé, že to prostě nefunguje.

Priorita dána pořadí

RPN má další výhodu v tom, že prioritou operátorů mohou být reprezentovány v pořadí podle jejich vzhledu. Zároveň se nikdy potřebovat rovnátka, i když mohou být zahrnuty jako znaky operace s cílem usnadnit přechod z infixová notace. Například, AB + C * - jednoznačný ekvivalent (A + B) * C, takže násobení nelze vypočítat až přidávání provádí, což dává druhý operand pro násobení. To znamená, že v případě, že vypočtená AB + C * jeden pracovník v době, dostaneme AB + C * -> (AB +) * C -> (A + B) * C.

algoritmus výpočtu

Provozovatel OPN vypadá stejně jako funkce, která bere jako argumenty dvě hodnoty napsané na její levé straně. Kromě toho se jedná o přírodní notace pro použití v programovacích jazycích, jako způsob jeho výpočtu odpovídá zásobníku operace a nutnost provádění syntaktické analýzy jsou eliminovány. Například svodič ve výrazu 5 + 6 * 7 se objeví jako 5, 6, 7 *, +, a to může být vypočtena jednoduše skenováním zleva doprava a zapište hodnoty ve stohu. Kdykoli je společným znakem provozu zvolí horní prvek 2 z paměti počítače, operátor se používá a výsledek se vrátil do paměti. Když se konečný výsledek exprese výpočtu bude v horní části zásobníku.

Například:

• S = () 5, 6, 7, *, + 5 umístěn v zásobníku.
• S = (5), 6, 7, *, + 6 umístěn v zásobníku.
• S = (5, 6), 7 *, 7 + umístěte stoh.
• S = (5, 6, 7), * 2 + vybrat hodnoty ze stohu, použití * a výsledek ve stohu.
• S = (5, 6 * 7) = (5, 42) a 2 hodnoty vybrané ze stohu, aplikovat + a dát výsledek ve stohu.
• S = (5 + 42) = (47), výpočet je dokončen, výsledek je uložen v horní části zásobníku.

Tento algoritmus lze zkontrolovat RPN opakovaně, ale pokaždé, když to bude fungovat, bez ohledu na to, jak složité aritmetický výraz.

OPN a komíny jsou úzce spjaty. Tento příklad ukazuje, jak používat paměť pro výpočet hodnoty reverzní polské notace. Méně jasné je, že můžete použít balík, přestavovat standardní infixovou výraz v akutním selháním ledvin.

Příklady programovacích jazyků

Pascal RPN uvědomil takhle (ukazuje část programu).

Číst čísla a operátory v cyklu s názvem postup, který určuje, zda token číslo nebo znamení provozu. V prvním případě se hodnota uložená v zásobníku, a druhý z obou horních čísla zásobníku odpovídající akce se provádí, a výsledek je uložen.

toktype: = číslo;

čtení (s);

pokud c v [ '+', '-', '*', '/'] pak začne

pokud eoln pak CN: = '' else číst (KN);

pokud cn = ‚‘ poté

Případ

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

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

konec

else begin

v případě, že = '-', pak sgn: = -1 jiný chyba: = c <> '+';

s: = CN

konec

skončit;

if (není chyba) a (toktype = číslo), pak getnumber;

pokud toktype <> num pak začne

y = pop; x: = pop;

pokud není chyba poté

Případ toktype of

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

konec

tlak (z);

C-realizace RPN (zobrazeno součástí programu):

pro (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čítko (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

}

hardwarové realizace

V těch dnech, kdy výpočetní technika byla velmi drahá, to byla myšlenka jako dobrý nápad přinutit lidi, aby používali svodičů přepětí. V roce 1960-tých letech., Stejně jako dnes, bylo možné koupit kalkulačky, které pracují v opačném polské notaci. Chcete-li přidat 2 a 3 z nich je třeba zadat 2, pak 3, a stiskněte tlačítko „plus“. Na první pohled vstupní operandy na provozovatele zdálo složité a těžko zapamatovatelné, ale po chvíli některé z nich jsou závislé na tento způsob myšlení a nemohl pochopit, proč jiní trvají na stupidní infix, který je tak složitý a tak je omezen.

společnost Burroughs dokonce postavil sálový počítač, který měl žádnou jinou paměť, kromě zásobníku. Jediná věc, která dělá stroj - použila algoritmy a metody RPN do centrálního zásobníku. Všechny její operace byly považovány za svodiče operátory, které se vztahují k horní hodnoty n. Například tým vzal zpáteční adresy z vrcholu zásobníku, a tak dále. D. Architektura takový stroj byl jednoduchý, ale ne dost rychle, aby soutěžit s více rozšířené architektury. Mnozí však stále mrzí, že takový jednoduchý a elegantní přístup k práci na počítači, kde každý program byl výrazem OPN, našel jeho pokračování.

Jednorázové kalkulačky s RPN byly populární, a někteří lidé stále dávají jim přednost. Kromě toho vyvinula stoh orientované jazyky, jako je Forth. Dnes je málo používaný, ale stále nostalgicky z jeho bývalých uživatelů.

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

Budeme-li předpokládat, že provozovatel salámu se infix notace, by mělo být v rámci role, jako v běžném párek v rohlíku. RPN se nachází přímo na dvě poloviny připravte nimi po výpočtu. Nyní přichází to nejtěžší - hořčice. Je již na uzeniny, t. E. Již počítáno jako unární. Předpokládá se, že hořčice by měly být rovněž uvedeny jako nepředvídatelných a proto by měl být přesunut do pravé části salámu ... Ale je to možné, by to vyžadovalo příliš velkou hromadu ...