Reverse Polish notation
Reverse Polish notation
Main page
2318269

Reverse Polish notation

logo
Community Hub0 subscribers
Read side by side
Reverse Polish notation
View on Wikipedia
from Wikipedia
"Operational stack" redirects here. For the English Channel lorry parking procedure, see Operation Stack.

Video: Keys pressed for calculating eight times six on a HP-32SII (employing RPN) from 1991

Reverse Polish notation (RPN), also known as reverse Łukasiewicz notation, Polish postfix notation or simply postfix notation, is a mathematical notation in which operators follow their operands, in contrast to the more common infix notation (in which operators are placed between operands), as well as prefix notation (in which operators precede their operands). The notation does not need any parentheses as long as each operator has a fixed number of operands.

The term postfix notation describes the general scheme in mathematics and computer sciences, whereas the term reverse Polish notation typically refers specifically to the method used to enter calculations into hardware or software calculators, which often have additional side effects and implications depending on the actual implementation involving a stack. The description "Polish" refers to the nationality of logician Jan Łukasiewicz,[1][2] who invented Polish notation in 1924.[3][4][5][6]

The first computer to use postfix notation, though it long remained essentially unknown outside of Germany, was Konrad Zuse's Z3 in 1941[7][8] as well as his Z4 in 1945. The reverse Polish scheme was again proposed in 1954 by Arthur Burks, Don Warren, and Jesse Wright[9] and was independently reinvented by Friedrich L. Bauer and Edsger W. Dijkstra in the early 1960s to reduce computer memory access and use the stack to evaluate expressions. The algorithms and notation for this scheme were extended by the philosopher and computer scientist Charles L. Hamblin in the mid-1950s.[10][11][12][13][14][15][excessive citations]

During the 1970s and 1980s, Hewlett-Packard used RPN in all of their desktop and hand-held calculators, and has continued to use it in some models into the 2020s.[16][17] In computer science, reverse Polish notation is used in stack-oriented programming languages such as Forth, dc, Factor, STOIC, PostScript, RPL, and Joy.

Explanation

[edit]

In reverse Polish notation, the operators follow their operands. For example, to add 3 and 4 together, the expression is 3 4 + rather than 3 + 4. The conventional notation expression 3 − 4 + 5 becomes 3 (enter) 4 − 5 + in reverse Polish notation: 4 is first subtracted from 3, then 5 is added to it.

The concept of a stack, a last-in/first-out construct, is integral to the left-to-right evaluation of RPN. In the example 3 4 −, first the 3 is put onto the stack, then the 4; the 4 is now on top and the 3 below it. The subtraction operator removes the top two items from the stack, performs 3 − 4, and puts the result of −1 onto the stack.

Common language in this context refers to items being pushed onto the stack when added and popped or removed from the stack when taken off.

The advantage of reverse Polish notation is that it removes the need for order of operations and parentheses that are required by infix notation and can be evaluated linearly, left-to-right. For example, the infix expression (3 + 4) × (5 + 6) becomes 3 4 + 5 6 + × in reverse Polish notation.

Practical implications

[edit]

Reverse Polish notation has been compared to how one had to work through problems with a slide rule.[18]

In comparison, testing of reverse Polish notation with algebraic notation, reverse Polish has been found to lead to faster calculations, for two reasons. The first reason is that reverse Polish calculators do not need expressions to be parenthesized, so fewer operations need to be entered to perform typical calculations. Additionally, users of reverse Polish calculators made fewer mistakes than for other types of calculators.[19][20] Later research clarified that the increased speed from reverse Polish notation may be attributed to the smaller number of keystrokes needed to enter this notation, rather than to a smaller cognitive load on its users.[21] However, anecdotal evidence suggests that reverse Polish notation is more difficult for users who previously learned algebraic notation.[20]

Converting from infix notation

[edit]

Edsger W. Dijkstra invented the shunting-yard algorithm to convert infix expressions to postfix expressions (reverse Polish notation), so named because its operation resembles that of a railroad shunting yard.

There are other ways of producing postfix expressions from infix expressions. Most operator-precedence parsers can be modified to produce postfix expressions; in particular, once an abstract syntax tree has been constructed, the corresponding postfix expression is given by a simple post-order traversal of that tree.

Implementations

[edit]

Hardware calculators

[edit]

Early history

[edit]

The first computer implementing a form of reverse Polish notation (but without the name and also without a stack), was Konrad Zuse's Z3, which he started to construct in 1938 and demonstrated publicly on 12 May 1941.[22][23][24][25] In dialog mode, it allowed operators to enter two operands followed by the desired operation.[z3 1] It was destroyed on 21 December 1943 in a bombing raid.[23] With Zuse's help a first replica was built in 1961.[23] The 1945 Z4 also added a 2-level stack.[31][32]

Other early computers to implement architectures enabling reverse Polish notation were the English Electric Company's KDF9 machine, which was announced in 1960 and commercially available in 1963,[33] and the Burroughs B5000, announced in 1961 and also delivered in 1963:

The KDF9 designers drew ideas from Hamblin's GEORGE (General Order Generator),[10][11][13][34][35][32] a high-level programming language written for a DEUCE computer installed at The New South Wales University of Technology, Kensington, Australia, in 1957.[10][11][13][33]

