Talk:Polish notation

This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Philosophy: Logic Low‑importance This article is within the scope of WikiProject Philosophy, a collaborative effort to improve the coverage of content related to philosophy on Wikipedia. If you would like to support the project, please visit the project page, where you can get more details on how you can help, and where you can join the general discussion about philosophy content on Wikipedia.PhilosophyWikipedia:WikiProject PhilosophyTemplate:WikiProject PhilosophyPhilosophy Low This article has been rated as Low-importance on the project's importance scale. Associated task forces: /  Logic Poland Low‑importance This article is within the scope of WikiProject Poland, a collaborative effort to improve the coverage of Poland on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.PolandWikipedia:WikiProject PolandTemplate:WikiProject PolandPoland Low This article has been rated as Low-importance on the project's importance scale. Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Low This article has been rated as Low-priority on the project's priority scale.

This stub is confusing. The notation for existential quantifier ($x)Gx does not seem to match the notation used in the artical.

Also, postfix notation redirects to Reverse Polish Notation

but Polish notation redirects to prefix notation.

I am tempted to fix this but the stub does not seem to say much on the general concept of prefix notation, and I don't think my maths is up to it. -- Chris Q 09:39, 20 Nov 2003 (UTC)

---

I've just added the "Query" title here. --Ludvikus 00:10, 13 October 2007 (UTC)Reply

The following part of the article removed, for clarifications.

This was a piece from article:

Polish notation is slightly easier to implement for computers, since the operation is encountered first, then the data to perform the operation comes later. However, people are much more familiar with infix notation.

This is a recent commment added by an anon into the article body:

The "easier" part is simply not true, and the argumentation is arbitrary.

Reverse Polish notation is, indeed, easier to implement, mainly because we are spared of the need for speculating about the order of operations. "Straight" Polish notation, however, is even a step-back from Infix notation with that respect, if we have to process it in natural (left-to-right) order.

The ordering of operands with respect to the operation is of imaginary significance and is completely irrelevant to the ease of implementation "for computers." Note that what comes after the operation is not necessarily "data," but may be another prefix expression.

The remarks are of merit IMO. So, what are real advantages of this notation? See Reverse Polish Notation how they are presented. Mikkalai 19:59, 18 Mar 2005 (UTC)

The point was that the original text was misleading, and was most probably due to confusion with RPN. PN is essentially isomorphic to RPN, and can be processed as such from right to left, thus leveraging the benefits of, but offering no advantages over, RPN.

--AoS 14:51, 21 Mar 2005 (UTC)

Polish notation is also used for Symbolic Logic, in fact it was invented for this purpose. This fact is ignored in the article. I intend to correct this latter when I can get to my own computer.

The note about this being used in Tcl is rather misleading. math in Tcl is in infix notation, but the language syntax is polish notation. Being this is a math article and when I first read the line, I became rather confused at what it meant. Could someone re-word this to read more clearly? I'm unsure how to word it myself. — Striker 22:48, 5 December 2005 (UTC)Reply

The "conventional" notation did not become so until the 1970s and 80s.

Does this mean to say that "The (common OR currently used) notation did not become conventional until the 1970s and 80s." or somesuch? - Centrx 22:59, 21 May 2006 (UTC)Reply

This page is written in a strange tone. I don't think it's good form to use the word "we" in an article (just as an example). Mo-Al 06:19, 25 June 2006 (UTC)Reply

I believe that the D operator is not the "nand" (sheffer stroke) operator but the "dubious" operator, which is a unary operator:

 Dx = ExNx

