Reverse Polish notation
Overview
 
Reverse Polish notation (RPN) is a mathematical notation wherein every operator
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

 follows all of its operand
Operand
In mathematics, an operand is the object of a mathematical operation, a quantity on which an operation is performed.-Example :The following arithmetic expression shows an example of operators and operands:3 + 6 = 9\;...

s, in contrast to Polish notation
Polish notation
Polish notation, also known as prefix notation, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left of their operands. If the arity of the operators is fixed, the result is a syntax lacking parentheses or other brackets that...

, which puts the operator in the prefix position. It is also known as Postfix notation and is parenthesis-free as long as operator arities
Arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...

 are fixed. The description "Polish" refers to the nationality of logician Jan Łukasiewicz, who invented (prefix) Polish notation in the 1920s.

The Reverse Polish scheme was proposed in 1954 by Burks, Warren, and Wright and was independently reinvented by F.
Encyclopedia
Reverse Polish notation (RPN) is a mathematical notation wherein every operator
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

 follows all of its operand
Operand
In mathematics, an operand is the object of a mathematical operation, a quantity on which an operation is performed.-Example :The following arithmetic expression shows an example of operators and operands:3 + 6 = 9\;...

s, in contrast to Polish notation
Polish notation
Polish notation, also known as prefix notation, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators to the left of their operands. If the arity of the operators is fixed, the result is a syntax lacking parentheses or other brackets that...

, which puts the operator in the prefix position. It is also known as Postfix notation and is parenthesis-free as long as operator arities
Arity
In logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...

 are fixed. The description "Polish" refers to the nationality of logician Jan Łukasiewicz, who invented (prefix) Polish notation in the 1920s.

The Reverse Polish scheme was proposed in 1954 by Burks, Warren, and Wright and was independently reinvented by F. L. Bauer and E. W. Dijkstra in the early 1960s to reduce computer memory access and utilize the stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...

 to evaluate expressions. The algorithms and notation for this scheme were extended by Australia
Australia
Australia , officially the Commonwealth of Australia, is a country in the Southern Hemisphere comprising the mainland of the Australian continent, the island of Tasmania, and numerous smaller islands in the Indian and Pacific Oceans. It is the world's sixth-largest country by total area...

n philosopher and computer scientist Charles Hamblin
Charles Leonard Hamblin
Charles Leonard Hamblin was an Australian philosopher, logician, and computer pioneer, as well as a professor of philosophy at the Technical University of New South Wales in Sydney....

 in the mid-1950s.

During the 1970s and 1980s, RPN had some currency even among the general public, as it was widely used in handheld calculators of the time – for example, the HP-10C series
HP-10C series
The HP-10C series calculators were introduced by Hewlett-Packard in 1981. Also known as the "Voyager" series, all are programmable, use Reverse Polish Notation, and feature continuous memory...

 and Sinclair Scientific
Sinclair Scientific
The Sinclair Scientific calculator was a 12-function, pocket-sized calculator, selling for about $100 in the USA and around £45 in the UK.The Sinclair Scientific first appeared in a case derived from that of the Sinclair Cambridge, but it was not part of the same range. At the time it was launched,...

 calculators.

In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, postfix notation is often used in stack-based and concatenative programming languages. It is also common in dataflow and pipeline
Pipeline (software)
In software engineering, a pipeline consists of a chain of processing elements , arranged so that the output of each element is the input of the next. Usually some amount of buffering is provided between consecutive elements...

-based systems, including Unix pipelines.

Most of what follows is about binary operators. A unary operator for which the Reverse Polish notation is the general convention is the factorial
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...

.

Explanation

