Reverzní polský záznam byl jednou základem světa počítačového programátora. Dneska není tak známá. Proto vtipné ilustrace, znázorňující "obrácenou" polskou klobásu mimo buchty, může být pro některé známé programátory ještě nepochopitelné. Není to dobré vysvětlení pro vtip, ale v tomto případě bude zcela opodstatněné.

Infix Record

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 + pro přidání hodnot proměnných x a y se použije symbol přídavku. Je méně známo, že označení zapůjčené z matematiky, nazývané infixnoy notace, je ve skutečnosti hlavním problémem strojů. Takový operátor bere jako vstup dvě hodnoty, psané nalevo a napravo od něj. Při programování je použití symbolů s operačními znaky nepovinné. Například, x + y je možno zapsat jako funkce draw (x, y), který se nakonec převede překladač ynfyksnuyu notaci. Všichni však dobře zná matematiku, aby nepoužívali aritmetické výrazy, které tvoří téměř jakýkoli vnitřní jazyk v téměř každém programovacím jazyce.

překladačů vzorce

První skutečně úspěšný programovací jazyk Fortran stal se tak především proto, že aritmetický výraz (tj vzorec) se ukázalo (vysílání) v kódu, proto jeho jméno - rovnice překlad. Předtím museli například nahrávatve formě funkcí tvoří (a, násobit (b, c)). V Kobolovi byl problém implementace automatické transformace vzorků považován za velmi obtížný, protože programátoři museli psát věci jako Add A to B. Mutliply C.

Co je špatné s infixem?

Problém spočívá v tom, že operátoři mají takové vlastnosti jako prioritu a asociativitu. Z tohoto důvodu se definice infixové funkce stává netriviálním úkolem. Například priorita násobení je vyšší než přidání nebo odečtení, což znamená, že výraz 2 + 3 * 4 není shodný se součtem 2 a 3 vynásobených 4, jako kdyby byli operátoři provedeni zleva doprava. Ve skutečnosti byste měli vynásobit 3 x 4 a přidat 2. Tento příklad ilustruje, že výpočet výrazů infix často vyžaduje změnu pořadí operátorů a jejich operandů. Navíc musíte použít závorky, aby se poznámka ukázala jasněji. Například (2 + 3) * (4 + 5) nelze psát bez závorek, protože 2 + 3 * 4 + 5 znamená, že musíte násobit 3 a 4 a přidat 2 a 5. Pořadí, ve kterém je nutné vypočítat operátory, vyžaduje dlouhé zapamatování. Z tohoto důvodu se školáci, začátečníci studia aritmetiky, často dostat nesprávné výsledky, i když skutečné operace jsou prováděny správně. Je nutné se učit operátory postupně srdcem. Nejprve je třeba provést akce v závorkách, násobení a rozdělení a nakonec přidání a odečítání. Ale existují i ​​jiné způsoby, jak psát matematické výrazy, jelikož infix notace je jen jeden z možných "malých jazyků", které lze přidat do většího jazyka.

Předpona a postfixPoznámka

Dvě z nejznámějších alternativních variant jsou záznam operátora před nebo po operandech. Jsou známé jako předpony a postfixové notace. Logik Jan Lukasiewicz přišel s první z nich ve dvacátých letech 20. století. Žil v Polsku, takže záznam se jmenuje polský. Varianta postfixu obdržela název reverzní polské notace (OPN). Jediný rozdíl mezi těmito dvěma metodami je směr, měli byste si přečíst záznam (zleva doprava nebo zprava doleva), takže některé detaily, aby v úvahu pouze jeden z nich. V OPN je operátor zaznamenán po jeho operandech. Takže výraz AB + je příkladem reverzní polské položky pro A + B.

neomezený počet operandů

zápis bezprostřední výhodou je, že shrnuje operátora n-adycheskym a ynfyksnaya notaci opravdu jen pracuje se dvěma hodnotami, které je ve své podstatě je vhodná pouze pro binární operace. Například ABC @ je inverzní polský výraz pomocí tryadycheskoho značku, které je maximální hodnota z A, B a C. V tomto případě je, že provozovatel 3 operandu opustil sám a splňuje funkci volání @ (A, B, C). Pokud se pokoušíte napsat znak "@" jako infix, jako například A @ BC nebo něco takového, pak bude jasné, že to prostě nefunguje.

