Notație postfixată

Ordinea operanzilor și operatorului în notația postfixată

Notația postfixată[1][2] sau notația poloneză postfixată (în engleză Reverse Polish notation – RPN[3]) este o notație pentru o operație matematică și logică în care operatorii sunt plasați după operanzi, cum ar fi semnul plus în expresia 3 4 +.

Avantajul acestei notații este că nu are nevoie de paranteze cât timp fiecare operator are un număr de operanzi fix. Descrierea „poloneză” se referă la naționalitatea logicianului Jan Łukasiewicz,[4][5] care a inventat această notație în 1924.[6][7][8][9][10]

Primul calculator care a folosit logica notației postfixate, deși a rămas mult timp necunoscut în afara Germaniei, a fost Z3 al lui Konrad Zuse, în 1941,[11][12][13][14][15][16][17][18] ca și Z4 în 1945. Schema postfixată a fost propusă din nou în 1954 de Arthur Burks, Don Warren și Jesse Wright[19] și a fost rescoperită independent de Friedrich L. Bauer și Edsger W. Dijkstra la începutul anilor 1960 pentru a reduce accesul la memoria calculatoarelor, folosind stiva pentru a evalua expresiile matematice. Algoritmii și notațiile pentru această schemă au fost extinse de către filozoful și informaticianul australian Charles Leonard Hamblin la mijlocul anilor 1950.[20][21][22][23][24][25][26]

În anii 1970 și 1980, Hewlett-Packard a folosit logica postfixată în toate calculatoarele lor de birou și de buzunar și a continuat s-o folosească în unele modele până în anii 2020.[27][28]

În informatică, notația postfixată este folosită în limbaje de programare orientate pe stivă⁠(d), cum ar fi Forth, STOIC, PostScript, RPL și Joy.

Explicarea funcționării

În notația postfixată operatorii urmează operanzii. De exemplu, pentru a aduna 3 cu 4 s-ar scrie 3 4 + în loc de 3 + 4. Dacă există mai multe operații, operatorii sunt dați imediat după operanzii lor (deseori un operator acționează asupra a doi operanzi, caz în care operatorul este scris după al doilea operand); deci expresia scrisă 3 − 4 + 5 în notație convențională (infixată) s-ar scrie 3 4 − 5 + în notația postfixată, unde mai întâi este scăzut 4 din 3, apoi este adunat 5.

