Talk:Reverse Polish notation
From Wikipedia, the free encyclopedia
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!
Contents |
[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)
