Reverzní polská notace

Reverse Polish Notation (RPN) (anglicky RPN pro Reverse Polish Notation ), známá také pod názvem dodatečně stanovena zápisu , který se používá k napsání tak jednoznačné aritmetických vzorců bez použití závorek . Odvozen z polského zápisu předložené v roce 1924 podle polského matematik Jan Lukasiewiczova , se liší od toho, aby z hlediska operandy jsou zde prezentovány před operátorů, a ne naopak.

Například výraz „3 × (4 + 7)“ lze v NPI psát ve tvaru „4 {Ent} 7 + 3 ×“ nebo dokonce ve tvaru „3 {Ent} 4 {Ent} 7 + × “ .

Dějiny

Odvozen z polské notaci použitou poprvé v roce 1924 podle matematik polského logik Jan Lukasiewiczova se NPI byl vytvořen podle filozofa a Australian počítačový vědec Charles Leonard Hamblin (in) v polovině roku 1950 , aby výpočty bez odkazu na jakýkoli adresa paměti.

V pozdní 1960 , to bylo propuštěno k veřejnosti jako uživatelské rozhraní s stolními kalkulačkami Hewlett-Packard ( HP-9100 ), a poté s HP-35 vědecká kalkulačka v roce 1972 .

Výroba

Kalkulačky NPI jsou založeny na použití zásobníku , jinými slovy, operandy jsou uspořádány v horní části zásobníku, zatímco výsledky výpočtů jsou vráceny také v horní části zásobníku. I když tento koncept může začátečníka zmást, prezentace výrazu v opačném polském zápisu má výhodu stručnosti.

Praktické důsledky

Tato technika má několik výhod:

pořadí operandů je zachováno;
výpočty se provádějí čtením výrazu zleva doprava;
operandy předcházejí operátorovi a výraz, který popisuje každý operand, zmizí při vyhodnocení operace a bude nahrazen vypočítanou hodnotou.

Výhody

NPI má následující výhody:

psaní je zkráceno odstraněním závorek;
přechodný výsledek lze znovu použít. Například při výpočtu rychle vidíme, že výraz je použit dvakrát. Můžeme to duplikovat v zásobníku, což dává: sine(3×π4)3×π4{\ displaystyle {\ frac {\ mathrm {sin} ({\ frac {3 \ times \ pi} {4}})} {\ frac {3 \ times \ pi} {4}}}} ${\ frac {{\ mathrm {sin}} ({\ frac {3 \ times \ pi} {4}})}} {{\ frac {3 \ times \ pi} {4}}}}$ 3×π4{\ displaystyle {\ frac {3 \ krát \ pi} {4}}} ${\ frac {3 \ krát \ pi} {4}}$
- 3 [vstup] pi * 4 / DUP SIN SWAP / s operátory zásobníku DUP a SWAP k duplikování a výměně.
mezilehlé výpočty jsou řízeny ve formě zásobníku .
protože umožňuje zobrazit průběžné výsledky, umožňuje snadnější detekci chyb, a proto rychlejší ladění; v době prvních integrovaných obvodů to snižovalo jejich složitost (správa baterie a provozovatelé baterií).

S trochou praxe uživatel provede své výpočty rychleji na kalkulačce NPI než na kalkulačce notačně založeného zápisu.

Nevýhody

ani operátor, ani závorky používané jako oddělovač, je nutné poskytnout některé mezi dvěma po sobě následujícími operandy. Jeden prostor by měl být ve většině případů dostatečný;
operátor můžeme spustit pouze v případě, že je jednoznačný binární nebo unární , to znamená, že pracuje na dvou argumentech nebo jednom. Musíme tedy odlišit operátor binárního odčítání ( 10 - 2 se stane 10 2 - ) od unárního operátoru negace (- 2 se stane 2 NEG) . Obecněji platí, že operátor musí vzít pevný počet argumentů (existují ternární, kvartérní operátoři ...) nebo vzít pevný počet argumentů popisujících ostatní argumenty spotřebované operátorem. Funkce DROPN ( HP48 ) tedy spotřebuje první argument v zásobníku (celé číslo), což mu dává počet dalších argumentů, které se mají spotřebovat (v tomto případě počet prvků, které se mají ze zásobníku odebrat);
intelektuální gymnastika, která má být provedena, zvyšuje složitost současně s velikostí výrazu. V závislosti na tom, zda jste zvyklí na IPN, nebo ne, může cvičení vypadat zábavně nebo restriktivně .