Acest mod de lucru este adecvat pe o stivă, unde se aplică regula „ultimul intrat, primul ieșit”. În exemplul de mai sus, 3 este încărcat în partea de jos a stivei (nivelul vizibil) și o acțiune specială (de exemplu apăsarea tastei "Enter ↑ pe un calculator) termină intrarea. Fără această acțiune 4 ar fi atașat la 3, dând 34, ceea ce nu este ce s-a dorit. Când este introdus 4, 3 este „promovat” pe al doilea nivel al stivei, fiind acum deasupra lui 4, vizibil în acest moment. Operatorul de scădere acționează imediat asupra primelor două niveluri ale conținutului stivei, scăzând valoarea de jos din cea de sus, obținând −1 la primul nivel. Acest lucru oprește și introducerea datelor, astfel încât 5 poate fi introdus imediat. Acest lucru ridică automat −1 la al doilea nivel. Atunci când utilizatorul apasă apoi + (adunare), conținutul primelor două niveluri este adunat, iar rezultatul, 4, apare în partea de jos. Această promovare (și retrogradare) automată a datelor între nivelurile din stivă, pe măsură ce fiecare operație este efectuată, plasează automat operanzii succesivi așa cum sunt necesari.

În multe calculatoare HP stiva are patru niveluri. Deci, este posibil să se introducă 3, Enter ↑, să se tasteze 4, Enter ↑, să se tasteze 5, Enter ↑ și să se tasteze 6. Acum stiva conține cele patru valori în cele patru niveluri ale sale. Apoi se poate apăsa butonul + de trei ori, iar suma, 18, va apărea la nivelul unu. Orice introducere nouă de date îl promovează pe 18 la nivelul doi. Această activitate este limitată doar de „înălțimea” (mărimea) stivei.

Gestionarea atentă a stivei permite ca expresiile complexe, cu multe paranteze, să fie evaluate într-un mod liniar simplu. Rareori este necesar ca rezultatele intermediare să fie stocate și rechemate, așa cum este nevoie de obicei la sistemele care lucrează în stilul notațiilor algebrice obișnuite.

Prin urmare, avantajul notației postfixate este că elimină necesitatea parantezelor care sunt cerute de notația infixată, deoarece stiva deține toate argumentele într-o progresie ultimul intrat, primul ieșit. De exemplu, pentru a calcula expresia (3 × 4) + (5 × 6), ar trebui tastat 3, apăsat Enter ↑ și tastat 4. La apăsarea × (înmulțire), produsul intermediar 12 apare în partea de jos a stivei. Apoi se tastează 5, Enter ↑ și 6. Rezultatul intermediar 12 a fost promovat la nivelul trei, cu 5 la nivelul doi și 6 la nivelul unu. Este necesar doar apăsarea succesivă a × și apoi a +. Produsul intermediar, 30, apare primul la nivelul unu, iar apoi rezultatul final, 42, apare tot la nivelul unu, deoarece acum s-a adunat 12 de la nivelul doi.

Implicații practice

Prin comparație, la testarea notației postfixate cu notația algebrică, s-a constatat că postfixata duce la calcule mai rapide, din două motive. Primul motiv este că calculatoarele care lucrează după logica postfixată nu au nevoie de paranteze, așa că trebuie introduse mai puține operațiuni pentru a efectua calcule tipice. În plus, utilizatorii calculatoarelor postfixate au făcut mai puține greșeli decât în cazul altor tipuri de calculatoare,[29][30] fapt care poate fi atribuit numărului mai mic de apăsări de taste necesare pentru a introduce această notație.[31] Totuși, dovezi empirice sugerează că notația postfixată este mai dificil de învățat de către utilizatori decât notația algebrică.[30]

Realizări

Limbaje de programare orientate pe notația postfixată

Calculatoare

Primul calculator în logică postfixată a fost Z3 al lui Konrad Zuse, construit în 1938 și prezentat publicului la 12 mai 1941.[14][16][38][39] În mod interactiv, permitea introducerea a doi operanzi urmați de operatorul dorit.[11][12][13][14][15][16][17][18][40] Acesta a fost distrus la 21 decembrie 1943 într-un raid de bombardament.[14] Cu ajutorul lui Zuse, în 1961 a fost construită o replică a sa.[14] La calculatorul Z4 din 1945 a fost adăugată o stivă.[41][42]

La începutul anilor 1960 English Electric Company a lansat modelele KDF9 și Burroughs B5000[43] după ideile lui Hamblin.[20][21][24]

Calculatorul demonstrativ al Hewlett-Packard "No Equals" era în logică RPN

Hewlett-Packard a realizat HP 9100A în 1968,[27] HP-35 în 1972[27] și HP-10 în 1977. Apoi a produs calculatoarele cu afișaj cu cristale lichide HP-10C, HP-11C, HP-15C, HP-16C și HP-12C, iar în 1990 HP-19BII dispunea de opțiunea de a funcționa în notație infixată sau postfixată. Printre ultimele modele RPN ale HP au fost 12C, 12C Platinum, 17bii+.

În Marea Britanie modelele Sinclair Scientific și Sinclair Scientific Programmable foloseau logica postfixată.[44][45]

În URSS s-au realizat calculatoarele MK-52, MK-61, Elektronika B3-34 și vechiul B3-21,[46][47] și mai modernul MK-161,[48] bazate și ele pe logica postfixată.

Simulatoare

și încă câteva.

Note

  1. ^ Ioan Ivan, Marius Popa, Paul Pocatilu, Structuri de date, București, Editura ASE, 2008, ISBN: 978-606-505-031-0
  2. ^ Cristian Masalagiu, Logica/calculul cu predicate de ordinul I, Universitatea Al. I. Cuza, Iași, 2019, accesat 2021-08-12
  3. ^ en „The Implementation and Power of Programming Languages”. Accesat în . 
  4. ^ en Łukasiewicz, Jan (). „Chapter IV. Aristotle's System in Symbolic Form (section on "Explanation of the Symbolism")”. Aristotle's Syllogistic from the Standpoint of Modern Formal Logic (ed. 1). p. 78. 
  5. ^ en Łukasiewicz, Jan (). Aristotle's Syllogistic from the Standpoint of Modern Formal Logic (ed. 2). Oxford University Press.  (Reprinted by Garland Publishing in 1987 ISBN: 0-8240-6924-2.)
  6. ^ pl Łukasiewicz, Jan (februarie 1929). Elementy logiki matematycznej (ed. 1). Warsaw, Poland: Państwowe Wydawnictwo Naukowe 
  7. ^ en Łukasiewicz, Jan (). Elements of mathematical logic. Tradus de Wojtasiewicz, Olgierd Adrian. New York, USA: The MacMillan Company. p. 24. 
  8. ^ en Hamblin, Charles Leonard (). „Translation to and from Polish notation” (PDF). Computer Journal. 5 (3): 210–213. doi:10.1093/comjnl/5.3.210 Accesibil gratuit. Arhivat din original (PDF) la .  (4 pages)
  9. ^ en Ball, John A. (). Algorithms for RPN calculatorsNecesită înregistrare gratuită (ed. 1). Cambridge, Massachusetts, USA: Wiley-Interscience, John Wiley & Sons, Inc. ISBN 0-471-03070-8. [...] In their advertisements and also in a letter to me, Hewlett-Packard Company (HP), the best known manufacturer of RPN calculators, says that RPN is based on a suggestion by Jan Łukasiewicz (1878–1956), and that RPN was invented and is patented by HP. Aside from the apparent contradiction in these two statements, I do not think that either of them is quite true. My first experience with RPN involved a nice old Friden EC-130 desktop electronic calculator, circa 1964. The EC-130 has RPN with a push-down stack of four registers, all visible simultaneously on a cathode ray tube display. Furthermore, they are shown upside down, that is, the last-in-first-out register is at the bottom. [...] Around 1966, the Monroe Epic calculator offered RPN with a stack of four, a printer, and either 14 or 42 step programmability. The instruction booklets with these two calculators make no mention of RPN or Jan Łukasiewicz. [...] 
  10. ^ en Kennedy, John (august 1982). „RPN Perspective”. PPC Calculator Journal. Mathematics Department, Santa Monica College, Santa Monica, California, USA. 9 (5): 26–29. CiteSeerX 10.1.1.90.6448 Accesibil gratuit. Arhivat din original la . Accesat în .  (12 pages)
  11. ^ a b en Ceruzzi, Paul E. (aprilie 1980). „1941 RPN Computer?”. PPC Calculator Journal. 7 (3): 25. Arhivat din original la . Accesat în . The interesting aspect of the programming of the Z-3 was that this code was very similar to that of, say, an HP-25. To perform an operation on two numbers, commands would first be given to recall the numbers from appropriate locations in the memory, followed by the command for the operation. Numbers were automatically positioned in registers in the Arithmetic Unit of the machine so that operations like division and subtraction would proceed in the right order. Results were left in a register in the AU so that long sequences of operations could be carried out. Thus, the Z-3 used a version of RPN that was nearly identical to that used by HP! I have obtained copies of early programs that Zuse had written for the evaluation of a 5 x 5 determinant, and it is possible to run these programs on an HP-41C with almost no modification whatsoever (once the numbers have been placed in the storage registers beforehand). The AU of the Z-3 contained 3 registers, although Zuse never referred to them as a stack, of course. These registers were labelled "f", "a", and "b". All entrance and exit to and from the AU was through the "f" register. This is sort of like the display register of the 41C, which is distinct from the stack. Arithmetic operations were performed on numbers in the a and b registers, so these may be thought of as corresponding to the x and y registers of HP's. Unlike modern computer practice, the actual numbers themselves were moved around the registers, not just a pointer. 
  12. ^ a b en Ceruzzi, Paul E. (). „2. Computers in Germany”. Reckoners - The prehistory of the digital computer, from relays to the stored program concept, 1935–1945. Contributions to the study of computer science. 1 (ed. 1). Westport, Connecticut, USA: Greenwood Press, Congressional Information Service, Inc. p. 0010. ISBN 0-313-23382-9. ISSN 0734-757X. LCCN 82-20980. Arhivat din original la . Accesat în . 
  13. ^ a b de Zuse, Horst. „2. Dialogfähigkeit der Maschine Z3”. Scris în Berlin, Germany. În Cremers, Armin B.; Manthey, Rainer; Martini, Peter; Steinhage, Volker. Die ergonomischen Erfindungen der Zuse-Maschinen (PDF). INFORMATIK 2005 Informatik LIVE! Band 1, Beiträge der 35. Jahrestagung der Gesellschaft für Informatik e.V. (GI), 19. bis 22. September 2005 in Bonn. Lecture Notes in Informatics. Bonn, Germany: Gesellschaft für Informatik (GI). pp. 200–204 [200–201]. Arhivat din original (PDF) la . Accesat în . Dazu stehen die beiden Register R1 und R2 als Kurzspeicher für die Operanden der arithmetischen Operationen zur Verfügung. Gerechnet wird in der umgekehrten polnischen Notation, wie z.B. beim Taschenrechner HP 45 (1972) oder HP11 (1998).  (5 pages)
  14. ^ a b c d e de Zuse, Horst, ed. (). „Z3 im Detail” [Z3 in details]. Professor Dr.-Ing. habil. Horst Zuse. Arhivat din original la . Accesat în . Die Z3 konnte in zwei Betriebsmodi betrieben werden, und zwar in dem Programm- und Dialogmodus. Das Rechnen im Dialog erfolgt wie mit einem Taschenrechner in der umgekehrten polnischen Notation.  [1]
  15. ^ a b en Bonten, Jo H. M. (). „Fast Calculators: Konrad Zuse's Z1 and Z3”. Geldrop, Netherlands. Arhivat din original la . Accesat în . The computer can be used as a simple hand-held calculator. In this mode besides entering the numeric values the user must enter the instructions and the addresses by pressing their keys. He has to enter the numbers and operators in the reverse Polish notation. 
  16. ^ a b c de Bundesmann, Jan (iunie 2016). „Zum 75. Geburtstag von Konrad Zuses Z3: Ratterkasten”. Report / Jubiläum. iX. Vol. 2016 nr. 6. Heise Verlag. p. 94. Arhivat din original la . Accesat în . Zum Eingeben der Zahlen stand eine Tastatur bereit (Dezimalzahlen, Gleitkommadarstellung). Anweisungen gaben Nutzer in umgekehrter polnischer Notation: zuerst die Argumente, um Register zu befüllen, dann der auszuführende Operator. 
  17. ^ a b de „Die Computerwelt von Konrad Zuse - Auf den Spuren eines EDV-Genies” (PDF). Die Welt der technischen Museen. Welt der Fertigung. Vol. 2018 nr. 2. . pp. 32–35. ISSN 2194-9239. Arhivat din original (PDF) la . Accesat în . Er hat wohl auch als erster die vom polnischen Mathematiker Jan Lukasiewicz entwickelte ›polnische Notation‹ weiterentwickelt und daraus die ›umgekehrte polnische Notation‹ (UPN) ersonnen, da diese in seinen Rechnern verwendet wird: zunächst werden die Werte eingegeben, danach die gewünschte Rechenoperation ausgelöst. Klammern werden auf diese Weise vermieden.  (4 pages)
  18. ^ a b de Tremmel, Sylvester (). „Computergeschichte: Zuse Z3 "im Test"”. c't magazin. Heise Verlag. Arhivat din original la . Accesat în . Über die I/O-Einheit kann man die Z3 als reine Rechenmaschine einsetzen, Operationen nimmt sie dann in der praktischen – wenn auch gewöhnungsbedürftigen – umgekehrten polnischen Notation entgegen. Werte im Speicher ablegen (oder von dort laden) kann man so allerdings nicht. 
  19. ^ en Burks, Arthur Walter; Warren, Don W.; Wright, Jesse B. (). „An Analysis of a Logical Machine Using Parenthesis-Free Notation”. Mathematical Tables and Other Aids to Computation. 8 (46): 53–57. doi:10.2307/2001990. JSTOR 2001990. 
  20. ^ a b en Hamblin, Charles Leonard (mai 1957). An Addressless Coding Scheme based on Mathematical Notation (Typescript). New South Wales University of Technology. 
  21. ^ a b en Hamblin, Charles Leonard (iunie 1957). „An addressless coding scheme based on mathematical notation”. Proceedings of the First Australian Conference on Computing and Data Processing. Salisbury, South Australia: Weapons Research Establishment. 
  22. ^ en Hamblin, Charles Leonard (). „Computer Languages”. The Australian Journal of Science (20?): 135–139; 
  23. ^ en Hamblin, Charles Leonard (noiembrie 1985). „Computer Languages”. The Australian Computer Journal (Reprint). 17 (4): 195–198. 
  24. ^ a b en Hamblin, Charles Leonard (). GEORGE IA and II: A semi-translation programming scheme for DEUCE: Programming and Operation Manual (PDF). School of Humanities, University of New South Wales, Kensington, New South Wales. Arhivat din original (PDF) la . Accesat în . 
  25. ^ en McBurney, Peter (). „Charles L. Hamblin: Computer Pioneer”. Arhivat din original la . [...] Hamblin soon became aware of the problems of (a) computing mathematical formulae containing brackets, and (b) the memory overhead in having dealing with memory stores each of which had its own name. One solution to the first problem was Jan Łukasiewicz's Polish notation, which enables a writer of mathematical notation to instruct a reader the order in which to execute the operations (e.g. addition, multiplication, etc) without using brackets. Polish notation achieves this by having an operator (+, ×, etc) precede the operands to which it applies, e.g., +ab, instead of the usual, a+b. Hamblin, with his training in formal logic, knew of Lukasiewicz's work. [...] 
  26. ^ en McBurney, Peter (). „Charles L. Hamblin and his work”. Arhivat din original la . 
  27. ^ a b c en Osborne, Thomas E. (). „Tom Osborne's Story in His Own Words”. Steve Leibson. Arhivat din original la . Accesat în . [...] I changed the architecture to use RPN (Reverse Polish Notation), which is the ideal notation for programming environment in which coding efficiency is critical. In the beginning, that change was not well received... [...] 
  28. ^ en Peterson, Kristina (). „Wall Street's Cult Calculator Turns 30”. Wall Street Journal. Arhivat din originalNecesită abonament cu plată la . Accesat în . 
  29. ^ en Kasprzyk, Dennis Michael; Drury, Colin G.; Bialas, Wayne F. (). „Human behaviour and performance in calculator use with Algebraic and Reverse Polish Notation”. Ergonomics. Department of Industrial Engineering, State University of New York at Buffalo, Amherst, New York, USA: Taylor & Francis. 22 (9): 1011–1019. doi:10.1080/00140137908924675. 
  30. ^ a b en Agate, Seb J.; Drury, Colin G. (martie 1980). „Electronic calculators: which notation is the better?”. Applied Ergonomics. Department of Industrial Engineering, University at Buffalo, State University of New York, USA: IPC Business Press. 11 (1): 2–6. doi:10.1016/0003-6870(80)90114-3. PMID 15676368. 0003-6870/80/01 0002-05. Arhivat din original la . Accesat în . In terms of practical choice between calculators, it would appear that RPN is faster and more accurate overall but particularly for more complex problems.  (5 pages)
  31. ^ en Hoffman, Errol; Ma, Patrick; See, Jason; Yong, Chee Kee; Brand, Jason; Poulton, Matthew (). „Calculator logic: when and why is RPN superior to algebraic?”. Applied Ergonomics. 25 (5): 327–333. doi:10.1016/0003-6870(94)90048-5. 
  32. ^ en Adobe Systems Incorporated (). „Preface by Charles Geschke”. PostScript Language Tutorial and CookbookNecesită înregistrare gratuită (ed. 27th printing, August 1998, 1st). Addison Wesley Publishing Company. ISBN 0-201-10179-3. 9-780201-101799. 
  33. ^ en PostScript Language Reference Manual (PDF) (ed. 1st printing, 3rd). Addison-Wesley Publishing Company. februarie 1999. ISBN 0-201-37922-8. Arhivat din original (PDF) la . Accesat în . 
  34. ^ de Born, Günter (decembrie 2000). „Kapitel 1. LOTUS 1-2-3-Format (WKS/WK1)”. Dateiformate – Eine Referenz – Tabellenkalkulation, Text, Grafik, Multimedia, Sound und Internet (PDF). Bonn, Germany: Galileo Computing. ISBN 3-934358-83-7. Arhivat din original (PDF) la . Accesat în . 
  35. ^ de Born, Günter (decembrie 2000). „Kapitel 2. LOTUS 1-2-3-Format (WK3)”. Dateiformate – Eine Referenz – Tabellenkalkulation, Text, Grafik, Multimedia, Sound und Internet (PDF). Galileo Computing. ISBN 3-934358-83-7. Arhivat din original (PDF) la . Accesat în . 
  36. ^ de Feichtinger, Herwig (). Arbeitsbuch Mikrocomputer (ed. 2). Munich, Germany: Franzis-Verlag GmbH. pp. 427–428. ISBN 3-7723-8022-0. 
  37. ^ de Wostrack, Gustav (ianuarie 1989). RPNL. Eine FORTH ähnliche Sprache mit strukturunterstützenden Sprachkonstrukten. Wolf-Detlef Luther, Gens. ISBN 978-3-88707022-9. 
  38. ^ de „Rechenhilfe für Ingenieure”. Alumni-Magazin der Technischen Universität Berlin. Vol. 2 nr. 3. Technische Universität Berlin. decembrie 2000. Arhivat din original la . 
  39. ^ de „An einem 12. Mai”. Deutsches Historisches Museum. Arhivat din original la . 
  40. ^ en Rojas, Raúl (). „Konrad Zuse's Legacy: The Architecture of the Z1 and Z3” (PDF). IEEE Annals of the History of Computing. 19 (2): 5–16 [7–8]. doi:10.1109/85.586067. Arhivat din original (PDF) la . Accesat în .  (12 pages)
  41. ^ en Blaauw, Gerrit Anne; Brooks, Jr., Frederick Phillips (). Computer architecture: Concepts and evolution. Boston, Massachusetts, USA: Addison-Wesley Longman Publishing Co., Inc. 
  42. ^ en LaForest, Charles Eric (aprilie 2007). „2.1 Lukasiewicz and the First Generation: 2.1.2 Germany: Konrad Zuse (1910–1995); 2.2 The First Generation of Stack Computers: 2.2.1 Zuse Z4”. Second-Generation Stack Computer Architecture (PDF) (thesis). Waterloo, Canada: University of Waterloo. pp. 8, 11. Arhivat din original (PDF) la . Accesat în .  (178 pages)
  43. ^ en Beard, Bob (). „The KDF9 Computer — 30 Years On” (PDF). Resurrection - The Bulletin of the Computer Conservation Society. Nr. 18. Computer Conservation Society (CCS). pp. 7–15. ISSN 0958-7403. Arhivat din original (PDF) la . Accesat în . [...] The KDF9 is remarkable because it is the believed to be the first zero-address instruction format computer to have been announced (in 1960). It was first delivered at about the same time (early 1963) as the other famous zero-address computer, the Burroughs B5000 in America. Like many modern pocket calculators, a zero-address machine allows the use of Reverse Polish arithmetic; this offers certain advantages to compiler writers. [...]  [2]
  44. ^ en Shirriff, Ken. „Reversing Sinclair's amazing 1974 calculator hack – half the ROM of the HP-35”. Arhivat din original la . Accesat în . 
  45. ^ en Sharwood, Simon (). „Google chap reverse engineers Sinclair Scientific Calculator”. The Register. Arhivat din original la . Accesat în . 
  46. ^ en Elektronika B3-21 page on RSkey.org
  47. ^ en „Elektronika MK-61/52 and 152/161: small tech review (En) - Кон-Тики”. arbinada.com. Arhivat din original la . Accesat în . 
  48. ^ en Elektronika MK-161 page on RSkey.org
  49. ^ en Dietrich, Johannes W. (). „TRURL RPN Engine”. doi:10.5281/zenodo.3257689. Accesat în . 

Vezi și

Legături externe

Portal icon Portal Matematică

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!