Prefix notation (Polish notation)
Prefix notation, or Polish notation, places operators before their operands. It is unambiguous without parentheses and is used in logic, programming (e.g., Lisp), calculators, and expression parsing.
Overview
Prefix notation, commonly called Polish notation, is a way to write mathematical expressions and logical formulas in which each operator appears before its operands. In contrast to ordinary infix notation (a + b), prefix notation writes the operator first and then the arguments, removing the need for many grouping symbols. For a general introduction see mathematical notation and for examples of written equations see equations.
Characteristics
Prefix notation is unambiguous when the arity (number of operands) of each operator is known, so a reader or parser can recover the structure of an expression by scanning from left to right. Typical properties include:
- Operators precede operands: an n-ary function f applied to x and y is written f x y.
- No parentheses are required for fully specified operators, because the order and grouping are determined by operator arities.
- It admits simple parsing algorithms based on stacks or recursive descent.
- It generalizes to logical connectives and higher-order operators; see formulae for related contexts.
History
Polish notation was introduced in the early 20th century by the logician Jan Łukasiewicz to simplify the notation of propositional logic. Łukasiewicz's work dates to around 1920; his goal was to eliminate parentheses and make logical expressions easier to analyze and formalize. More detail about the creator and his work can be found at Jan Łukasiewicz and historical notes refer to the period around 1920.
Uses and examples
Prefix notation appears in several applied contexts. It is used in some programmable calculators and user interfaces, and it influenced early computer languages and interpreters. For instance, certain CASIO calculators and similar devices support entering expressions in prefix form (CASIO). Functional programming languages and languages shaped by lambda calculus use prefix forms extensively; the Lisp family is a prominent example (Lisp and related languages).
Simple examples
Common arithmetic examples illustrate how prefix form eliminates parentheses. Written in prefix form:
- + 1 2 corresponds to 1 + 2.
- * + 1 2 3 corresponds to (1 + 2) * 3 because the + takes the next two operands, leaving 3 for the multiplication.
- A nested example: - * 4 + 2 3 5 is parsed as ((4 * (2 + 3)) - 5).
To evaluate a prefix expression, one typically reads from left to right, building the parse tree by applying operators to the subsequent operands according to their arity, or by using a stack-based algorithm that reverses the order if more convenient.
Notable distinctions and facts
Prefix notation is closely related to postfix or Reverse Polish Notation (RPN); both remove many parentheses but place the operator on opposite sides of its operands. A key practical requirement for both forms is knowledge of each operator's arity: without it, expressions may be ambiguous. Prefix notation remains important in theoretical logic, compiler design, and the implementation of expression evaluators where unambiguous, parenthesis-free representations are advantageous.
Further reading and implementations are discussed in introductory materials and documentation: see notation overview, example equations, and language references such as Lisp or vendor pages like calculator manuals for practical usage.
Examples
The addition of the numbers 21 and 43 is represented in the prefix notation as follows:
+ 21 43
The statement "P → Q" is written in Polish notation as follows:
Cpq
In the usual infix notation, the following term requires several parentheses:
(4 + 9) : (17 + 2)
With the prefix notation, on the other hand, none:
: + 4 9 + 17 2
Analogously, the statement
(P → (Q → R)) → ((P → Q) → (P → R))
for the shorter
CCpCqrCCpqCpr
Application
Besides the function notation in mathematics, where in many cases the function name precedes its arguments (e. g., "sin 30" or "lg 10"), and a niche position in logic, where Polish notation is still used by some authors today, this notation is currently most prominent in computer science. Thus, most command line interpreters use Polish notation (e.g., "dir *.doc" or "ls -a /").
In analogy to mathematical usage, in most programming languages mathematical functions or generally function calls are written in Polish notation, but then usually with additional parentheses (e.g. "sin(30)" or "exp(log(10))"). Programming languages with Polish notation are APL, Assembler, Tcl and Lisp. The latter (like its dialects, e.g. Scheme) is counted among the applications of Polish notation because of its proximity to lambda calculus and the associated function notation. The advantage of the absence of parentheses is lost in Lisp, however, firstly because operators cannot be clearly distinguished from operands in the context there (variables, functions as operands) and secondly because the significance of an operator (i.e. the number of its operands) is not unique. The solution chosen in Lisp, to put an opening parenthesis before the operator and a closing parenthesis after its last operands, is called the "Cambridge variant of Polish notation".
The Polish notation (and even more the reverse Polish notation, see below) is well suited to be evaluated in a simple way by machines. Especially in the early days of electronic data processing, this notation was therefore often created or used as an intermediate product of compilers and interpreters, in order to simplify the further processing of an input available in a more user-friendly notation for the computer system.
Related articles
Author
AlegsaOnline.com Prefix notation (Polish notation) Leandro Alegsa
URL: https://en.alegsaonline.com/art/78706