In Reverse Polish notation the operators
Operation (mathematics)
The general operation as explained on this page should not be confused with the more specific operators on vector spaces. For a notion in elementary mathematics, see arithmetic operation....

 follow their operands; for instance, to add 3 and 4, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" in conventional infix notation would be written "3 4 − 5 +" in RPN: first subtract 4 from 3, then add 5 to that. An advantage of RPN is that it obviates the need for parentheses that are required by infix. While "3 − 4 * 5" can also be written "3 − (4 * 5)", that means something quite different from "(3 − 4) * 5". In postfix, the former would be written "3 4 5 * −", which unambiguously means "3 (4 5 *) −" which reduces to "3 20 −"; the latter would be written "3 4 - 5 *", which unambiguously means "(3 4 -) 5 *".

Interpreters of Reverse Polish notation are often stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...

-based; that is, operands are pushed onto a stack, and when an operation is performed, its operands are popped from a stack and its result pushed back on. So the value of postfix expression is on the top of the stack. Stacks, and therefore RPN, have the advantage of being easy to implement and very fast.

Despite the name, reverse Polish notation is not exactly the reverse of Polish notation, for the operands of non-commutative operations are still written in the conventional order (e.g. "/ 6 3" in Polish notation and "6 3 /" in reverse Polish both evaluating to 2, whereas "3 6 /" in reverse Polish notation would evaluate to ½).

Practical implications


  • Calculations occur as soon as an operator is specified. Thus, expressions are not entered wholesale from right to left but calculated one piece at a time, most efficiently from the center outwards.
  • The automatic stack permits the automatic storage of intermediate results for use later: this key feature is what permits RPN calculators to easily evaluate expressions of arbitrary complexity: they do not have limits on the complexity of expression they can evaluate.
  • Brackets and parentheses are unnecessary: the user simply performs calculations in the order that is required, letting the automatic stack store intermediate results on the fly for later use. Likewise, there is no requirement for the precedence
    Order of operations
    In mathematics and computer programming, the order of operations is a rule used to clarify unambiguously which procedures should be performed first in a given mathematical expression....

     rules required in infix notation.
  • In RPN calculators, no equals key is required to force computation to occur.
  • RPN calculators do, however, require an enter key to separate two adjacent numeric operands.
  • Users must know the size of the stack, because practical implementations of RPN use different sizes for the stack. For example, the algebraic
    Algebraic
    Algebraic may refer to any subject within the algebra branch of mathematics and related branches like algebraic geometry and algebraic topology.Algebraic may also refer to:...

     expression , if performed with a stack size of 4 and executed from left to right, would exhaust the stack. The answer might be given as an erroneous imaginary number
    Imaginary number
    An imaginary number is any number whose square is a real number less than zero. When any real number is squared, the result is never negative, but the square of an imaginary number is always negative...

     instead of approximately 0.5 as a real number
    Real number
    In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

    .
  • When writing RPN on paper (something that some users of RPN may not do) adjacent numbers need a separator between them. Using a space requires clear handwriting to prevent confusion. For example, could look like while something like is straightforward.

Converting from infix notation

Edsger Dijkstra
Edsger Dijkstra
Edsger Wybe Dijkstra ; ) was a Dutch computer scientist. He received the 1972 Turing Award for fundamental contributions to developing programming languages, and was the Schlumberger Centennial Chair of Computer Sciences at The University of Texas at Austin from 1984 until 2000.Shortly before his...

 invented the Shunting-yard algorithm to convert infix expressions to postfix (RPN), so named because its operation resembles that of a railroad shunting yard
Classification yard
A classification yard or marshalling yard is a railroad yard found at some freight train stations, used to separate railroad cars on to one of several tracks. First the cars are taken to a track, sometimes called a lead or a drill...

.

There are other ways of producing postfix expressions from infix notation. Most Operator-precedence parser
Operator-precedence parser
An operator precedence parser is a bottom-up parser that interprets an operator-precedence grammar. For example, most calculators use operator precedence parsers to convert from the human-readable infix notation with order of operations format into an internally optimized computer-readable format...

s can be modified to produce postfix expressions; in particular, once an abstract syntax tree
Abstract syntax tree
In computer science, an abstract syntax tree , or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it...

 has been constructed, the corresponding postfix expression is given by a simple post-order traversal of that tree.

