Reverzní polská notace

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. září 2021; kontroly vyžadují 2 úpravy .

Reverzní polská notace (RPN ) je forma zápisu matematických a logických výrazů, ve kterých jsou operandy umístěny před znaky operace . Také označovaný jako reverzní bezzávorková notace , postfixová notace , Lukasiewiczova bezzávorková symbolika , polská inverzní notace , POLIZ .

Zásobníkový stroj je algoritmus, který provádí výpočty pomocí reverzní polské notace (viz níže pro příklad vyhodnocení výrazů ).

Historie

Reverzní polská notace (RPN) byla vyvinuta australským filozofem a počítačovým teoretikem Charlesem Hamblinem v polovině 50. let na základě polské notace , kterou v roce 1920 navrhl polský matematik Jan Lukasiewicz . Hamblinova práce byla představena na konferenci v červnu 1957 a publikována v letech 1957 a 1962 .

První počítače podporující reverzní polskou notaci byly KDF9 od English Electric Company , který byl oznámen v roce 1960 a vydán (objevil se v prodeji) v roce 1963 , a americký Burroughs B5000 , oznámený v roce 1961 , vydaný ve stejném roce 1963. konstruktéři B5000, R. S. Barton , později napsal, že vyvinul reverzní polskou notaci nezávisle na Hamblinovi kolem roku 1958, když četl knihu o symbolické logice , a než se seznámil s Hamblinovou prací.

Friden přinesl svodič přepětí na stolní kalkulačky s EC-130 z června 1964. A v roce 1968 vyvinuli inženýři společnosti Hewlett-Packard stolní kalkulačku 9100A s podporou svodiče přepětí. Tato kalkulačka učinila reverzní polskou notaci populární mezi vědci a inženýry, i když raná reklama 9100A nezmiňovala svodič přepětí. V roce 1972 se kalkulačka HP-35 s podporou SPD stala první vědeckou kapesní kalkulačkou .

V roce 1971 se objevil původní programovací jazyk Forth , jehož jazykový stroj má dvouvrstvou strukturu a všechny výpočty se provádějí na zásobníku . V tomto jazyce je OPN přirozeným způsobem zápisu jakýchkoli datových operací, i když je možné v případě potřeby implementovat obvyklou ( infixovou ) notaci aritmetických operací.

Svodič byl použit v sovětském inženýrském kalkulátoru B3-19M (vyvinutém společně s NDR), vydaném v roce 1976. Všechny programovatelné mikrokalkulátory vyráběné v SSSR do konce 80. let 20. století s výjimkou Elektronika MK-85 a Elektronika MK-90 používaly svodič - jeho implementace byla jednodušší a umožnila vystačit si při programování výpočtů s menším počet příkazů ve srovnání s obvyklou algebraickou notací a množství programové paměti v těchto modelech byly vždy kritickým zdrojem. Svodič se používá v moderních ruských programovatelných kalkulátorech " Elektronika MK-152 " a " Elektronika MK-161 ", což zajišťuje jejich kompatibilitu s programy napsanými pro sovětské kalkulačky.

Definice

Abychom dali induktivní definici postfixové notace [1] , označme výrazy v infixové notaci , , , jejich ekvivalentní výrazy v postfixové notaci , , respektive; je libovolný binární operátor, pak: $E$ $E_1$ $E_2$ $\tečka E$ $\tečka E_1$ $\tečka E_2$ $Ó$

1. If - proměnná nebo konstanta, to je . $E$ $\tečka E$ $E$

2. If je výraz ve tvaru , to je . $E$ $E_1 nebo E_2$ $\tečka E$ $\tečka E_1 \tečka E_2 o$

3. If je výraz ve tvaru , tedy . $E$ $(E_1)$ $\tečka E$ $\tečka E_1$

Popis

Charakteristickým rysem reverzní polské notace je, že všechny argumenty (nebo operandy ) jsou umístěny před znakem operace. Obecně záznam vypadá takto:

Záznam sady operací se skládá ze sekvence operandů a operačních znaků. Operandy ve výrazu jsou při zápisu odděleny mezerami.
Výraz se čte zleva doprava. Když se ve výrazu vyskytne znak operátoru, odpovídající operace se provede na posledních dvou operandech, které se vyskytují před ním, v pořadí, v jakém jsou zapsány. Výsledek operace nahradí posloupnost jejích operandů a její znaménko ve výrazu, načež je výraz dále vyhodnocen podle stejného pravidla.
Výsledek vyhodnocení výrazu je výsledkem poslední vyhodnocené operace.

Zvažte například vyhodnocení výrazu 7 2 3 * −(ekvivalentní výraz v infixové notaci: 7 − 2 * 3).

