Definition:Polish Notation/Reverse Polish Notation

Definition

For stack-based programming languages, reverse Polish language is a useful variant of Polish notation, because it naturally coincides with how the input is to be structured for the language.

As the name suggests, a string $\mathsf P$ is in reverse Polish language if and only if reversing it gives a string $\tilde {\mathsf P}$ in Polish notation.

Thus the reverse Polish language equivalents of these examples of Polish notation:

$\Box p q \ldots$

$\Box {\diamond} p {\diamond} q \ldots$

are:

$\ldots q p \Box$

$\ldots q {\diamond} p {\diamond} \Box$

Also see

• Unique Readability for Reverse Polish Notation

Historical Note

Polish notation, along with its variant reverse Polish notation, was developed by a group of Polish mathematicians, led by Jan Łukasiewicz who invented it in the $1920$s.

Sources

• 1955: John L. Kelley: General Topology ... (previous) ... (next): Chapter $0$: Subsets and Complements; Union and Intersection: Theorem $3 \ \text{(b)}$
• 1993: M. Ben-Ari: Mathematical Logic for Computer Science ... (previous) ... (next): Chapter $2$: Propositional Calculus: $\S 2.2$: Propositional formulas
• 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): Appendix $\text{A}.8$: Cartesian Product
• 2009: Kenneth Kunen: The Foundations of Mathematics ... (previous) ... (next): $\mathrm{II}.4$ Polish Notation
• 2012: M. Ben-Ari: Mathematical Logic for Computer Science (3rd ed.) ... (previous) ... (next): $\S 2.1.3$