# Polish notation

## Primary tabs

Synonym:
prefix notation, \L{}ukasiewicz notation, Lukasiewicz notation
Type of Math Object:
Definition
Major Section:
Reference

## Mathematics Subject Classification

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