První znaménko operace je "*", takže operace násobení se provede nejprve na operandech 2 a 3 (jsou poslední před znaménkem). Výraz se pak převede do tvaru 7 6 −(výsledek násobení - 6 - nahradí trojici "2 3 *").
Druhý znak operace je "−". Operace odečítání se provádí na operandech 7 a 6.
Výpočet dokončen. Výsledek poslední operace je 1, to je výsledek vyhodnocení výrazu.

Zjevné rozšíření reverzní polské notace na unární, ternární a operace s jakýmkoli jiným počtem operandů: při použití znamének takových operací při vyhodnocování výrazu je operace aplikována na odpovídající počet naposledy nalezených operandů.

Rysy reverzní polské notace jsou následující:

Pořadí provádění operací je jednoznačně určeno pořadím znaků operace ve výrazu, není tedy potřeba používat závorky a zavádět priority a asociativitu operací.
Na rozdíl od infixové notace není možné používat stejné znaky pro zápis unárních a binárních operací. Takže v infixové notaci výraz 5 * (−3 + 8)používá znaménko mínus jako symbol unární operace (změna znaménka čísla) a výraz (10 − 15) * 3používá stejné znaménko k označení binární operace (odčítání). Konkrétní operace je určena pozicí postavy. Reverzní polská notace to neumožňuje: notace 5 3 − 8 + *(podmíněná analogie prvního výrazu) bude interpretována jako chybná, protože není možné určit, že „mínus“ za 5 a 3 neznamená odčítání; v důsledku toho bude proveden pokus o výpočet nejprve 5 − 3, potom 2 + 8, načež se ukáže, že pro operaci násobení není dostatek operandů. Chcete-li tento výraz stále napsat, budete jej muset buď přeformulovat (například napsáním výrazu místo − 3výrazu 0 − 3), nebo zavést samostatné označení pro operaci změny znaménka, například „±“: 5 3 ± 8 + *.
Stejně jako v infixovém zápisu lze v OPN zapsat jeden a tentýž výpočet v několika různých verzích. Například výraz (10 − 15) * 3v OPN může být zapsán jako 10 15 − 3 *, nebo jej můžete napsat jako3 10 15 − *
Kvůli nedostatku závorek je reverzní polská notace kratší než infix. Díky tomu se při počítání na kalkulačkách zvyšuje rychlost práce operátora (snižuje se počet stisknutých kláves) a u programovatelných zařízení se snižuje objem těch částí programu, které popisují výpočty. Posledně jmenovaný může být důležitý pro přenosná a vestavěná výpočetní zařízení, která mají vážná omezení velikosti paměti.

Výpočty zásobníku

Obecný řád

Automatizace vyhodnocování výrazů v reverzní polské notaci je založena na použití zásobníku . Výpočtový algoritmus pro zásobníkový stroj je elementární:

Zpracování vstupních symbolů
- Pokud je jako vstup zadán operand, je posunut na vrchol zásobníku.
- Pokud je na vstup dán znak operace, provede se odpovídající operace s požadovaným počtem hodnot vytažených ze zásobníku, v pořadí sčítání. Výsledek provedené operace je umístěn na horní straně zásobníku.
Pokud vstupní znaková sada není zcela zpracována, přejděte ke kroku 1.
Po úplném zpracování vstupní znakové sady leží výsledek vyhodnocení výrazu na vrcholu zásobníku.

Implementace stohovacího stroje, jak softwarově, tak hardwarově, je extrémně jednoduchá a může být velmi efektivní. Reverzní polská notace je zcela sjednocená - v podstatě stejným způsobem zapisuje unární, binární, ternární a libovolné další operace a také volání funkcí, což umožňuje nekomplikovat návrh výpočetních zařízení a zároveň rozšířit množinu podporovaných operací. To byl důvod pro použití reverzní polské notace v některých vědeckých a programovatelných kalkulačkách.

Příklad vyhodnocení výrazu

Infixový výraz v GRE lze zapsat takto: $(1 + 2)\krát 4 + 3$ 1 2 + 4 × 3 +

Výpočet se provádí zleva doprava, zadání je interpretováno tak, jak je uvedeno v tabulce níže (je uveden stav zásobníku po operaci, horní část zásobníku je zvýrazněna červeně ):

Vstup	Úkon	Zásobník
jeden	dát na stoh	jeden
2	dát na stoh	1, 2
+	přidání	3
čtyři	dát na stoh	3, 4
*	násobení	12
3	dát na stoh	12, 3
+	přidání	patnáct

Výsledek, 15, je na konci výpočtu v horní části zásobníku.

Klávesa "Enter" (na kalkulačkách označená jako "Enter" nebo symbol "↑") funguje jako oddělovač operandů, když jsou dva operandy bezprostředně vedle sebe. Pokud za operandem následuje znak operace , pak jeho stisknutí není vyžadováno, což snižuje počet akcí, které je třeba provést k získání výsledku.