One of the designers of the B5000, Robert S. Barton, later wrote that he developed reverse Polish notation independently of Hamblin sometime in 1958 after reading a 1954 textbook on symbolic logic by Irving Copi,[36][37][38] where he found a reference to Polish notation,[38] which made him read the works of Jan Łukasiewicz as well,[38] and before he was aware of Hamblin's work.

Friden introduced reverse Polish notation to the desktop calculator market with the EC-130, designed by Robert "Bob" Appleby Ragen,[39] supporting a four-level stack[5] in June 1963.[40] The successor EC-132 added a square root function in April 1965.[41] Around 1966, the Monroe Epic calculator supported an unnamed input scheme resembling RPN as well.[5]

Hewlett-Packard

[edit]
Main article: HP calculators
A promotional Hewlett-Packard "No Equals" hat from the 1980s – both a boast and a reference to RPN

Hewlett-Packard engineers designed the 9100A Desktop Calculator in 1968 with reverse Polish notation[16] with only three stack levels with working registers X ("keyboard"), Y ("accumulate") and visible storage register Z ("temporary"),[42][43] a reverse Polish notation variant later referred to as three-level RPN.[44] This calculator popularized reverse Polish notation among the scientific and engineering communities. The HP-35, the world's first handheld scientific calculator,[16] introduced the classical four-level RPN with its specific ruleset of the so-called operational (memory) stack[45][nb 1] (later also called automatic memory stack[46][47][nb 1]) in 1972.[48] In this scheme, the Enter ↑ key duplicates values into Y under certain conditions (automatic stack lift with temporary stack lift disable), and the top register T ("top") gets duplicated on drops (top copy on pop aka top stack level repetition) in order to ease some calculations and to save keystrokes.[47] HP used reverse Polish notation 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.

Later calculators with LCDs in the early 1980s, such as the HP-10C, HP-11C, HP-15C, HP-16C, and the financial HP-12C calculator also used reverse Polish notation. In 1988, Hewlett-Packard introduced a business calculator, the HP-19B, without reverse Polish notation, but its 1990 successor, the HP-19BII, gave users the option of using algebraic or reverse Polish notation again.

In 1986,[49][50] HP introduced RPL, an object-oriented successor to reverse Polish notation. It deviates from classical reverse Polish notation by using a dynamic stack only limited by the amount of available memory (instead of three or four fixed levels) and which could hold all kinds of data objects (including symbols, strings, lists, matrices, graphics, programs, etc.) instead of just numbers. The system would display an error message when running out of memory instead of just dropping values off the stack on overflow as with fixed-sized stacks.[51] It also changed the behaviour of the stack to no longer duplicate the top register on drops (since in an unlimited stack there is no longer a top register) and the behaviour of the Enter ↑ key so that it no longer duplicated values into Y, which had shown to sometimes cause confusion among users not familiar with the specific properties of the automatic memory stack. From 1990 to 2003, HP manufactured the HP-48 series of graphing RPL calculators, followed by the HP-49 series between 1999 and 2008. The last RPL calculator was named HP 50g, introduced in 2006 and discontinued in 2015. However, there are several community efforts like newRPL or DB48X to recreate RPL on modern calculators.

As of 2011, Hewlett-Packard was offering the calculator models 12C, 12C Platinum, 17bII+, 20b, 30b, 33s, 35s, 48gII (RPL) and 50g (RPL) which support reverse Polish notation.[52]

While calculators emulating classical models continued to support classical reverse Polish notation, new reverse Polish notation models feature a variant of reverse Polish notation, where the Enter ↑ key behaves as in RPL. This latter variant is sometimes known as entry RPN.[53]

In 2013, the HP Prime introduced a 128-level form of entry RPN called advanced RPN. In contrast to RPL with its dynamic stack, it just drops values off the stack on overflow like other fixed-sized stacks do.[51] However, like RPL, it does not emulate the behaviour of a classical operational RPN stack to duplicate the top register on drops.

In late 2017, the list of active models supporting reverse Polish notation included only the 12C, 12C Platinum, 17bii+, 35s, and Prime. By July 2023, only the 12C, 12C Platinum, the HP 15C Collector's Edition, and the Prime remain active models supporting RPN.

See also: HP-related community-developed calculators

Sinclair Radionics

[edit]

In Britain, Clive Sinclair's Sinclair Scientific (1974) and Scientific Programmable (1975) models used reverse Polish notation.[54][55]

Commodore

[edit]

In 1974, Commodore produced the Minuteman *6 (MM6) without an Enter ↑ key and the Minuteman *6X (MM6X) with an Enter ↑ key, both implementing a form of two-level RPN. The SR4921 RPN came with a variant of four-level RPN with stack levels named X, Y, Z, and W (rather than T) and an Ent key (for "entry"). In contrast to Hewlett-Packard's reverse Polish notation implementation, W filled with 0 instead of its contents being duplicated on stack drops.[56]

Prinztronic

[edit]