Vlastnosti

Z komutativity sčítání vyplývá, že: ab + = ba + (v infixované notaci a + b = b + a.
Asociativita sčítání znamená, že: abc + + = ab + c + (v infixované notaci a + (b + c) = (a + b) + c.
Distributivita znamená, že: ab + c * = ac * bc * + (v infixované notaci (a + b) * c = a * c + b * c nebo c * (a + b)).

Příklad

Výpočet:

((1 + 2) × 4) + 3

lze zaznamenat v NPI

1 2 + 4 × 3 +

nebo

3 4 1 2 + × +

V praxi na kalkulačce s NPI bude výpočet zadán jako:

„1“, „zadat“ nebo „mezera“, „2“, „+“, „4“, „×“, „3“, „+“

nebo

„3“, „zadat“ nebo „mezera“, „4“, „zadat“ nebo „mezera“, „1“, „zadat“ nebo „mezera“, „2“, „+“, „×“, „+ " (pozorujeme, že první sekvence vyžaduje méně stisknutí kláves!)

Výraz je vyhodnocen následovně ( zásobník je zobrazen po každé operaci . Je reprezentován ve fyzickém smyslu , tj. Poslední položka v zásobníku nahoře, ačkoli mnoho kalkulaček z ergonomických důvodů umisťuje poslední položku na minimum):

	Vchod	Chirurgická operace	baterie
Krok n o 1	1	Stiskněte operand	1
Krok n o 2	2	Stiskněte operand	2 1
Krok n o 3	+	Přidání	3
Krok n o 4	4	Stiskněte operand	4 3
Krok n o 5	×	Násobení	12
Krok n o 6	3	Stiskněte operand	3 12
Krok n o 7	+	Přidání	15

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

Metoda, jak se snadno naučit NPI

Reverzní polskou notaci lze považovat za intuitivní, její obtížnost je dána především neznámostí (většina kalkulaček jiných než HP ji nepoužívá). K překladu algebraického výrazu (například (((1 + 2) × 4) +3) stačí přečíst jej tak, že si řeknete, co musíte udělat, to znamená rozumět algebraickému výrazu, provádět operace v správné pořadí (začněte zde přidáním 1 a 2, poté vynásobte 4 atd.).

Výpočet ((1 + 2) × 4) + 3 lze číst intuitivně:

Dal jsem 1, (1) ;
Přidám 2, (2 +) ;
Vynásobím 4, (4 ×) ;
Přidávám 3. (3 +) .

což jednoduše dává 1 2 + 4 × 3 +

Některá skutečná použití NPI

Programovací jazyk Forth
Programovací jazyk RPL (Hewlett Packard)
Tyto vědecké kalkulačky Hewlett-Packard se HP-35 , HP-41 , HP-28 , HP-48 , HP-15C , HP-35S , HP-12c , atd.
Operační systém Omega pro kalkulačku NumWorks , vidlice oficiálního operačního systému.
Jazyk popisu stránky PostScript
Program Calc integrovaný do Emacsu
Tabulky z Unixu , program DC
Psaní umělců
Jazyk popisu formátu bibliografie pro LaTeX a BibTex .bst .
v kosmických letech , kde představuje významnou časovou úsporu i nižší riziko chyb (žádné riziko chybějící nebo posunuté závorky)
modul MODET, používaný v programovacím jazyce pro seizmické zpracování Geovecteur (stejně jako v novější verzi Geocluster)
Většina profesionálních osvětlovacích konzolí (sady digitálních varhan) určených k programování světelných efektů ve světě zábavy.
Vytváření složité grafiky v rrdtools.
Jazyk WarpScript, vytvořený Warp10 za účelem usnadnění zpracování Geo-Time Series (GTS).

Poznámky a odkazy

Vstupte
(in) Co je RPN? , na webu hpmuseum.org, konzultováno 19. května 2013
(en) Biografie CLHanblin na webu vukutu
calc na webu gnu.org
Soubory stylu bibliografie (.bst) , viz zejména oddíl 16
Všimněte si, že balíček BibLaTeX LaTeXu nabízí pro úpravy stylů jednodušší syntaxi než bst.
Manuální stránka rrdgraph
https://www.warp10.io/

Související články