Polish notation
From Free net encyclopedia
Polish notation, also known as prefix notation, is a form of notation for logic, arithmetic, and algebra. Its distinguishing feature is that it places operators, whose arity is assumed known, to the left of their operands. The result is a syntax lacking parentheses or other brackets, that can still be parsed without ambiguity. The Polish logician Jan Łukasiewicz invented this notation around 1920 in order to simplify sentential logic. While no longer much used in logic, it has since found a place in computer science.
Contents |
Arithmetic
We begin with a trivial arithmetical example. The expression:
+ 1 2
evaluates to Template:Plus 1 2.
Polish notation is not limited to only two values, nor to just addition. For example, this expression:
(× (+ 0 1) (+ 2 3))
evaluates to 5.
While the examples above use parentheses, one of the benefits of Polish notation is that, assuming the arity of each operator is known, parentheses are unnecessary: the order of operations is unique and easy to determine, provided that the expression is well-formed. For example, assuming × and + are binary, then this expression:
× + 0 1 + 2 3
can mean only this:
(× (+ 0 1) (+ 2 3))
Polish notation has seen wide application in Lisp s-expressions, where the brackets are required due to the arithmetic operators having variable arity. It has not seen much other use, but a variant called reverse Polish notation, or postfix notation, is used in many stack-based programming languages, and is the operating principle of certain calculators, notably from Hewlett-Packard.
Although obvious, it is important to note that the number of operands in an expression must equal the number of operators plus one, otherwise the statement makes no sense. This can be easy to overlook when dealing with longer, more complicated expressions with several operators, so care must be taken to double check that an expression makes sense when using Polish notation.
Order of Operations
Order of operations is defined within the structure of Polish notation and can be easily determined. One thing to keep in mind is that when executing an operation, the operation is applied TO the first operand BY the second operand. This is not an issue with operations that commute, but for non-communative operations like division or subtraction, this fact is crucial to the analysis of a statement. For example, the following statement:
/ 10 5
is read as "Divide 10 BY 5" or "Divide 5 inTO 10". Thus the solution is 2, not 1/2 as would be the result of an incorrect analysis.
Polish notation is especially popular with stack-based due to its innate ability to easily distinguish order of operations without the need for parentheses. To evaluate order of operations under polish notation, one does not even need to memorize an operational hierarchy, as with infix notation. Instead, one looks directly to the notation to discover which operator to evaluate first. Reading an expression from left to right, one first looks for an operator and proceeds to look for two operands. If another operator is found before two operands are found, then the old operator is placed aside until this new operator is resolved. This process iterates until an operator is resolved, which must happen eventually, as there must be one more operand than there are operators in a complete statement. Once resolved, the operator and the two operands are replaced with a new operand. Because one operator and two operands were removed and one operand was added, there was a net loss of one operator and one operand, meaning that there still exist more operators than operands by a factor of one, allowing the iterative process to complete once again. This the general theory behind using stacks in programming languages to evaluate a statement in Polish notation, although there are various algorithms that manipulate the process. Once analyzed, a statement in Polish notation becomes less intimidating to the human mind as it allows some separation from convention with added convenience. An example shows the ease with which a complex statement in Polish notation can be deciphered through order of operations:
- * / 15 - 7 + 1 1 3 + 2 + 1 1 =
- * / 15 - 7 2 3 + 2 + 1 1 =
- * / 15 5 3 + 2 + 1 1 =
- * 3 3 + 2 + 1 1 =
- 9 + 2 + 1 1 =
- 9 + 2 2 =
- 9 4 =
5
Application of Mathematical Laws
It is important to see that with Polish notation, basic mathematical laws still hold true but must be adopted to the notation. For example, under Polish notation, the law of Additive Communativity is expressed mathematically as:
+ A B = + B A
Similarly, under this notation, since parentheses are not necessary, the law of Additive Associativity involves the repositioning of operators to be expressed notationally as follows:
+ + A B C = + A + B C
Polish notation for logic
The table below shows the core of Jan Łukasiewicz's notation for sentential logic. The "conventional" notation did not become so until the 1970s and 80s.
| Concept | Conventional Notation | Polish Notation | |
|---|---|---|---|
| Negation | ¬φ | Nφ | |
| Conjunction | φ∧ψ | Kφψ | |
| Alternation | φ∨ψ | Aφψ | |
| Conditional | φ→ψ | Cφψ | |
| Biconditional | φ↔ψ | Eφψ | |
| Sheffer stroke | \psi </math> | Dφψ |
See also
ja:ポーランド記法 nl:Poolse notatie pl:Notacja polska pt:Notação Polonesa