History of implementations

The first computers to implement architectures enabling RPN were the English Electric Company's KDF9
English Electric KDF9
KDF9 was an early British computer designed and built by English Electric, later English Electric Leo Marconi, EELM, later still incorporated into ICL. It first came into service in 1964 and was still in use in 1980 in at least one installation...

 machine, which was announced in 1960 and delivered (i.e. made available commercially) in 1963, and the American Burroughs B5000, announced in 1961 and also delivered in 1963. One of the designers of the B5000, Robert S. Barton
Robert (Bob) Barton
Robert Stanley "Bob" Barton was recognized as the chief architect of the Burroughs B5000 and other computers such as the B1700, and a co-inventor of dataflow. Barton's thinking has been broadly influential...

, later wrote that he developed RPN independently of Hamblin sometime in 1958 while reading a textbook by Kopi on symbolic logic and before he was aware of Hamblin's work.

Hewlett-Packard

Friden
Friden, Inc.
Friden Calculating Machine Company was an American manufacturer of typewriters and electronic calculators. It was founded by Carl Friden in San Leandro, California in 1934. Friden electromechanical calculators were robust and popular....

 introduced RPN to the desktop calculator market with the EC-130 in June 1963. Hewlett-Packard
Hewlett-Packard
Hewlett-Packard Company or HP is an American multinational information technology corporation headquartered in Palo Alto, California, USA that provides products, technologies, softwares, solutions and services to consumers, small- and medium-sized businesses and large enterprises, including...

 engineers designed the 9100A Desktop Calculator
Hewlett-Packard 9100A
The Hewlett-Packard 9100A is an early computer , first appearing in 1968. HP called it a desktop calculator because, as Bill Hewlett said, "If we had called it a computer, it would have been rejected by our customers' computer gurus because it didn't look like an IBM...

 in 1968 with RPN. This calculator popularized RPN among the scientific and engineering communities, even though early advertisements for the 9100A failed to mention RPN. The HP-35
HP-35
The HP-35 was Hewlett-Packard's first pocket calculator and the world's first scientific pocket calculator . Like some of HP's desktop calculators it used reverse Polish notation. Introduced at US$395, the HP-35 was available from 1972 to 1975.Market studies at the time had shown no market for...

, the world's first handheld scientific calculator
Calculator
An electronic calculator is a small, portable, usually inexpensive electronic device used to perform the basic operations of arithmetic. Modern calculators are more portable than most computers, though most PDAs are comparable in size to handheld calculators.The first solid-state electronic...

, used RPN in 1972. HP used RPN on every handheld calculator it sold, whether scientific, financial, or programmable, until it introduced the HP-10 adding machine calculator in 1977. By this time HP was the leading manufacturer of calculators for professionals, including engineers and accountants.

HP introduced an LCD-based line of calculators in the early 1980s that used RPN, such as the HP-10C
HP-10C series
The HP-10C series calculators were introduced by Hewlett-Packard in 1981. Also known as the "Voyager" series, all are programmable, use Reverse Polish Notation, and feature continuous memory...

, HP-11C, HP-15C, HP-16C, and the famous financial calculator, the HP-12C. When Hewlett-Packard introduced a later business calculator, the HP-19B, without RPN, feedback from financiers and others used to the 12C compelled them to release the HP-19BII, which gave users the option of using algebraic notation or RPN. From 1990 to 2003 HP manufactured the HP-48 series
HP-48 series
The HP-48 is a series of graphing calculators using Reverse Polish notation and the RPL programming language, produced by Hewlett-Packard from 1990 until 2003. The series include the HP-48S, HP-48SX, HP-48G, HP-48GX, and HP-48G+, the G models being expanded and improved versions of the S models...

 of graphing RPN calculators and in 2006 introduced the HP-50g with a 131x80 LCD and a 75 MHz ARM