That is, when x is equivalent to not-x. This makes sense for the many-valued logics. (See C.I.Lewis and C.H. Langford's Symbolic Logic, (Dover Press, 1959), where they write about Łukasiewicz's 3-valued logic, Ł3.

-RR

A reference to an article by Łukasiewicz which introduces this system is needed. The notation is used in his works written in the 1920s, though I think that the standard is Elements of Mathematical Logic written 1929.

The article reads : "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 (assuming only binary operators are used in the expression). 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."

I'm not sure I understand it, can someone please add an explanation or confirm if it's a mistake?

It means that the number of things getting operated on is the number of operators + 1. For example, in "+ 1 2", "+" is the operator, and "1" and "2" are the operands. Mo-Al 02:40, 12 August 2006 (UTC)Reply

I'm reading this article, and towards the end it gives examples of association and distribution. For each it offers a more polish way of writing the statement of equivalence, using "=" as a binary operator.

I'm not sure that this use is appropriate, because it renders the equivalence confusing (and I have never seen this usage before... which does not mean it is incorrect, of course). Slightly Drunk 19:58, 4 January 2007 (UTC)Reply

• As a formal student of Philosophy and Logic in the United States, I have always known this subject by its former name.

Furthermore, Google shows us the former is far more common.

Accordingly, I'm recommending that the Title of this Article be changed to the former. Yours truly, --Ludvikus 00:08, 13 October 2007 (UTC)Reply

• 76,900 Google hits for "Prefix notation": [1]. --Ludvikus 00:14, 13 October 2007 (UTC)Reply
• 155,000 Google hits for "Polish notation": [2] --Ludvikus 00:17, 13 October 2007 (UTC)Reply

Should we also change all occurences of "prefix notation" (but not necessarily "prefix expression") to "Polish notation" in the article? I think we should either do that, or change the "or less frequently known as 'Prefix notation'" in the first sentence to "also known as 'Prefix notation'" (although the former is true, the article doesn't call it that "less frequently" than the alternative). --Spug (talk) 01:04, 12 December 2007 (UTC)Reply

I think the article should be called Prefix notation since it is country neutral. Accordingly, Reverse Polish Notation should be Postfix notation. 68.239.247.134 (talk) 05:24, 27 December 2009 (UTC)Reply

We should probably rewrite these sections; they overlap, and the former describes RPN as used in many stack-based programming languages, while the former says that PN is especially popular with those languages. --Spug (talk) 01:01, 12 December 2007 (UTC)Reply

The statement "In the previous example, the parentheses in the infix version were required, since moving them (5 − 6) + 7 or simply removing them 5 − 6 + 7 would change the meaning and result of the overall expression."

This is not true. Addition is associative - the parentheses don't matter! This would be true if addition and multiplication were mixed: 5 - (6 * 7) <> (5 - 6) * 7 Jesse1919 (talk) 03:37, 24 February 2008 (UTC)Reply

Yes, I also think that the example fails to illustrate the point. I will change it to one that mixes addition and multiplication. Borromean-ring (talk) 16:21, 4 May 2008 (UTC)Reply

Is Polish notation also referred to as "Polish logic," or does/can that term have a different meaning? The article Polish Logic, about an anthology, has a hatnote pointing to this article. -- ℜob C. alias ᴀʟᴀʀoʙ 18:39, 7 September 2008 (UTC)Reply

is there an algorithm to convert infix to prefix?—Preceding unsigned comment added by 72.68.199.83 (talk) 05:04, 3 March 2009 (UTC)Reply

Certainly. For example, construct the parse tree of the infix formula, and traverse it in preorder.—Emil J. 15:45, 18 October 2010 (UTC)Reply

See Shunting-yard algorithm. —Bkell (talk) 16:19, 18 October 2010 (UTC)Reply

The example ((15 / (7 - (1 + 1))) * 3) - (2 + (1 + 1)) uses an unnecessary number of parentheses, (15 / (7 - (1 + 1))) * 3 - (2 + 1 + 1) is, as far as I can tell, the normal equivalent example. If parentheses are used to avoid talking about precedence rules, perhaps this should be noted. Exaggerating the verbosity of infix notation makes the article look biased. Polish notation, especially reverse, is beautiful and clearly much more efficient, so no cheating is needed :). — Preceding unsigned comment added by 83.179.7.128 (talk) 10:41, 18 February 2012 (UTC)Reply

The simplified version can be simplified a bit further – the first pair of parens is not necessary, too: 15 / (7 - (1 + 1)) * 3 - (2 + 1 + 1) --CiaPan (talk) 07:03, 1 October 2018 (UTC)Reply

As I perceive the example, it is designed to avoid the necessity of applying any precedence rules, not expressed by parentheses. I think this gets especially important in connection with unary operators, where the precedence is not always absolutely clear. Possibly, the whole expression should be parenthesized, too, it would then contain seven (binary) operators (taking "-" as one of them) and seven parens-pairs. Personally, I would prefer to have the "-" as unary, writing ((((15 / (7+(-(1 + 1)))) * 3)) + (-(2 + (1 + 1)))), or more algebraically, introducing the multiplicative inverse as second unary operator, instead of the binary division:

${\displaystyle ((((15*((7+(-(1+1)))))^{-1}*3))+(-(2+(1+1)))).}$

In this context it is not about simplifying, but about machine-readability, and precedence rules are ugly to implement. Purgy (talk) 07:55, 1 October 2018 (UTC)Reply

The mention of Lisp doesn't seem relevant, because Lisp doesn't use parentheses-free Polish notation even when possible. The Lisp version of infix expression 5 • 2 ÷ 3 + 8 ÷ 7 is (+ (* 5 (/ 2 3)) (/ 8 7)), not + * / 2 3 5 / 8 7. This is in contrast to stack-based, prefix languages like Forth, which really use reverse Polish notation. 152.1.137.158 (talk) 15:06, 15 April 2016 (UTC)Reply

The current evaluation algorithm that process the expression from left to right is wrong. Counterexample:

infix notation: 2*(5*2 + 1)
prefix notation: * 2 + * 5 2 1
expected evaluation: 22
obtained evaluation: 12
actually evaluated expression: (2 + 5*2)*1

The "push-down automaton with shift reduce rules" is the correct algorithm for this situation. This algorithm needs a finite state control that keeps track of what is on top of stack, and typically, the current state also need to be pushed on the stack. I guess it may be implemented with a operand counter. It can be a rather complex algorithm, therefore removal may be a better solution. Proto8170 (talk) 07:57, 29 September 2018 (UTC)Reply

I'm not really into single stepping this "algorithm", and I also do not want to involve myself in checking your results. I'm also no expert in " shift reduce rules", but introduced the DPDA in the text. Your remarks about the finite control (keeping track, pushing states, operand counter) rather confuse me, and I object to this being a "complex algorithm". I would not object to removing this elaborate example, but in case it is right, some readers might lose a guide. Purgy (talk) 12:42, 1 October 2018 (UTC)Reply

@Proto8170: You're right, the algorithm is wrong. I did the calculation step-by-step on your example and confirmed your result.
Anyway, as far as I can see, the whole section #Explanation as well as #Prefix evaluation algorithm together with its subsection #Example possibly fulfill WP:NOR criteria for what should not appear in Wikipedia. It's a pity, the more I myself expanded some part of them – but they actually remain absolutely unsourced. --CiaPan (talk) 20:40, 1 October 2018 (UTC)Reply

With three editors talking about deletion of the example, I simply was bold. However, I object to removing #Explanation as well as the whole former #Prefix evaluation algorithm. It never would come to my mind to consider this as "original research", these are trivial consequences ("simple calculations") of the way the notation is set up, where there are certainly thousands of reliable sources in the wild. I'd assume there must be even a Knuth among them. Purgy (talk) 07:04, 2 October 2018 (UTC)Reply

An editor has identified a potential problem with the redirect Noitaton hsilop and has thus listed it for discussion. This discussion will occur at Wikipedia:Redirects for discussion/Log/2022 September 7#Noitaton hsilop until a consensus is reached, and readers of this page are welcome to contribute to the discussion. –LaundryPizza03 (dc̄) 02:59, 7 September 2022 (UTC)Reply

No love for APL? 2A01:CB0C:CD:D800:D890:8BF2:2502:B9F0 (talk) 07:54, 16 September 2022 (UTC)Reply

An editor has identified a potential problem with the redirect Noitaton Hsilop and has thus listed it for discussion. This discussion will occur at Wikipedia:Redirects for discussion/Log/2022 September 16#Noitaton Hsilop until a consensus is reached, and readers of this page are welcome to contribute to the discussion. Steel1943 (talk) 22:04, 16 September 2022 (UTC)Reply