Talk:Reverse Polish notation

From Wikipedia, the free encyclopedia

Contents

[edit] Old comments

I don't think the really long example showing how to convert infix notation to RPN really belongs. - Furrykef 15:12, 9 Sep 2004 (UTC)

I disagree. As I was reading about the RPN stack algorithm, I was wondering if the best (easiest) way to write an infix notation interpreter is to convert from infix to RPN notation. So I was quite happy to see that the description of the RPN stack algorithm was immediately followed by a description of an RPN-based infix notation interpreter. The description of the infix to RPN conversion algorithm and related example should say. --Zeno of Elea 6 July 2005 03:43 (UTC)
This example does not belong and it is confusing.
Examples are always a good idea--they show real-world stuff--but when I learned RPN, reading the H-P manual that came with my RPN calculator, it said to work from the inside out. So the example is not only wrong as it works from left-to-right, but it's overly complex and confusing and shows RPN in a bad light. It should be changed to reflect how easy (and natural) it is to work from the inside out:
1 Enter 2 +
4 *
5 +
3 -
The H-P manuals still say this: See: Chain Calculations on page 50 of this HP 32SII Owner's Manual
Here's another great HP example from a live web page, not a pdf.
The manual is filled with great examples.
Awaiting thoughts and comments.--TMH 22:00, 27 September 2006 (UTC)


Why is there always a space between the left bracket and letter, in the pre box? lysdexia 13:37, 5 Nov 2004 (UTC)

I added the step to handle function tokens in the infix->postfix algorithm. It was mentioned what to do when they are found on the stack, but with no mention of how/when they would be placed there. BryanMWoods 05:28, 14 September 2005 (UTC)

There's a contradiction. -- It was introduced before it was invented -- Which is right?

If you're referring to the intro paragraph, it indicates that PN was invented in the 1920s and RPN was invented in the 1950s. You're right that this probably could be phrased better. OTOH, I'm wondering what it means about "zero-address memory stores". TheIncredibleEdibleOompaLoompa 10:52, 30 October 2005 (UTC)

The algorithm (still) doesn't seem to handle functions properly. If an operator's left arguement is the result of a function call, the These must only be operators part of the last clause isn't true. If no one objects I'll add my fixes to the algorithm on the page. However, if I add my changes it may no longer strictly be Edsger Dijkstra's shunting yard algorithm. It might be. The "shunting" between the operand and operator stacks is still the core of the algorithm. Thoughts? -- BryanMWoods 07:27, 8 November 2005 (UTC)

yeah, sounds good!

[edit] Shunting Yard

Since the information about the shunting yard algorithm is mainly intended for developers who wish to convert statements in infix notation to RPN notation I think that it would be a good idea to provide an example of the algorithm in C, I would do it myself however I am not good enough at C to implement one effectively. Or a least provide a link to an implementation of it.

The majority of the code would be for the data structures. And if you have a data structures library, there isn't really any code to show. My (C++) implementation was just a direct transcription of the algorithm into STL data structures. I think the algorithmic description is all that's needed. -- BryanMWoods 19:23, 5 December 2005 (UTC)

[edit] New or additional Example

We need another example that uses operators that have order importance, like - and /. I'm trying to refresh myself on this and this example with only + and * is of no help.

[edit] Split shunting yard to separate article

It seems to me the the shunting yard algorithm is worthy of a separate article. The algorithm itself is not exclusivly tied to RPN as the same algorithm can be used to produce an abstract syntax tree. Further its presence here assumes that it's the only way to produce RPN from infix notation. --Salix alba (talk) 18:54, 13 August 2006 (UTC)

I agree with making it a separate page. DFH 18:58, 23 August 2006 (UTC)
Operator-precedence parser has another, different exposition of this algorithm. Split it off and refer to it on both pages. Tom Duff 19:36, 23 August 2006 (UTC)

I agree too. I have to admit that having that on the same RPN page vas *very* useful to me 'cause i didn't know this efficient way to convert from one notation to the other. Anyway, as long as it is clearly marked this possibility (not just in a link at the end of the page), i'm cool with making a separate page. Danilo Roascio 11:42, 13 September 2006 (UTC)

[edit] Vague Explination of algorithm

1) while there is an operator, o2, at the top of the stack, and either

           o1 is associative or left-associative and its precedence is less than or equal to that of o2, or


Which is correct? Perhaps rewording would make it more clear.

           o1 is (associative or left-associative) and its precedence is less than or equal to that of o2,
           or
           o1 is associative or (left-associative and its precedence is less than or equal to that of o2),