Převod z infixové notace

Edsger Dijkstra vynalezl algoritmus pro převod výrazů z infixové notace na IPV. Algoritmus byl nazýván "seřaďovací nádraží", pro podobnost jeho operací s tím, co se děje na železničních seřaďovacích nádražích. Infixová notace je forma matematické notace, kterou většina lidí používá (například 3 + 4nebo 3 + 4 * (2 − 1)). Stejně jako algoritmus výpočtu SPV je algoritmus seřaďovacího nádraží založen na zásobníku. Konverze se účastní dvě textové proměnné: vstupní a výstupní řetězce. Proces převodu používá zásobník, který ukládá operace, které ještě nebyly přidány do výstupního řetězce. Konverzní program čte vstupní řetězec znak po znaku v sekvenci (znak nemusí být nutně písmeno), v každém kroku provádí některé akce v závislosti na tom, který znak byl přečten.

Jednoduchý příklad

Vchod:3 + 4

Přidat 3na výstupní řádek (pokud je přečteno číslo, je okamžitě přidáno do výstupního řádku).

Push +(nebo jeho identifikátor) do zásobníku operací.

Přidejte 4do výstupního řádku.

Přečetli jsme celý výraz, nyní přesuneme všechny operace zbývající na zásobníku na výstupní řádek. V našem příkladu zásobník obsahuje pouze +.

Výstupní linka:3 4 +

V tomto příkladu se objevují některá pravidla: všechna čísla jsou přenesena na výstupní řádek ihned po přečtení; když je výraz zcela přečten, všechny zbývající operace v zásobníku se přesunou na výstupní řádek.

Algoritmus

I když je zde více znaků ke čtení:

Čteme další postavu.
Pokud je znakem číslo nebo postfixová funkce (například ! - faktoriál ), připojte jej k výstupnímu řetězci.
Pokud je symbol funkcí předpony (například sin - sinus ), zatlačte jej na zásobník.
Pokud je znakem otevřená závorka, zatlačte jej na hromádku.
Pokud je znakem uzavírací závorka:

Dokud není horním prvkem zásobníku otevírací závorka, vysuňte prvky ze zásobníku na výstupní řetězec. Tím se odstraní otevírací závorka ze zásobníku, ale nepřidá se do výstupního řetězce. Pokud zásobník skončil dříve, než jsme se setkali s otevírací závorkou, znamená to, že buď je oddělovač ve výrazu špatně umístěn, nebo závorky nejsou shodné.

Pokud existují různé typy závorek, výskyt neodpovídající závorky také znamená chybu. Pokud jsou některé závorky funkcemi současně (například [x] je celočíselná část ), přidáme do výstupního řetězce symbol této funkce.

Pokud je symbolem binární operace o1 , pak:

1) zatímco v horní části zásobníku je funkce předpony ... … NEBO operace v horní části zásobníku má vyšší prioritu nebo stejnou úroveň priority jako o1 … NEBO operace horní části zásobníku je asociativní vlevo s prioritou o1 ... zatlačte horní prvek zásobníku do výstupního řetězce; 2) zatlačte operaci o1 na zásobník.

Po skončení vstupního řetězce přesuňte všechny znaky ze zásobníku do výstupního řetězce. Na hromádce měly zůstat pouze operační symboly; pokud tomu tak není, pak výraz neodpovídá závorkám.

Omezení a úpravy

Algoritmus předpokládá, že zdrojový řetězec je správný (ne všechny chyby jsou zkontrolovány) a všechny funkce předpony/přípony jsou unární.

Viz hlavní článek pro úpravu vícemístných funkcí s pevným počtem argumentů .

Pro operace jako -x , které jsou binární i unární, je nutná úprava: když je taková operace nalezena, systém se podívá na předchozí znak a určí, zda je mínus binární operace nebo unární funkce. Proto zásobník a NPV potřebují různé symboly pro binární a unární mínus.

Komplexní příklad

Priority :

nejvyšší: výrazy v závorkách ( )
vysoká: ^
průměrný: * /
nízká: + −

