Fork me on GitHub
Math for the people, by the people.

User login

Polish notation

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

Mathematics Subject Classification

68N17 no label found03B70 no label found

Comments

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.

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

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.

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

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.

Thank you very much, Igor, that fixed it.

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.

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.

Subscribe to Comments for "Polish notation"