Prinz and Prinztronic were own-brand trade names of the British Dixons photographic and electronic goods stores retail chain, later rebranded as Currys Digital stores, and became part of DSG International. A variety of calculator models was sold in the 1970s under the Prinztronic brand, all made for them by other companies.

Among these was the PROGRAM[57] Programmable Scientific Calculator which featured reverse Polish notation.

Heathkit

[edit]

The Aircraft Navigation Computer Heathkit OC-1401/OCW-1401 used five-level RPN in 1978.

Soviet Union / Semico

[edit]

Soviet programmable calculators (MK-52, MK-61, B3-34 and earlier B3-21[58] models) used reverse Polish notation for both automatic mode and programming. Modern Russian calculators MK-161[59] and MK-152,[60] designed and manufactured in Novosibirsk since 2007 and offered by Semico,[61] are backwards compatible with them. Their extended architecture is also based on reverse Polish notation.

Others

[edit]
  • A seven-level stack had been implemented in the MITS 7400C scientific desktop calculator in 1972[62][63][64]
  • National Semiconductor 4615 and 4640
  • Novus 650 Mathbox, 3500 Sliderule, 4510 Mathematician, 4515 Mathematician PRO/RG, 4520 Scientist and 4525 Scientist PR
  • Some APF calculators like the Mark 55 (1976)[65]
  • SwissMicros (originally firming as RPN-Calc) calculators including the DM-10CC (2012), DM-11CC (2012), DM-12CC (2012), DM-15CC (2012), DM-16CC (2012), DM10 (2013), DM11 (2013), DM12 (2013), DM15 (2013), DM16 (2013), DM10L Collector's Edition (2020), DM11L (2016), DM12L (2016), DM15L (2015), DM16L (2015), DM41 (2015), DM41L (2015), DM41X (2020), DM42 (2017) and DM32 (2023).
  • The Tektronix 7854 Digital Oscilloscope (1980) included calculator functionality implemented using RPN, where operations could be applied to entire waveforms (arrays).Rousseau, Tom; Cox, Bill (August 1980). "Digital Waveform Processing in a High-Performance 7000-Series Oscilloscope" (PDF). TekScope. Vol. 12, no. 3. Beaverton, Oregon, US: Tektronix, Inc. Retrieved 2026-06-07.

Community-developed hardware-based calculators

[edit]
See also: Hewlett-Packard RPN calculators

An eight-level stack was suggested by John A. Ball in 1978.[5]

The community-developed calculators WP 34S (2011), WP 31S (2014) and WP 34C (2015), which are based on the HP 20b/HP 30b hardware platform, support classical Hewlett-Packard-style reverse Polish notation supporting automatic stack lift behaviour of the Enter ↑ key and top register copies on pops, but switchable between a four- and an eight-level operational stack.

In addition to the optional support for an eight-level stack, the newer SwissMicros DM42-based WP 43S as well as the WP 43C (2019) / C43 (2022) / C47 (2023) derivatives support data types for stack objects (real numbers, infinite integers, finite integers, complex numbers, strings, matrices, dates and times). The latter three variants can also be switched between classical and entry RPN behaviour of the Enter ↑ key, a feature often requested by the community.[66] They also support a rarely seen significant figures mode, which had already been available as a compile-time option for the WP 34S and WP 31S.[67][68]

Since 2021, the HP-42S simulator Free42 version 3 can be enabled to support a dynamic RPN stack only limited by the amount of available memory instead of the classical 4-level stack. This feature was incorporated as a selectable function into the DM42 since firmware DMCP-3.21 / DM42-3.18.[69][70]

Software calculators

[edit]

Software calculators:

Programming languages

[edit]

Existing implementations using reverse Polish notation include:

See also

[edit]

Notes

[edit]

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Reverse Polish notation

View on Grokipedia
from Grokipedia
Reverse Polish notation (RPN), also known as postfix notation, is a mathematical notation system in which every operator follows its operands, allowing expressions to be written unambiguously without parentheses or operator precedence rules. For instance, the infix expression 3+4×53 + 4 \times 5 becomes 3 4 5 × + in RPN, evaluated from left to right using a stack where operands are pushed and operators pop the required number of values, apply the operation, and push the result back.[1] RPN originated as the reverse of Polish notation, a prefix system developed by Polish logician Jan Łukasiewicz around 1924 to represent logical statements without parentheses, facilitating mechanical analysis and truth-table computation.[2] The postfix variant was first proposed in 1954 by Arthur W. Burks, Don W. Warren, and Jesse B. Wright for designing a relay-based logical machine that processes parenthesis-free formulas using a stack-like evaluator to compute truth values efficiently. It was independently reinvented in 1960 by Friedrich L. Bauer and Klaus Samelson, who described its use in sequential formula translation for early compilers, leveraging a pushdown store (stack) to handle expression evaluation during program assembly.[3] In computing, RPN enables straightforward parsing and evaluation of expressions, forming the basis for algorithms like the shunting-yard algorithm used in many compilers to convert infix to postfix form.[3] It powers stack-based virtual machines, such as the Java Virtual Machine's bytecode execution model, where instructions mimic RPN operations for arithmetic and control flow. Notably, Hewlett-Packard adopted RPN in its pioneering calculators starting with the 9100A desktop model in 1968 and the handheld HP-35 in 1972, allowing efficient entry of complex calculations with fewer keystrokes and no parentheses.[4][5] RPN also underpins languages like Forth, where code is structured as postfix sequences for real-time embedded systems. Its advantages include reduced computational overhead in expression trees and unambiguous serialization, making it valuable in symbolic computation, circuit design, and query optimization in databases.[1]

