# Definition:Polish Notation

## Definition

**Polish notation** is a method of writing expressions without the need for parentheses.

The main method in writing an expression in **Polish notation** is to output an operator $\Box$, directly followed by the output of all its arguments $p, q, \ldots$, yielding:

- $\Box p q \ldots$

If we had another, operator $\diamond$ taking only one argument, then also:

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

is in **Polish notation**.

Note that for the applicability of **Polish notation**, it is vital to be able to efficiently distinguish an argument from an operator, or a sequence of arguments.

### Formal Definition

Let $\AA$ be an alphabet.

Let each $s \in \AA$ be assigned a natural number called its arity.

The formal grammar for Polish notation is given by the single bottom-up rule:

- If $s$ has arity $n$ and $\phi_1, \ldots, \phi_n$ are well-formed formulas, then:

- $s \phi_1 \cdots \phi_n$

- is also a well-formed formula.

Notably, in the case where $s$ has arity $0$, this is a vacuous truth, so any such $s$ constitutes a well-formed formula.

### Reverse Polish Notation

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$

This article is complete as far as it goes, but it could do with expansion.Could benefit from being defined in BNF or otherwise formally, as an exercise in formal languagesYou can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Expand}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

## 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.

## Also see

## Sources

- 1993: M. Ben-Ari:
*Mathematical Logic for Computer Science*... (previous) ... (next): Chapter $2$: Propositional Calculus: $\S 2.2$: Propositional formulas - 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$