The former i think, left associativity just refers to the order in wich you have to do the operations to have associativity property verified. It has nothing to do with precedence. Danilo Roascio 11:42, 13 September 2006 (UTC)

[edit] RPN?

This article is about RPN, but the only algorithm I see is that of the shunting yard algorithm. I've added a formal description of the RPN evaluation algorithm; better check for any errors I may have dropped in.

And yes, I agree to split the shunting yard section. Jafet 09:40, 14 September 2006 (UTC)

[edit] ThePalace

I'm trying to remember correctly, but I believe that ThePalace's scripting Language Iptscrae uses RPN. I know that calculations are similar to this: "2 3 + var =" (sets var to 5) --TJ09 03:14, 19 November 2006 (UTC)

[edit] Language topologies similar to RPN syntax

Why is Subject Verb Object in the See Also section of RPN? Consider that in RPN, the operands come before the operator. In my mindset (English is my native and only language, by the way), "operator" is approximately like "verb", sort of. I therefore think that the RPN-ish syntaxes in natural languages are the Subject Object Verb syntax and the Object Subject Verb syntax. Perhaps I'm missing something, but I just can't see any logical reason for Subject Verb Object to be in the ==See Also== section of Reverse Polish Notation. Stuart Morrow 18:45, 30 January 2007 (UTC)

You're absolutely correct. Fixed. /blahedo (t) 23:42, 2 February 2007 (UTC)

[edit] Reordering expressions

I've removed this paragraph:

One could reorder this expression, putting the operand directly after each pair of values such as, 4 7 + 3 *. The reordered form would be entered as "4", "Enter", "7", "+", "3", "*". Both expressions are equivalent, but the first requires more memory as all operands must be stored prior to the application of their respective operators. In the second expression the result of the addition of 4 and 7 would be stored on the stack as the variable 11 where the multiplication with 3 is calculated. In the first method 3, 4, and 7 must be stored before any calculations. The second method only requires two memory locations to be stored regardless of the expression's length or complexity. The first method's memory requirements depend directly on the number of operands in the equation.

First of all, the reordering as stated is a consequence of the commutative property, not a distinct "method" of using RPN. If the operations were instead subtraction and division, that kind of reordering would change the result!

But that could be (and is) addressed with a swap operator. The larger problem is that the second claim, that "the second method only requires two memory locations to be stored regardless of the expression's length or complexity" is not true. If I have an expression like "(3 + 4) * (5 + 6)", I need to store more than two values in memory no matter how I reorder them. (At least, within the context of arithmetic operations. This issue is related to tail recursion and continuations, but in any case, is entirely independent of the notation used for the expression. /blahedo (t) 22:59, 2 February 2007 (UTC)

[edit] Move request to "Postfix notation"

This would bring it in line with Prefix notation and the template used on the page itself. --Islomaniac 973 22:21, 11 April 2007 (UTC)

[edit] VB6 example is completely broken

The postfix evaluator example does not work at all. Passing it "3 2 +", for example, returns 4 instead of 5. "3 2 + 7 1 * -" returns 6, not -2. "3 2 + 7 * 1 -" returns 0, not 34. However, is a code example really necessary anyway? Burbble 23:49, 25 September 2007 (UTC)

Would anybody object if I just deleted it then? 75.83.32.62 18:22, 30 September 2007 (UTC)

I'm going to replace the VB6 example with a Python example I wrote and hereby place into the public domain. It is much shorter, easier to read and more portable. I wrote it by interpreting "The postfix algorithm" with no previous knowledge of RPN so I might have made some mistakes, if so please fix them. BJTalk 13:30, 20 November 2007 (UTC)
Great script. Without lengthening it, I've improved it to support:
  1. integers of more than one digit
  2. floating point numbers
  3. unary negative symbols (e.g. -3.2)
  4. any binary operator (e.g. **, //)
The script now requires input elements be separated by spaces, which is reasonable and the article also refers to method of expression. Small header comment instructs the reader. --Ds13 (talk) 01:14, 11 June 2008 (UTC)
Looks great! BJTalk 01:33, 11 June 2008 (UTC)

[edit] Where does the Charles Hamblin come in?

Okay, I find this: http://www.csc.liv.ac.uk/~peter/this-month/this-month-3-030303.html, but I remember reading Lukasiewicz and Tarski in school, and they had both the prefix and the postfix notation, as I recall. This seems to me to be an attempt to enhance Australian contributions to computing :) The stack was invented by Friedrich Bauer in Munich, not by Hamblin, IMHO. I think we need a computer historian here. --WiseWoman (talk) 14:10, 28 December 2007 (UTC)