Fundamentals

Definition and Syntax

Reverse Polish notation (RPN), also known as postfix notation, is a mathematical notation system in which operators are placed after their corresponding operands, thereby eliminating the need for parentheses to denote operator precedence in unambiguous expressions.[6][1] This approach contrasts with traditional infix notation, where operators appear between operands (e.g., as in standard arithmetic writing), and prefix notation (also called Polish notation), where operators precede their operands.[6][7] The syntax of RPN consists of a linear sequence of tokens processed from left to right, where each token is either an operand—such as a number or variable—or an operator.[1][8] Operands are introduced first in the sequence, immediately followed by the unary or binary operator that applies to them, ensuring that the structure inherently defines the order of operations without additional delimiters.[6][9] Binary operators require exactly two preceding operands, while unary operators act on one, maintaining a postfix arrangement that supports stack-based evaluation, though the mechanics of evaluation are separate from the notation's definition.[1][7] Formally, an RPN expression is represented as a one-dimensional array or string of tokens, where the entire expression resolves to a single value through sequential application of operators to available operands.[6][8] This token-based format allows for unambiguous parsing in computational contexts, distinguishing RPN from infix by its operand-operator ordering and from prefix by its reversed positioning of operators relative to operands.[1][9]

Basic Examples

To illustrate the syntax of Reverse Polish Notation (RPN), consider simple arithmetic expressions where operands precede operators, and evaluation proceeds from left to right using a stack data structure. In RPN, numbers are pushed onto the stack, and operators pop the required operands, perform the operation, and push the result back. This avoids the need for parentheses in basic cases.[10] A fundamental example is the addition of two numbers: the expression 3 4 + evaluates to 7. The stack simulation proceeds as follows:
  • Push 3: stack = [3]
  • Push 4: stack = [3, 4]
  • Apply +: pop 4 and 3, compute 3 + 4 = 7, push 7: stack = [7]
The final stack value is 7.[10] For multiplication followed by addition, such as 2 3 * 5 +, which equals 11, the steps are:
  • Push 2: stack = [2]
  • Push 3: stack = [2, 3]
  • Apply *: pop 3 and 2, compute 2 × 3 = 6, push 6: stack = [6]
  • Push 5: stack = [6, 5]
  • Apply +: pop 5 and 6, compute 6 + 5 = 11, push 11: stack = [11]
This demonstrates how RPN handles operator precedence implicitly through stack order.[11] Subtraction requires attention to operand order, as the top of the stack (right operand, first popped) is subtracted from the preceding operand (second popped): 5 3 - yields 2 (5 - 3). Stack steps:
  • Push 5: stack = [5]
  • Push 3: stack = [5, 3]
  • Apply -: pop top (3), pop next (5), compute 5 - 3 = 2, push 2: stack = [2][12]
Similarly, for division, 10 4 / results in 2.5:
  • Push 10: stack = [10]
  • Push 4: stack = [10, 4]
  • Apply /: pop top (4), pop next (10), compute 10 ÷ 4 = 2.5, push 2.5: stack = [2.5][12]
Exponentiation, denoted by ^, follows binary convention with the base as the first operand: 2 3 ^ equals 8.
  • Push 2: stack = [2]
  • Push 3: stack = [2, 3]
  • Apply ^: pop top (3), pop next (2), compute 2³ = 8, push 8: stack = [8][11]
RPN also accommodates unary operators, which pop a single operand. For the square root of 5, denoted 5 √, the result is approximately 2.236:
  • Push 5: stack = [5]
  • Apply √: pop 5, compute √5 ≈ 2.236, push 2.236: stack = [2.236][13]

Historical Development

Origins in Polish Notation

