Reverse Polish notation (or just
RPN) by analogy with the related
Polish notationPolish 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...
, a prefix notation introduced in 1920 by the
PolishPoland , officially the Republic of Poland , is a country in Central Europe . Poland is bordered by Germany to the west; the Czech Republic and Slovakia to the south; Ukraine, Belarus and Lithuania to the east; and the Baltic Sea and Kaliningrad Oblast, a Russian exclave, to the north...
mathematician Jan Łukasiewicz, is a mathematical notation wherein every
operatorIn mathematics, an operator is a type of function. Often, an "operator" is a function which acts on functions to produce other functions ; or it may be a generalization of such a function, as in linear algebra, where some of the terminology reflects the origin of the subject in operations on the...
follows all of its
operandAn operand is a quantity on which an operation is performed. The following arithmetic expression shows an example of operators and operands:...
s. It is also known as
Postfix notation and is parenthesis-free as long as operator
aritiesIn 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 number of domains in the corresponding Cartesian product. The term springs from such words as unary, binary, ternary,...
are fixed.
The Reverse Polish scheme was proposed in 1954 by Burks, Warren, and Wright and was independently reinvented by F.
Reverse Polish notation (or just
RPN) by analogy with the related
Polish notationPolish 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...
, a prefix notation introduced in 1920 by the
PolishPoland , officially the Republic of Poland , is a country in Central Europe . Poland is bordered by Germany to the west; the Czech Republic and Slovakia to the south; Ukraine, Belarus and Lithuania to the east; and the Baltic Sea and Kaliningrad Oblast, a Russian exclave, to the north...
mathematician Jan Łukasiewicz, is a mathematical notation wherein every
operatorIn mathematics, an operator is a type of function. Often, an "operator" is a function which acts on functions to produce other functions ; or it may be a generalization of such a function, as in linear algebra, where some of the terminology reflects the origin of the subject in operations on the...
follows all of its
operandAn operand is a quantity on which an operation is performed. The following arithmetic expression shows an example of operators and operands:...
s. It is also known as
Postfix notation and is parenthesis-free as long as operator
aritiesIn 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 number of domains in the corresponding Cartesian product. The term springs from such words as unary, binary, ternary,...
are fixed.
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
stackIn computer science, a stack is a last in, first out abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds to the top of the list, hiding any items already on the...
to evaluate expressions. The notation and algorithms for this scheme were extended by
AustraliaAustralia , officially the Commonwealth of Australia, is a country in the Southern Hemisphere comprising the continental mainland , the island of Tasmania, and numerous smaller islands in the Indian and Pacific Oceans...
n philosopher and computer scientist
Charles HamblinCharles Leonard Hamblin was an Australian philosopher, logician and a computer pioneer as well as a professor for 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 desktop calculators of the time – for example, the
HP-10C seriesThe HP-10C series calculators were introduced by Hewlett-Packard in 1981. Also known as the "Voyager" series, all are programmable and use Reverse Polish Notation...
and
Sinclair ScientificThe 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. It was launched in August...
calculators.
In
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
, postfix notation is often used in stack-based and concatenative programming languages. It is also common in dataflow and
pipelineIn 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
factorialIn 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
operatorIn mathematics, an operator is a type of function. Often, an "operator" is a function which acts on functions to produce other functions ; or it may be a generalization of such a function, as in linear algebra, where some of the terminology reflects the origin of the subject in operations on the...
s follow their operands; for instance, to add three and four, 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 of course reduces to "3 20 -".
Interpreters of Reverse Polish notation are often
stackIn computer science, a stack is a last in, first out abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds to the top of the list, hiding any items already on the...
-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. Stacks, and therefore RPN, have the advantage of being easy to implement and very fast.
Note that, despite the name, reverse Polish notation is not exactly the reverse of Polish notation, as the operands of non-commutative operations are still written in the conventional order (e.g. "/ 6 3" in Polish notation corresponds to "6 3 /" in reverse Polish, both evaluating to 2, whereas "3 6 /" would evaluate to 0.5). Numbers are also written with the digits in the conventional order.
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. Some claim this results in fewer operator errors when performing complex calculations.
- 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 calculate, unlike algebraic calculators.
- 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
In mathematics and computer programming, an expression or string of symbols is intended to represent a numerical value; a properly-formed expression may be evaluated in an unambiguous way. But in practice, an expression with multiple terms and operators may be written with parentheses, in...
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.
- The machine state is always a stack of values awaiting operation; it is impossible to enter an operator onto the stack. This makes use conceptually easy compared to more complex entry methods.
- Educationally, RPN calculators have the advantage that the user must understand the expression being calculated: it is not possible to simply copy the expression from paper into the machine and read off the answer without understanding. One must calculate from the middle of the expression, which is only meaningful if the user understands what they are doing.
- Reverse Polish notation also reflects the way calculations are done on pen and paper. One first writes the numbers down and then performs the calculation. Thus the concept is easy to teach.
- The widespread use of electronic calculators using infix
Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on . It is not as simple to parse by computers as prefix notation or postfix notation Infix notation is the common arithmetic and logical formula notation,...
in educational systems can make RPN impractical at times, not conforming to standard teaching methods. The fact that RPN has no use for parentheses means it is faster and easier to calculate expressions, particularly the more complex ones, than with an infix calculator, owing to fewer keystrokes and greater visibility of intermediate results. It is also easy for a computer to convert infix notationInfix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on . It is not as simple to parse by computers as prefix notation or postfix notation Infix notation is the common arithmetic and logical formula notation,...
to postfix, most notably via Dijkstra's shunting-yard algorithm – see converting from infix notation below.
- Users must know the size of the stack, since practical implementations of RPN use different sizes for the stack. For example, the 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 numberfrom blue area)|-||-||-||-| style="background:#cedff2;" | |-|style="background:#cedff2;" | |-|style="background:#cedff2;" | |-|style="background:#cedff2;" | |-||-||-||-| |-|}...
instead of approximately 0.5 as a real numberIn mathematics, the real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339..., where the digits continue in some way; or, the real...
.
- When writing RPN on paper (something which even some users of RPN may not do) adjacent numbers need a separator between them. Using a space is not good practice because it requires clear handwriting to prevent confusion. For example, 12 34 + could look like 123 4 + but in a monospace font it is quite clear, while something like 12, 34 + is straightforward. The comma becomes a virtual Space key.
- RPN is very easy to write and makes practical sense when it is adopted. The "learning" process to adopt RPN in writing usually comes later than adopting RPN on a calculator so that one may communicate more easily with non-RPN users.
The postfix algorithm
The algorithm for evaluating any postfix expression is fairly straightforward:
- While there are input tokens left
- Read the next token from input.
- If the token is a value
- Otherwise, the token is an operator.
- It is known a priori that the operator takes n arguments.
- If there are fewer than n values on the stack
- (Error) The user has not input sufficient values in the expression.
- Else, Pop the top n values from the stack.
- Evaluate the operator, with the values as arguments.
- Push the returned results, if any, back onto the stack.
- If there is only one value in the stack
- That value is the result of the calculation.
- If there are more values in the stack
- (Error) The user input has too many values.
Example
The infix expression "5 + ((1 + 2) * 4) − 3" can be written down like this in RPN:
- 5 1 2 + 4 * + 3 −
The expression is evaluated left-to-right, with the inputs interpreted as shown in the following table (the
Stack is the list of values the algorithm is "keeping track of" after the
Operation given in the middle column has taken place):
| Input |
Operation |
Stack |
Comment |
| 5 |
Push operand |
5 |
| 1 |
Push operand |
5, 1 |
| 2 |
Push operand |
5, 1, 2 |
| + |
Add |
5, 3 |
Pop two values (1, 2) and push result (3) |
| 4 |
Push operand |
5, 3, 4 |
| * |
Multiply |
5, 12 |
Pop two values (3, 4) and push result (12) |
| + |
Add |
17 |
Pop two values (5, 12) and push result (17) |
| 3 |
Push operand |
17, 3 |
| − |
Subtract |
14 |
Pop two values (17, 3) and push result (14) |
When a computation is finished, its result remains as the top (and only) value in the stack; in this case, 14.
The above example could be rewritten by following the "chain calculation" method described by HP for their series of RPN calculators:
As was demonstrated in the Algebraic mode, it is usually easier (fewer keystrokes) in working a problem like this to begin with the arithmetic operations inside the parentheses first.
- 1 2 + 4 * 5 + 3 −
Converting from infix notation
Edsger DijkstraEdsger 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 yardA 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 parserAn 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 treeIn 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 certain programming language. Each node of the tree denotes a construct occurring in the source code...
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
KDF9KDF9 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. BartonFor a former member of the Louisiana House of Representatives, see Robert E. "Bob" Barton.Robert S. "Bob" Barton was recognized as the chief architect of the Burroughs B5000 and other computers such as the B1700.He directed a research lab for Burroughs Corporation in La Jolla, California...
, later wrote that he developed RPN independently of Hamblin, sometime in 1958 while reading a textbook on symbolic logic, and before he was aware of Hamblin's work.
RPN in Hewlett-Packard
FridenFriden 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-PackardHewlett-Packard Company , commonly referred to as HP, is a technology corporation headquartered in Palo Alto, California, United States. HP has its United States offices at the former old Compaq Campus in unincorporated Harris County, Texas, Latin America offices in Miami-Dade County, Florida,...
(HP) engineers designed the
9100A Desktop CalculatorThe Hewlett-Packard 9100A is an early computer/calculator, 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-35The 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
calculatorA calculator is a device that is used for performing mathematical calculations. It differs from a computer by having a limited problem solving ability and an interface optimized for interactive calculation rather than programming...
, used RPN in 1972. HP used RPN on every handheld calculator it sold, whether scientific, financial, or programmable, until it introduced an adding machine-style calculator, the HP-10A. HP introduced an LCD-based line of calculators in the early 1980s that used RPN, such as the
HP-10CThe HP-10C series calculators were introduced by Hewlett-Packard in 1981. Also known as the "Voyager" series, all are programmable and use Reverse Polish Notation...
, 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 12-C 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 seriesThe 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
ARMThe ARM is a 32-bit reduced instruction set computer instruction set architecture developed by ARM Limited. It was known as the Advanced RISC Machine, and before that as the Acorn RISC Machine. The ARM architecture is the most widely used 32-bit ISA in terms of numbers produced...
CPU that emulates the Saturn CPU of the HP-48 series.
RPN in Soviet Union
SovietThe Union of Soviet Socialist Republics was a constitutionally socialist state that existed in Eurasia from 1922 to 1991. The name is a translation of the , tr. Soyuz Sovetskikh Sotsialisticheskikh Respublik, abbreviated СССР, SSSR. The common short name is Soviet Union, from , Sovetskiy Soyuz...
programmable calculators (
MK-52The 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-34Elektronika 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
RussiaRussia , officially known as both Russia and the Russian Federation , is a country in northern Eurasia . It is a semi-presidential republic, comprising 83 federal subjects...
n calculators MK-161 and MK-152, designed and manufactured in
NovosibirskNovosibirsk is Russia's third-largest city, after Moscow and Saint Petersburg, and the largest city of Siberia. 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 RPN implementations
Existing implementations using Reverse Polish notation include:
- Any 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 and PostScript, and also many Assembly languages ....
, such as:
- Forth
- Factor
Factor is a high-level 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 is a dynamically typed concatenative programming language created by John Warnock and Charles Geschke in 1982. PostScript is best known for its use as a page description language in the electronic and desktop publishing areas....
page description language
- Ambi
Ambi is a structured, imperative, stack-based, computer programming language designed and implemented by .-Overview:Ambi is a programming language generalised from Reverse Polish Notation arithmetic. Other languages such as Forth and RPL have similar roots and illustrious histories, but have...
- 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...
- RPN Scientific Calculator for Mac OS X
- RPN calculator for Microsoft Windows
- XCALC for Microsoft Windows
- Open Source RPN Calculator for Microsoft Windows
- RPN Alchemy Arbitrary Precision RPN Calculator for Microsoft Windows and Linux
- Microsoft PowerToy calculator for Microsoft Windows XP
- RPN calculator for cellular phones, in open source Java
- RPN calculator for Palm PDAs
Palm handhelds are Personal Digital Assistants which run the Palm OS. Palm devices have evolved from handhelds to smartphones which run Palm OS, WebOS and Windows Mobile This page describes the range of Palm devices, from the first generation of Palm machines known as the Pilot through to the...
- Mac OS X Calculator
- RPN calculator for Mac OS X and iPhone
- Some Hewlett-Packard
Hewlett-Packard Company , commonly referred to as HP, is a technology corporation headquartered in Palo Alto, California, United States. HP has its United States offices at the former old Compaq Campus in unincorporated Harris County, Texas, Latin America offices in Miami-Dade County, Florida,...
science/engineering and business/finance calculatorA calculator is a device that is used for performing mathematical calculations. It differs from a computer by having a limited problem solving ability and an interface optimized for interactive calculation rather than programming...
s
- Unix system
Unix is a 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 dcdc 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...
- MAcalc for the iPhone
The iPhone is an Internet and multimedia enabled smartphone designed and marketed by Apple Inc. Because its minimal hardware interface lacks a physical keyboard, the multi-touch screen renders a virtual keyboard when necessary...
- Interactive JavaScript
JavaScript is an object-oriented scripting language used to enable programmatic access to objects within both the client application and other applications. It is primarily used in the form of client-side JavaScript, implemented as an integrated component of the web browser, allowing the...
RPN calculator
- JavaScript RPN calculator with keyboard-based user interface, more like HP calculators
- Mouseless online RPN calculator
- Linux IpTables "Rope" programming language
- b:Ada Programming/Mathematical calculations (RPN calculator implemented in Ada
Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...
)
- Emacs lisp library package: calc
- Sinclair calculators
- Open source GTK+
GTK+ is a cross-platform widget toolkit for creating graphical user interfaces. It is one of the most popular toolkits for the X Window System, along with Qt....
based galculator
- Infix to Postfix Conversion / Postfix Evaluator / Postfix to Infix Conversion http://www.java2s.com/Code/JavaScript/Development/Postfix-Infix.htm
- Simple XUL RPN Calculator
- A programmable JavaScript RPN calculator
- A Custom Function for FileMaker Pro Advance
- RPNParser class in Ruby
Ruby is a dynamic, reflective, general purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was initially developed and designed by Yukihiro "Matz" Matsumoto...
- The RPN/RPL Implementations web page, also posted as a USENET FAQ
- HC - Open Source calculator - Open Source calculator for almost any system (precompiled versions exist for *NIX and Windows) which supports both infix and postfix (RPN) notation
A Postfix evaluator implemented in Python 2.6
import operator
OPERATORS = {
'+': operator.add,
'-': operator.sub,
'*': operator.mul,
'/': operator.truediv,
'^': operator.pow,
'%': operator.mod,
}
def evaluate_rpn(expression, stack):
try:
for token in expression.split:
try:
result = float(token)
except ValueError:
result = OPERATORS[token](stack.pop(-2), stack.pop)
stack.append(result)
except KeyError:
print "Invalid input", repr(token)
except IndexError:
print "The stack is too small to apply the operator", repr(token)
if __name__ "__main__":
print "RPN.py - Press Control-D to exit."
stack = []
try:
while True:
evaluate_rpn(raw_input('%s> ' % stack), stack)
except (KeyboardInterrupt, EOFError):
print
External links