Vstup: 3 + 4 * 2 / (1 - 5)^2 Čteme "3" Přidejte "3" do výstupního řetězce Výstup: 3 Čteme "+" Dejte na hromádku „+“. Výstup: 3 Zásobník: + Čteme "4" Přidejte "4" do výstupního řetězce Výstup: 34 Zásobník: + Čteme "*" Zatlačte "*" na zásobník Výstup: 34 Zásobník: + * Čteme "2" Přidejte "2" do výstupního řetězce Výstup: 3 4 2 Zásobník: + * Čteme "/" Přesuňte "*" ze zásobníku na výstupní řetězec, stiskněte "/" na zásobník Výstup: 3 4 2 * Zásobník: + / Čteme "(" Zatlačte "(" na zásobník Výstup: 3 4 2 * Zásobník: + / ( Čteme "1" Přidejte "1" k výstupnímu řetězci Výstup: 3 4 2 * 1 Zásobník: + / ( Čteme "-" Zatlačte "-" na zásobník Výstup: 3 4 2 * 1 Zásobník: + / ( − Čteme "5" Přidejte "5" do výstupního řetězce Výstup: 3 4 2 * 1 5 Zásobník: + / ( - Čteme ")" Pop "−" ze zásobníku do výstupního řetězce, pop "(" Výstup: 3 4 2 * 1 5 − Zásobník: + / Čteme "^" Vložte "^" na zásobník Výstup: 3 4 2 * 1 5 − Zásobník: + / ^ Čteme "2" Přidejte "2" do výstupního řetězce Výstup: 3 4 2 * 1 5 − 2 Zásobník: + / ^ Konec projevu Vysunování všech prvků ze zásobníku do řetězce Výstup: 3 4 2 * 1 5 − 2 ^ / +

Optimalizace výrazů

Pokud píšete interpret, pak výstupní řetězec získaný po převodu původního výrazu do reverzní polské notace lze uložit místo původního výrazu pro pozdější interpretaci. Reverzní polská notace také umožňuje počítači zjednodušit výrazy.

Příklad algoritmu pro zjednodušení výrazu

Zvažte algoritmus, který provádí předvýpočet konstant ve výrazu. Výraz je uveden v OPN. Potřebujeme zásobník pro ukládání smíšených dat (čísla a operátory).

Algoritmus je podobný tomu, který se používá k vyhodnocování výrazů. Skenujeme výraz zleva doprava.

Pokud existují znaky ke čtení:

Čteme další postavu.
Pokud je znakem číslo, zatlačte ho na hromádku.
Pokud je znakem proměnná, za předpokladu, že proměnná je null , vložte znak do zásobníku.
Pokud je symbol operátor:
1) (pokud mají všechny operátorové argumenty v zásobníku jinou hodnotu než null ) vytáhne argumenty operátoru ze zásobníku a vloží výsledek operace do zásobníku;
2) (pokud je alespoň jeden z argumentů null ) za předpokladu, že výsledek operace je null , vložíme do zásobníku symbol operátoru.

Po prozkoumání celého výrazu zůstane v zásobníku optimalizovaný výraz (příkazy výrazu jsou v zásobníku v obráceném pořadí).

Příklad toho, jak algoritmus funguje

Výraz Infixový zápis: exp(-1/2*x) Reverzní polská notace: -1 2 / x * zk Čtení: "-1" Zatlačte "-1" na zásobník Zásobník: -1 Čtení: "2" Zatlačte "2" na stoh Zásobník: -1 2 Čteme: "/" Vypočítáme kvocient, výsledek vložíme do zásobníku Zásobník: -0,5 Čtení: "x" Zatlačte "x" do zásobníku s hodnotou null Zásobník: -0,5x (null) Čteme: "*" Stiskněte "*" do zásobníku s hodnotou null Zásobník: -0,5 x (null) * (null) Čteme "exp" Push "exp" do zásobníku s hodnotou null Zásobník: -0,5 x (null) * (null) exp (null) Výsledek optimalizace: -0,5 x * zk

Tato metoda samozřejmě nezahrnuje všechny možné optimalizační metody.

Příklady implementace

Článek " Reverzní polská notace: příklady implementace " obsahuje příklady implementace reverzní polské notace v různých programovacích jazycích.

Praktické implementace

Jako praktickou aplikaci této techniky můžeme uvést uspořádání konfigurací bytecode aplikačních řešení systému 1C:Enterprise . 1C neposkytuje oficiální potvrzení , ale uživatelé tohoto systému na specializovaných fórech poskytují důkazy a algoritmy, které umožňují dekompilaci zdrojových textů.

Literatura

T. Pratt, M. Zelkowitz. Programovací jazyky: Návrh a implementace = Terrence W. Pratt, Marvin V. Zelkowitz. Programovací jazyky: Návrh a implementace. - 4. vydání. - Petr, 2002. - 688 s. — (Klasika informatiky). - 4000 výtisků. - ISBN 5-318-00189-0 .

Poznámky

↑ A. V. Aho, R. Seti, D. D. Ulman. Kompilátory: principy, technologie a nástroje. M.: "Williams", 2003. S. 51.

Viz také

Programovací jazyky, které používají OPN jako hlavní:

Forth
faktor
dovětek
Jazyk stylů BibTeX