Polish notation, also known as prefix notation, was developed by the Polish philosopher and logician Jan Łukasiewicz in the early 1920s as a method to represent logical and mathematical expressions without the need for parentheses, thereby eliminating ambiguity in operator precedence.[14] Łukasiewicz first introduced this notation in 1924, drawing inspiration from the way mathematicians denote functions by placing the function symbol before its arguments, such as f(x).[14] In this system, operators precede their operands, allowing expressions to be written linearly and unambiguously, for instance, representing the implication $ p \rightarrow q $ as $ \text{C}pq $, where C stands for the connective of implication.[14] The primary motivation behind Polish notation was to simplify the notation of propositional logic, where traditional infix expressions often required extensive parentheses to resolve ambiguities, such as in chained implications like $ p \rightarrow q \rightarrow r $.[14] By prefixing operators, Łukasiewicz aimed to enhance clarity and brevity, reducing the symbol count significantly—for example, a complex formula might use 23 symbols in Polish notation compared to 43 in fully parenthesized infix form.[14] Early applications focused on philosophy and mathematics, particularly in Łukasiewicz's work on the propositional calculus and the semantics of implication, where the notation facilitated precise analysis of logical structures without visual clutter.[14] This approach was particularly useful in his studies of many-valued logics and the history of Aristotelian syllogistics, influencing subsequent developments in formal logic. The postfix variant of this notation, known as reverse Polish notation (RPN), was first proposed in 1954 by Arthur W. Burks, Don W. Warren, and Jesse B. Wright in their analysis of a relay-based logical machine that used stack-like evaluation for parenthesis-free formulas.[15] It was independently described in 1960 by Friedrich L. Bauer and Klaus Samelson for sequential formula translation in early compilers, utilizing a pushdown store.[3] Further contributions came in the mid-1950s from Australian philosopher and computer scientist Charles L. Hamblin, who extended the scheme by proposing the reversal for addressless coding compatible with stack-based architectures, where operands are pushed onto a stack before the operator pops and processes them, enabling efficient, parenthesis-free computation without recursive parsing.[16] In his 1957 presentation at the W.R.E. Conference on Computing, titled "An Addressless Coding Scheme based on Mathematical Notation," Hamblin outlined this postfix variant as an adaptation of Łukasiewicz's prefix system, demonstrating its utility in programming languages like GEORGE, which he developed that same year for the DEUCE computer.[16] This reversal preserved the ambiguity-free nature of Polish notation while aligning it with the sequential processing capabilities of stack-oriented machines, laying the theoretical groundwork for its later computational adoption.[16]

Adoption in Computing and Calculators

Reverse Polish notation (RPN) found early adoption in computing through stack-based architectures that facilitated efficient expression evaluation without parentheses. In the late 1960s, Charles H. Moore developed the Forth programming language, which inherently employed RPN to leverage a data stack for operations, enabling compact code suitable for resource-constrained environments like early minicomputers and embedded systems.[17] This approach influenced subsequent stack-oriented languages and hardware designs, such as those in real-time control applications during the 1970s.[18] The integration of RPN into calculators marked a significant milestone in mid-20th-century hardware. The Friden EC-130, introduced in 1963, was the first fully electronic desktop calculator to implement RPN, using a cathode-ray tube display and a multi-register stack to process postfix expressions efficiently.[19] This innovation preceded broader commercialization, demonstrating RPN's practicality for scientific computations in an era of emerging solid-state technology. Hewlett-Packard's contributions accelerated RPN's spread in the late 1960s. The HP-9100A, released in 1968, became the first programmable scientific desktop calculator employing RPN, allowing users to store and execute complex routines via magnetic cards while supporting floating-point arithmetic.[4] Developed at HP's Loveland facility, it bridged calculators and computers, influencing the design of subsequent handheld models like the HP-35 in 1972. Regional developments further expanded RPN's use. In the Soviet Union, the Elektronika B3-19M, launched in 1977, represented the first domestically produced RPN calculator, followed by the programmable B3-21 that same year, both aimed at educational and engineering applications in state institutions.[20] By the mid-1970s, RPN had transitioned from niche scientific tools to programmable devices across manufacturers, solidifying its role in professional computing workflows due to streamlined evaluation processes.[21]

Conversion Techniques

Infix to RPN Algorithm

The Shunting-yard algorithm, developed by Edsger W. Dijkstra in 1961, provides a systematic method to convert infix mathematical expressions into reverse Polish notation (RPN) by parsing tokens from left to right while respecting operator precedence and associativity.[22] It employs an operator stack to temporarily hold operators and an output queue to build the RPN sequence, simulating the shunting operations in a railway yard where incoming operators are either added to the stack or rerouted to the output based on priority rules.[22] Operators are assigned numerical precedence levels, with higher values indicating tighter binding; for instance, multiplication (*) and division (/) typically have precedence 10, while addition (+) and subtraction (-) have precedence 9.[22] Operators of equal precedence are handled as left-associative, meaning they are popped from the stack to the output before pushing the new operator, ensuring evaluation from left to right (e.g., in "A + B + C", the first + is resolved before the second).[23] Parentheses override precedence by isolating subexpressions on the stack. The algorithm processes a tokenized infix expression as follows (pseudocode adapted for clarity):[23] 
Initialize an empty output queue and an empty operator stack.

While there are tokens to read in the input:
    Read the next token.
    If the token is an operand (e.g., variable or number), add it to the output queue.
    If the token is an operator o1:
        While the operator stack is not empty and the top operator o2 has precedence greater than or equal to o1 (and o1 is left-associative for equal precedence):
            Pop o2 from the operator stack and add it to the output queue.
        Push o1 onto the operator stack.
    If the token is a left parenthesis '(', push it onto the operator stack.
    If the token is a right parenthesis ')':
        While the top of the operator stack is not a left parenthesis:
            Pop the operator from the stack and add it to the output queue.
        Pop the left parenthesis from the operator stack (do not add to output).

After processing all tokens, while the operator stack is not empty:
    Pop operators from the stack and add them to the output queue.