priorita pořadí

Reverse Polish Notation je další výhodou je, že prioritou operátorů mohou být reprezentovány v pořadí podle jejich vzhledu. V tomto případě nebudou zátky nikdy potřebné, ačkoli mohou být zahrnuty jako známky operací, které se usnadníkonverze s infix notací. Například AB + C * je jedinečný ekvivalent (A + B) * C, protože násobení nelze vypočítat, dokud se neprovádí přidání druhého operandu pro operaci násobení. To znamená, že je-li AB + C * počítáno jedním provozovatelem najednou, pak A B + C * -> (A B +) * C -> (A + B) * C.

Výpočtový algoritmus

V OPC operátor vypadá stejně jako funkce, která přijímá jako dva argumenty hodnoty zapsané na jeho levé straně. Kromě toho je to přirozená notace pro použití v programovacích jazycích, neboť průběh výpočtů odpovídá operacím na zásobníku a neexistuje potřeba parsování. Například v OPC výraz 5 + 6 * 7 bude vypadat jako 567 *, +, a lze jej vypočítat jednoduše skenováním zleva doprava a zápisem hodnot do zásobníku. Při každém nalezení transakce jsou vybrány dva horní prvky paměti počítače, operátor je použit a výsledek je vrácen do paměti. Po dosažení konce výrazu se výsledek výpočtů zobrazí v horní části zásobníku. Například:

S = () 567 *, + vložte 5 do zásobníku.

S =
6 7 *, + vložte 6 do zásobníku.

S = (5 6) 7 *, + vložte 7 do zásobníku.

S = (567) *, + vyberte 2 hodnoty ze zásobníku, použijte * a vložte výsledek do zásobníku.

S = (5 6 * 7) = (542) + vyberte 2 hodnoty ze zásobníku, použijte + a umístěte výsledek do zásobníku.

S = (5 + 42) = (47) Výpočet je úplný, výsledek je v horní části zásobníku.

Tento algoritmus zpětného leštění může být kontrolován mnohokrát, ale pokaždé to bude fungovat bez ohledu na to, kolikaritmetický výraz je složitý. OPN a zásobníky jsou úzce propojeny. Níže uvedený příklad ukazuje, jak lze paměť použít k výpočtu hodnoty reverzní polské notace. Je méně zřejmé, že můžete použít zásobník, který transformuje standardní infix výrazy do TNF.

Příklady programovacích jazyků

V jazyce Pascal je reverzní polský záznam přibližně implementován (zobrazena část programu). Čtení čísel a operátorů v smyčce se nazývá postup, který určuje, zda token je číslo nebo znak operace. V prvním případě je hodnota zapsána do zásobníku a ve druhé nad dvěma horními čísly zásobníku se provede odpovídající akce a výsledek se uloží. toktype: = číslo; čtěte c); pokud v ['+', '-', '*', '/'] se začne, pokud eoln pak cn: = 'else else (cn); pokud cn = '' pak případ od '+': toktype: = add; '-': toktype: = sub; '*': toktype: = me; '/': toktype: = div konec jiný start, pokud c = '-' pak sgn: = -1 jinak chyba: = s & lt; & gt; '+'; c: = koncový konec cn; pokud (ne chyba) a (toktype = num) pak getnumber; pokud toktype < num začíná: = ro; x: = ro; v případě chyby pak případ, toktype add: z: = x + y; sub: z: = x-y; me: z: = x * y; div: z: = konce tlačítek x /y (z); C-realizace reverzního polského záznamu (část programu je dána): for (s = strtok (s, w); s; s = strtok (0 w)) {a = strtod (s & amp; e); pokud (e> s) zatlačte (a); #define rpnop (x) printf ("% c:", * s), b = (pop), a = (pop), push (x) else if (* s == '+') rpnop ); else pokud (* s == '-') rpnop (a - b); else pokud (* s == '*') rpnop (a * b); else pokud (* s == '/') rpnop (a /b); #undef rpnop}