## You are here

HomePolish notation

## Primary tabs

# Polish notation

Whereas operators are traditionally placed between operands, with parentheses used to override operator precedence, it is possible to place each operator to the left of its operands, thus eliminating ambiguity and the need for parentheses, and even the need for rules of operator precedence.

This is known as *Polish notation* (after the Polish mathematician Jan Łukasiewicz who came up with it), or *prefix notation*. Polish notation is a system of notating mathematical operations (whether arithmetic, logical, etc.) where the operators precede their operands and the ambiguities of operator precedence and the need for parentheses are altogether eliminated.

For example, $2+3\times 15$ probably means 47, but if the possibility exists that the author meant but neglected to put in parentheses, the expression could actually mean $(2+3)\times 15=75$. In Polish notation, we could define the basic arithmetic operators to all be binary, and write $+\times 2\quad 3\quad 15$ with the confidence that it will evaluate to 21 rather than 47.

Lisp is one computer programming language that uses Polish notation. In Łukasiewicz’s vision, parentheses are not necessary at all, certainly not for resolving operator precedence. Lisp, however, uses parentheses to specify arity by enclosing operands affected by a single operator in a “list,” and “the only hierarchy rule [in Lisp is] … that innermost lists are evaluated before the lists that enclose them.” (Chirlian, 1986) Thus, in the Lisp expression $(-21(+3\quad 5\ 8))$, the addition operator is ternary and the subtraction operator is binary.

Certain LaTeX packages, such as pstricks, also use Polish notation when used for plotting plane curves.

For stack-based programming languages like Adobe PostScript, reverse Polish notation (or postfix notation) – in which the operators are written after the operands – is often the norm. Note that it is quite common for authors to confuse Polish and reverse Polish, e.g., page 3 of Chirlian (1986) speaks of “reverse Polish or prefix notation.”

# References

- 1 P. Chirlian, Lisp, Cleveland: Weber Systems pp. 3, 29 - 34 (1986)

## Mathematics Subject Classification

68N17*no label found*03B70

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Attached Articles

## Corrections

missing word by Mathprof ✓

definition is not given by Mathprof ✓

Incorrect and confused by ratboy ✓

quotation marks by CWoo ✓

## Comments

## TeX problems

I know the name of the Polish mathematician is not showing up correctly. I don't know how to fix it. I am also aware that a lot of text is getting italicized that shouldn't be. My feeling is that once I correct the mathematician's name the italics problem will disappear.

## Re: TeX problems

> I know the name of the Polish mathematician is not showing

> up correctly. I don't know how to fix it. I am also aware

> that a lot of text is getting italicized that shouldn't be.

> My feeling is that once I correct the mathematician's name

> the italics problem will disappear.

You get the Polish "crossed L" use \L, as in "\L ukasiewicz" or "\L{}ukasiewicz".

## Polish notation

The claim that "it is possible to place all operators to the left of all the operands" seems dubious. Could you explain, please, how to build the parse trees for such expressions.

## Re: Polish notation

It is not generally possible to split a Polish expression

into two parts where all operations are in the left part

and all operands are in the right part. A simple example

(with extra parentheses for clarity, since normal priority

rules are ignored in an example in the entry) is

(2*3)+(4*5)

which translates to Polish notation as

+ * 2 3 * 4 5

What was probably meant is that each operation in a

Polish expression occurs before all of _its_ operands.

The translation of (2+3)*15 to + * 2 3 15 in the entry

is however quite wrong; + * 2 3 15 means (2*3)+15.

## Is there a theoretical advantage?

Is there a real grammatical difference between infix (standard), prefix (Polish) or postfix (reverse Polish)?

I mean this in the sense of Chomsky hierarchy, (push-down automatas etc.). I believe they all can be accepted by a PDA, though the infix seems more tricky. Also when parentheses are replaced with order of operation conventions, the length of an infix expression can be less than the equivalent pre/post-fix notation, though I'm sure that the reverse is also true in some instances.

## Re: Is there a theoretical advantage?

I plead the fifth on Chomsky hierarchies. As for comparative lengths, that calls for some pencil and paper scribbling. Give me a day to get back to you on that.

## Re: TeX problems

Thank you very much, Igor, that fixed it.

## Re: Polish notation

lars_h wrote: "The translation of (2+3)*15 to + * 2 3 15 in the entry

is however quite wrong; + * 2 3 15 means (2*3)+15."

Are you sure you're not thinking about reverse PN? Or maybe I am.

## Re: Polish notation

Yes, I'm quite sure I'm not thinking about RPN.

The rules are that a Polish notation expression

is one of the following:

1. a variable,

2. a constant,

3. a k-ary operation followed by k expressions.

(Formalists like me often like to regard case 2 merely

as the k=0 subcase of case 3, but never mind that now.)

+ and * are both binary operations. Thus, if one in

+ * 2 3 15 inserts parentheses around each

subexpression then the result is

+(*(2)(3))(15)

The first operand of + is the first complete

expression following it: * 2 3. Since that evaluates to 6,

the expression as a whole evaluates to 21.