This produces the RPN in the output queue, ready for evaluation.[23] Extensions to the basic algorithm accommodate functions and unary operators by treating them as special high-precedence operators. Functions like sin are tokenized as unary operators; when a function name is encountered, it is pushed onto the stack, and upon reaching the closing parenthesis of its argument, the function is popped to the output after the argument subexpression (e.g., the infix "sin(x)" converts to the RPN "x sin").[8] Unary operators, such as negation (-x), are distinguished from binary ones during tokenization (e.g., unary if following an operator or start of expression) and assigned higher precedence than binary operators, allowing them to bind tightly without popping intervening binary operators.[8] To illustrate, consider converting the infix expression "(A + B) * C" to RPN using the algorithm:[23]
  • Token '(': Push to stack. Stack: ['(']
  • Token 'A': Output: [A]
  • Token '+': Push to stack (stack top is '('). Stack: ['(', '+']
  • Token 'B': Output: [A, B]
  • Token ')': Pop until '(': Pop '+' to output, then pop '('. Output: [A, B, +]
  • Token '': Stack empty, so push ''. Stack: ['*']
  • Token 'C': Output: [A, B, +, C]
  • End of input: Pop '*' to output. Output: [A, B, +, C, *]
The resulting RPN is "A B + C *", which correctly groups the addition before multiplication due to precedence handling.[23]

Evaluation of RPN Expressions

The evaluation of Reverse Polish Notation (RPN) expressions relies on a stack-based algorithm that scans the expression from left to right, processing tokens sequentially to compute the result without requiring parentheses or operator precedence rules.[24] This method leverages the postfix structure of RPN, where operands appear before their operators, allowing straightforward operand accumulation and operation application.[25] The algorithm initializes an empty stack to hold operands and intermediate results. For each token in the RPN expression:
  • If the token is an operand (typically a number), push it onto the stack.
  • If the token is a binary operator (such as +, -, *, or /), pop the top two elements from the stack (let the second pop be the right operand and the first pop the left operand), apply the operation (e.g., left + right), and push the result back onto the stack.
  • If the token is a unary operator (such as negation, denoted as ~ or - in some contexts), pop the top element, apply the operation, and push the result back.[24][25][26]
Upon completing the scan, the stack should contain a single element representing the expression's value, which is then popped as the final result. If the stack is empty or contains multiple elements at the end, the expression is invalid.[24] Error conditions during evaluation include stack underflow, which occurs when an operator is encountered but fewer than the required number of operands (one for unary, two for binary) are available on the stack.[25] Type mismatches, such as applying an arithmetic operator to non-numeric tokens, can also arise, though valid RPN expressions typically consist solely of numbers and operators.[24] The following pseudocode illustrates the evaluator, assuming numeric operands and basic arithmetic operators for simplicity: 
function evaluateRPN(tokens):
    stack = empty stack
    for each token in tokens:
        if token is operand:
            push stack, convert(token to number)
        else if token is binary operator:
            if stack size < 2:
                raise underflow error
            right = pop stack
            left = pop stack
            result = apply(left, token, right)
            push stack, result
        else if token is unary operator:
            if stack size < 1:
                raise underflow error
            operand = pop stack
            result = apply(token, operand)
            push stack, result
    if stack size != 1:
        raise invalid expression error
    return pop stack
[24][25] Consider the RPN expression "3 4 2 + -", equivalent to the infix 3 - (4 + 2):
  • Push 3: stack = [3]
  • Push 4: stack = [3, 4]
  • Push 2: stack = [3, 4, 2]
  • Encounter +: pop 2 (right) and 4 (left), compute 4 + 2 = 6, push 6: stack = [3, 6]
  • Encounter -: pop 6 (right) and 3 (left), compute 3 - 6 = -3, push -3: stack = [-3]
  • End of expression: pop -3 as result.[25]

Advantages and Applications

Computational Benefits

Reverse Polish notation (RPN) eliminates the need for parentheses in mathematical expressions by placing operators after their operands, which significantly reduces parsing complexity in compilers and interpreters. This postfix structure ensures unambiguous expression representation, as each operator unambiguously applies to a fixed number of preceding operands without requiring precedence rules or grouping symbols during evaluation. Consequently, RPN avoids the operator precedence issues inherent in infix notation, allowing for straightforward, error-free processing by machines.[27] The evaluation of RPN expressions relies on a stack data structure, where operands are pushed onto the stack and operators trigger pop operations to compute results in constant time, O(1), per operation.[27] Overall, this stack-based approach achieves linear time complexity, O(n), for evaluating an expression of length n, as it requires only a single left-to-right pass without backtracking.[27] Such efficiency makes RPN particularly suitable for devices with limited memory, where stack operations minimize overhead and temporary storage needs.[28] In terms of resource utilization, RPN expressions are typically shorter than their infix equivalents due to the absence of parentheses and explicit precedence indicators, leading to space savings in storage and transmission. The space complexity remains O(n) via the stack, but the overall processing is faster for machines, as subexpressions are evaluated immediately upon encountering operators, optimizing computational throughput compared to multi-pass infix parsing.[27] While RPN offers substantial benefits for automated computation, it presents a steeper learning curve for human users accustomed to infix notation, potentially increasing initial cognitive load despite its machine-oriented simplicity.

Use Cases in Modern Systems

