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.