Reverzní polský záznam: algoritmus, metody a příklady

Reverzní polský záznam byl jednou základem světa počítačového programátora. Dnes to není tak dobře známé. Proto komiksová ilustrace, která zobrazuje "obrácenou" polskou klobásu mimo buchtu, může být stále špatně pochopena některými znalými programátory. Není to moc dobré vysvětlit tento vtip, ale v tomto případě bude zcela opodstatněné.

Vstup do infixu

Všichni programátoři a většina studentů jsou obeznámeni s používáním operátorů. Například ve výrazu x + y se znaménko sčítání používá k součtu hodnot proměnných x a y. Méně známá je skutečnost, že toto zapůjčení z matematického označení, nazývané infix notation, je ve skutečnosti velkým problémem pro stroje. Takový operátor bere jako vstup dvě hodnoty zapsané doleva a doprava. Při programování je zápis s provozními značkami nepovinný. Například, x + y může být zapsáno jako funkce pro přidání (x, y), ke které kompilátor nakonec převede zápis infix. Nicméně všichni vědí, že matematika příliš dobře nevyužívá aritmetické výrazy, které tvoří jakousi interní mini-jazyk téměř ve všech programovacích jazycích.

Překladatelé vzorců

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 se děje s infixem?

Problémem je, že operátoři mají vlastnosti, jako je priorita a asociativita. Z tohoto důvodu se definice funkce infixu stává netriviálním úkolem. 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 musíme použít závorky, abychom vytvořili výraz jasnější. 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 je třeba počítat operátory, vyžaduje dlouhé uložení. Z tohoto důvodu se studenti, kteří začínají učit aritmetiku, často dostávají špatné výsledky, i když ve skutečnosti jsou operace prováděny správně. Je třeba se učit pořadí operací operátorů srdcem. Za prvé musíme provést akce v závorkách, pak násobení a rozdělení a nakonec přidání a odečítání. Ale existují i ​​jiné způsoby psaní matematických výrazů, protože infix notace je jen jedním z možných "malých jazyků", které mohou být přidány k většímu.

Předpona a postfixová notace

Dvě nejoblíbenější alternativy jsou záznam operátora před nebo po operandech. Jsou známé jako předpony a postfixové notace. Logik Jan Lukasevič vynalezl první z nich ve dvacátých letech minulého století. Žil v Polsku, takže záznam se jmenuje polský. Postfixová verze byla označena jako reverzní polština (ARF). Jediným rozdílem mezi těmito dvěma metodami je směr, ve kterém je možné přečíst záznam (zleva doprava nebo zprava doleva), takže stačí uvést do úvahy pouze jednu z nich. V pojistce je operátor napsán za operandy. Takže výraz AB + je příkladem reverzního polského záznamu 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.

Prioritou je objednávka

Reverzní polský vstup má další výhodu v tom, že priorita operátorů může být reprezentována podle pořadí 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 * jedním pracovníkem v době, dostanete B + C * -> (A + B) * C -> (A + B) * C.

Algoritmus výpočtu

V operátoru OPN vypadá operátor jako funkce, která má jako argumenty dvě hodnoty zapsané vlevo od něj. 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. Po dosažení konce výrazu bude výsledek výpočtu na vrcholu zásobníku.

Například:

• S = () 5, 6, 7, *, + vložte 5 na zásobník.
• S = (5) 6, 7, *, + vložte 6 na zásobník.
• S = (5, 6) 7, *, + vložte 7 do zásobníku.
• S = (5, 6, 7) *, + vyberte ze zásobníku 2 hodnoty, použijte * a vložte výsledek do zásobníku.
• S = (5, 6 * 7) = (5, 42) + vyberte 2 hodnoty ze zásobníku, použijte + a vložte výsledek do zásobníku.
• S = (5 + 42) = (47) výpočet je kompletní, výsledek je v horní části zásobníku.

Tento algoritmus reverzního polského záznamu lze kontrolovat mnohokrát, ale pokaždé to bude fungovat bez ohledu na to, jak složitý je aritmetický výraz.

Zachycovač a zásobníky jsou úzce příbuzné. Výše uvedený příklad ukazuje, jak lze paměť použít k výpočtu hodnoty v inverzní polské notaci. Je méně zřejmé, že můžete použít zásobník konverzí standardních infix výrazů na svodič.

Příklady v programovacích jazycích

V jazyce Pascal je reverzní polský záznam implementován přibližně takto (část programu je dána).

Pro čtení čísel a operátorů ve smyčce se volá procedura, která určuje, zda token je číslo nebo operační znaménko. V prvním případě je hodnota zapsána do zásobníku, zatímco ve druhém případě je příslušná akce provedena na horních dvou číslech zásobníku a výsledek je uložen.

toktype: = číslo;

čtěte (c);

pokud v [`+`, `-`, `*`, `/`] začne

pokud eoln pak cn: = `` jinak číst (cn);

pokud cn = `pak

případ s

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

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

konce

jiný začátek

pokud c = `-` pak sgn: = -1 jinak chyba: = s <> `+`;

s: = cn

konce

konec;

pokud (ne chyba) a (toktype = num) pak getnumber;

pokud toktype <> num začíná

y: = roorx: = rop;

pokud ne chyba

případ toktype z

přidat: z: = x + y-sub: z: = x-y-mul: z: = x * y-div:

konce

push (z);

C implementace reverzního polského záznamu (část programu je dána):

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

a = strtod (s, e);

pokud (e> s) stiskněte (a);

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

else pokud (* s == `+`) rpnop (a + b);

else pokud (* s == `-`) rpnop (a - b);

else pokud (* s == `*`) rpnop (a * b);

else pokud (* s == `/`) rpnop (a / b);

#undef rpnop

}}

Implementace hardwaru

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, zadejte 2, potom 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.

Burroughs dokonce postavil sálový počítač, který neměl žádnou jinou paměť RAM, s výjimkou stohu. Jediná věc, kterou stroj dělal, je použití algoritmů a metod, které umožňují obrátit polský záznam na centrální zásobník. Všechny operace byly považovány za OPN operátory, jejichž působnost byla rozšířena na n nejvyšší hodnoty. Například příkaz návrat vzal adresu z horní části zásobníku atd. Architektura tohoto stroje byla jednoduchá, ale nebyla dostatečně rychlá, aby konkurovala obecnějším architekturám. Mnozí však stále litují, že takový jednoduchý a elegantní přístup k výpočtu, kdy každý program byl výrazem OPN, nenalezl jeho pokračování.

Současně byly oblíbené kalkulačky s reverzní polskou nahrávkou a někteří je ještě preferují. Navíc byly vyvinuty jazyky orientované na zásobníky, jako například Forth. Dnes je málo využívaná, ale přesto způsobuje nostalgii ze strany bývalých uživatelů.

Takže, co je smysl žertovat o návratu polské klobásy?

Pokud považujete operátora klobásy, pak v zápisu infix by měl být uvnitř role, jako u normálního hot dog. Naopak v polském záznamu je to vpravo od obou polovin, které jsou po výpočtu připraveny k úderu mezi nimi. Nyní začíná nejtěžší část - hořčice. Je již na klobásu, to znamená, že již byl vypočten jako unární operátor. Existuje názor, že hořčice by měla být také ukázána jako nedefinovaná, a proto by měla být přesunuta napravo od klobásy ... Ale možná to bude trvat příliš mnoho stohu ...