In modern virtual machines, Reverse Polish Notation (RPN) plays a key role through postfix-style bytecode in systems like the Java Virtual Machine (JVM). The JVM employs a stack-based operand stack for executing instructions, where operations such as addition or multiplication pop arguments from the stack and push results, mirroring postfix evaluation without requiring operator precedence handling. This structure, defined in the JVM specification, enables efficient interpretation and just-in-time compilation of Java programs by processing expressions linearly.[29] Spreadsheet software, including Microsoft Excel, internally represents formulas in RPN to facilitate storage and computation. User-entered infix expressions, such as =SUM(A1:A10), are tokenized and converted to a postfix sequence in binary file formats like XLSB, allowing stack-based evaluation that propagates results across dependent cells with minimal parsing overhead. This approach, part of Excel's parsed expression system, supports complex, interdependent calculations in large worksheets.[30] In AI and symbolic computation, RPN aids in linearizing expression trees for evaluation in environments like Wolfram Mathematica. Mathematica supports converting symbolic expressions to RPN for streamlined processing in algebraic manipulations, where the postfix form simplifies traversal and computation of nested operations.[31] Embedded systems leverage RPN for efficient sensor data processing on resource-limited microcontrollers, often via Forth implementations on Arduino platforms. Forth's stack-based RPN syntax enables real-time scripting in libraries like AmForth, where developers define words for fusing inputs from sensors like accelerometers or temperature probes, optimizing memory and execution speed in interrupt-driven applications. This notation's postfix simplicity reduces code size and avoids recursion overhead, making it ideal for battery-powered IoT devices.[32] In recent blockchain developments, RPN underpins smart contract scripting in platforms like Bitcoin, where the Script language uses postfix notation for transaction conditions and validations. Bitcoin Script processes operations on a stack, such as OP_ADD for combining values, enabling secure, non-Turing-complete execution of rules like multisignature approvals without loops.[33]

Implementations

Hardware Devices

The Hewlett-Packard HP-35, introduced in 1972, was the world's first pocket-sized scientific calculator to utilize Reverse Polish Notation (RPN), featuring transcendental functions and a four-level stack for efficient computation without parentheses.[5] This handheld device, powered by early integrated circuits and displaying results on red LED digits, marked a pivotal shift from bulky desktop models to portable tools for engineers and scientists.[34] Subsequent HP series built on this foundation, including the programmable HP-41C released in 1979, which offered expandability via synthetic programming and ROM modules while maintaining RPN entry for complex operations.[35] Other manufacturers adopted RPN in the 1970s to compete with HP's innovation, often licensing technology or reverse-engineering designs for cost efficiency. The Sinclair Scientific, launched in 1974 by the British firm Sinclair Radionics, was a compact, low-cost device using RPN with a limited scientific function set implemented via a reprogrammed four-function chip, displaying results in scientific notation on a single-line LED.[36] Commodore International's MM6X model (X variant), introduced in 1974, incorporated RPN for basic scientific calculations, featuring a slide-rule-like design with LED output and battery power.[37] In the Soviet Union, the Elektronika MK-52, produced from 1983 to 1992 by factories including Semico, was a programmable RPN calculator with 105 program steps, 15 registers, and vacuum fluorescent display, reflecting adaptations of Western RPN concepts for domestic engineering needs.[38] Niche devices from the 1970s further diversified RPN hardware, appealing to hobbyists and specialized users. Prinztronic, a British brand under Dixons, released the Programmable Scientific Calculator in 1975, an RPN model with 102 program steps and a three-level stack, manufactured in Taiwan for affordable scientific use.[39] Heathkit's OC-1401 Aircraft Navigation Computer, available as a 1978 kit or assembled unit, employed a five-level RPN stack tailored for aviation calculations, including great-circle navigation functions on an LED display.[37] Soviet adaptations extended to earlier models like the Elektronika B3-19 (1975), which used RPN for basic scientific tasks in a rugged, domestically produced form factor.[37] In the 2000s and 2010s, RPN persisted in professional-grade hardware, evolving from LED displays to advanced graphing capabilities. The HP 50g, introduced in 2006, supported RPN alongside algebraic modes in a graphing calculator with symbolic computation, infrared connectivity, and a high-resolution monochrome screen, serving as a staple for engineers until its discontinuation around 2015.[40] Community-driven projects revived RPN in modern contexts, such as FPGA-based implementations in the 2010s that emulated classic HP logic on reconfigurable hardware for customizable, open-source devices.[41] SwissMicros has produced modern RPN hardware since 2017, including the DM42, a programmable scientific calculator emulating the HP-42S with 34-digit precision, alphanumeric display, and USB connectivity, followed by the DM42n variant. As of November 2025, SwissMicros released the R47, a high-end RPN model with refined software for complex operations, matrix handling, and numerical integration.[42][43] As of 2025, HP continues RPN in select models like the HP 12C financial calculator and the HP Prime graphing calculator, which includes configurable RPN mode for stack-based entry, underscoring its enduring role in professional tools from early LED portables to contemporary graphing systems.[44] This progression highlights RPN's adaptability, from power-hungry 1970s LEDs requiring frequent battery changes to efficient LCDs and CAS-integrated graphers that maintain stack efficiency for complex workflows.[34]