ARM architecture
ARM is a 32-bit reduced instruction set computer instruction set architecture developed by ARM Holdings. It was named the Advanced RISC Machine, and before that, the Acorn RISC Machine. The ARM architecture is the most widely used 32-bit ISA in numbers produced...

 CPU that emulates the Saturn CPU of the HP-48 series.

As of 2011, Hewlett-Packard is producing the calculator models 12C, 12C Platinum, 17BII
HP-17B
Introduced on January 4, 1988, along with the HP-19B, HP-27S and the HP-28S. It was a simplified business model, like the 19B. There were two versions, the US one working in English only, and the international one with a choice of six languages. Code name: Trader....

, 20B (financial), 30B
HP 30b
HP 30b is a programmable financial calculator from HP which was released on 7th January 2010. HP 30b is an advanced version of the HP's prior model HP 20b...

 (business), 33S
HP 33s
The Hewlett-Packard Co. markets the hp 33s calculator. Main features:* RPN or traditional semi-algebraic , user selectable* Two-line LCD display...

, 35S
HP 35s
The HP 35s Scientific Calculator is, as of 2007, the latest in Hewlett-Packard's long line of non-graphing scientific and programmable calculators...

, 48GII and 50G (scientific) which support RPN notation.

Soviet Union

Soviet
Soviet Union
The Soviet Union , officially the Union of Soviet Socialist Republics , was a constitutionally socialist state that existed in Eurasia between 1922 and 1991....

 programmable calculators (MK-52
MK-52
The Elektronika MK-52 is RPN-programmable calculator which was manufactured in the Soviet Union during the years 1983 to 1992.The functionality of the MK-52 is identical to that of the MK-61, except the MK-52 has an internal non-volatile EEPROM memory module, for permanent data storage, diagnostic...

, MK-61, B3-34
Elektronika B3-34
Elektronika B3-34 was a very popular Soviet programmable calculator. It was released in 1980 and was sold for 85 rubles.B3-34 used Reverse Polish notation and had 98 bytes of instruction memory, 4 stack user registers and 14 addressable registers...

 and earlier B3-21 models) used RPN for both automatic mode and programming. Modern Russia
Russia
Russia or , officially known as both Russia and the Russian Federation , is a country in northern Eurasia. It is a federal semi-presidential republic, comprising 83 federal subjects...

n calculators MK-161 and MK-152, designed and manufactured in Novosibirsk
Novosibirsk
Novosibirsk is the third-largest city in Russia, after Moscow and Saint Petersburg, and the largest city of Siberia, with a population of 1,473,737 . It is the administrative center of Novosibirsk Oblast as well as of the Siberian Federal District...

 since 2007, are backward compatible with them. Their extended architecture is also based on Reverse Polish notation.

Current implementations