Software and Programming Languages

Reverse Polish notation (RPN) has been natively incorporated into several programming languages, particularly those that are stack-oriented, where operands are pushed onto a stack and operators pop and apply operations in postfix order. Forth, developed by Charles H. Moore starting in the late 1960s and reaching maturity around 1970, is a quintessential example of an RPN-native language designed for embedded systems and real-time applications, emphasizing simplicity and extensibility through its stack-based execution model.[17] PostScript, introduced by Adobe Systems in 1984 as a page description language for desktop publishing, employs RPN for its operand-operator syntax, enabling concise representation of complex graphics and text layout instructions in printer drivers and rendering engines.[45] Stack-oriented languages from the late 1990s and 2000s further exemplify RPN semantics in purely functional paradigms. Joy, created by Manfred von Thun in 2001, is a concatenative programming language that relies on function composition and stack manipulation without variables, using RPN-style notation to build programs from quotations and combinators for tasks like symbolic computation.[46] These languages promote a postfix evaluation model that avoids recursion through iteration and stack operations, influencing modern esoteric and experimental programming designs. Software implementations of RPN appear prominently in calculator emulators and open-source tools. The HP Prime graphing calculator, released in 2013, includes an RPN mode alongside algebraic entry, with official PC and mobile emulators available for simulating its stack-based computations on desktops and Android devices.[47] Open-source alternatives, such as Free42—a programmable simulator of the HP-42S RPN calculator—provide high-precision arithmetic and programmability under the GNU General Public License, supporting ongoing development for scientific and engineering users since its inception in 2004. Another example is the C47 project, an open-source firmware and software suite for RPN-based scientific calculations, compatible with hardware like the SwissMicros DM42 and emphasizing community-driven enhancements in the 2020s.[48] In libraries and APIs, RPN support facilitates expression parsing and evaluation across languages. For JavaScript, the calculator-lib package offers functions to process RPN postfix expressions, converting and evaluating them using stack simulation for web-based mathematical tools and interactive applications.[49] Similarly, npm modules tagged with "rpn" enable tree-based analysis and execution of postfix notations, integrating seamlessly into Node.js environments for dynamic computations.[50] These implementations leverage RPN's unambiguous parsing to build robust evaluators, often referencing stack evaluation techniques for efficiency in runtime processing.

References

  1. Reverse Polish Notation -- from Wolfram MathWorld
  2. (PDF) Operators in the mind: Jan Lukasiewicz and Polish notation
  3. Sequential formula translation | Communications of the ACM
  4. HP Virtual Museum: 9100A desktop calculator, 1968
  5. Hewlett-Packard-35 handheld scientific calculator, 1972 - HP
  6. Stacks
  7. [PDF] Programming Abstractions
  8. [PDF] Expression Parsing & Visualizing Complex Mappings
  9. [PDF] The Compilation Process - Bryn Mawr College
  10. Postfix Expressions
  11. Reverse Polish Notation - Ada Computer Science
  12. Reverse Polish Notation - Marshall Leach
  13. [PDF] Lab 1: JavaRPNCalculator
  14. Łukasiewicz's Parenthesis-Free or Polish Notation
  15. Professor Charles Leonard Hamblin | IT History Society
  16. Forth programming language, history and evolution
  17. A Brief Introduction to Forth
  18. Friden EC-130 Electronic Calculator
  19. History of Calculators - Timeline - The X-Number Way
  20. The Evolution of RPN & Numeric Entry
  21. [PDF] CWI Scanprofile/PDF/300
  22. [PDF] 6.087 Practical Programming in C, Lecture 7 - MIT OpenCourseWare
  23. 4.9. Infix, Prefix and Postfix Expressions - Runestone Academy
  24. [PDF] Postfix Expression
  25. Expression parsing - Algorithms for Competitive Programming
  26. An exhaustive review for infix to postfix conversion with applications ...
  27. RPN - The Museum of HP Calculators
  28. Chapter 2. The Structure of the Java Virtual Machine
  29. [MS-XLSB]: Formulas - Microsoft Learn
  30. Converting Wolfram expression to Reverse Polish Notation (RPN)
  31. [PDF] Programming the Arduino in AmForth - Craig and Heather's Website
  32. Bitcoin Script: A Comprehensive Guide - Nervos Network
  33. HP-35 - The Museum of HP Calculators
  34. HP-41C - The Museum of HP Calculators
  35. Sinclair Scientific - Vintage Calculators
  36. Non-HP RPN Calculators
  37. Elektronika MK-52 - Calculator - The Centre for Computing History
  38. Prinztronic Program - Kees van der Sanden
  39. HP 50g Graphing Calculator
  40. An Open-source Scientific RPN Calculator - Hackaday
  41. HP Calculators - HP® Store
  42. [PDF] PostScript Language Reference, third edition - Adobe
  43. The Joy Programming Language - Frequently Asked Questions
  44. Downloads / Software - HP Calc
  45. The C47 calculator project
  46. felamaslen/calculator-lib: JavaScript libraries for processing ... - GitHub
  47. keywords:rpn - npm search
User Avatar
No comments yet.