Existing implementations using Reverse Polish notation include:
  • Any stack-oriented programming language
    Stack-oriented programming language
    A stack-oriented programming language is one that relies on a stack machine model for passing parameters. Several programming languages fit this description, notably Forth, RPL, PostScript, and also many Assembly languages ....

    , such as:
    • Forth
    • Factor
      Factor (programming language)
      Factor is a stack-oriented programming language created by Slava Pestov. Factor is dynamically typed and has automatic memory management, as well as powerful metaprogramming features. The language has a single implementation featuring a self-hosted optimizing compiler and an interactive development...

    • PostScript
      PostScript
      PostScript is a dynamically typed concatenative programming language created by John Warnock and Charles Geschke in 1982. It is best known for its use as a page description language in the electronic and desktop publishing areas. Adobe PostScript 3 is also the worldwide printing and imaging...

       page description language
    • Befunge
      Befunge
      Befunge is a stack-based, reflective, esoteric programming language. It differs from conventional languages in that programs are arranged on a two-dimensional grid...

    • Joy
  • Orpie
    Orpie
    Orpie is a command-line reverse polish notation calculator written in OCaml by Paul Pelzl, a graduate student at the University of Michigan. It is open source and available for a wide variety of Unix-like operating systems.- External links :*...

  • Mouseless online RPN calculator
  • Mac OS X Calculator
  • Several Apple iPhone
    IPhone
    The iPhone is a line of Internet and multimedia-enabled smartphones marketed by Apple Inc. The first iPhone was unveiled by Steve Jobs, then CEO of Apple, on January 9, 2007, and released on June 29, 2007...

     applications
  • Several Android applications
  • Some Hewlett-Packard
    Hewlett-Packard
    Hewlett-Packard Company or HP is an American multinational information technology corporation headquartered in Palo Alto, California, USA that provides products, technologies, softwares, solutions and services to consumers, small- and medium-sized businesses and large enterprises, including...

     science/engineering and business/finance calculator
    Calculator
    An electronic calculator is a small, portable, usually inexpensive electronic device used to perform the basic operations of arithmetic. Modern calculators are more portable than most computers, though most PDAs are comparable in size to handheld calculators.The first solid-state electronic...

    s
  • Unix system
    Unix
    Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...

     calculator program dc
    Dc (Unix)
    dc is a cross-platform reverse-polish desk calculator which supports arbitrary-precision arithmetic. It is one of the oldest Unix utilities, predating even the invention of the C programming language; like other utilities of that vintage, it has a powerful set of features but an extremely terse...

  • Emacs lisp library package: calc
  • Xorg
    X.Org Server
    X.Org Server refers to the X server release packages stewarded by the X.Org Foundation,which is hosted by freedesktop.org, and grants...

     calculator (xcalc
    Xcalc
    xcalc is an on-screen calculator program for the X Window System. It can be used in algebraic mode or in reverse polish notation. Early versions also featured a slide rule mode, but this was removed for X11R4, which was released in 1989. The sliderule program for the BSD operating systems is based...

    )
  • F-Correlatives in MultiValue
    MultiValue
    MultiValue is a type of multidimensional database, typically considered synonymous with PICK, a database originally developed as the Pick operating system....

     dictionary items

See also

  • Calculator input methods
    Calculator input methods
    There are various ways in which a calculator might interpret key strokes.One can categorize calculators into two main types: 1) single-step or immediate execution calculators and 2) expression or formula calculators....

  • Factor (programming language)
    Factor (programming language)
    Factor is a stack-oriented programming language created by Slava Pestov. Factor is dynamically typed and has automatic memory management, as well as powerful metaprogramming features. The language has a single implementation featuring a self-hosted optimizing compiler and an interactive development...

  • Formula calculator
    Formula calculator
    A formula calculator is a software calculator that can perform a calculation in two steps:1. Enter the calculation by typing it in from the keyboard.2...

  • Forth (programming language)
  • HP calculators
    HP calculators
    HP calculators are various calculators manufactured by the Hewlett-Packard company over the years.- History :In the 1960s, Hewlett-Packard was becoming a diversified electronics company with product lines in electronic test equipment, scientific instrumentation, and medical electronics, and was...

  • Joy (programming language)
  • LIFO (computing)

  • Object–subject–verb
  • Orpie
    Orpie
    Orpie is a command-line reverse polish notation calculator written in OCaml by Paul Pelzl, a graduate student at the University of Michigan. It is open source and available for a wide variety of Unix-like operating systems.- External links :*...

    , an RPN calculator
  • PostScript
    PostScript
    PostScript is a dynamically typed concatenative programming language created by John Warnock and Charles Geschke in 1982. It is best known for its use as a page description language in the electronic and desktop publishing areas. Adobe PostScript 3 is also the worldwide printing and imaging...

  • Stack machine
    Stack machine
    A stack machine may be* A real or emulated computer that evaluates each sub-expression of a program statement via a pushdown data stack and uses a reverse Polish notation instruction set....

  • Subject–object–verb (SOV)


External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK