Talk:Reverse Polish notation

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)

I agree; I think the current "5 1 2 + 4 * 3-+" example in the article is very cumbersome, and does not easily express how one would use RPN in a more natural form (rather it makes RPN look like some sort of crazy weird system of academic interest only). "1 2 + 4 * 5 + 3 -" is exactly how I would enter this, being simplest to read from infix expressions inside-out, and I think the example ought to be changed to reflect this. Kate (talk) 11:07, 24 September 2008 (UTC)

I agree---3*4+2*5 is "3 4 * 2 5 * +" to me, so I suppose you do need an expandable stack, but that "hanging" 5 should definitely be moved in the example... In general, I would say that numbers should be as close to the operators that operate on them as possible. (which is what you get if you read the infix from inside out)

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!

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)

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.

We also need an example with a negative number. — Preceding unsigned comment added by Cdunn2001 (talk • contribs) 18:30, 26 July 2011 (UTC)

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)

Vague Explanation 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)

Incomprehensible example

I was baffled by this example: (e.g. "/ 6 3" in Polish notation and "6 3 /" in reverse Polish both evaluating to 2, whereas "3 6 /" in reverse Polish notation would evaluate to ½)

Would not it be better to say that "6 3 /" is equal to 6 / 3 = 2 in the conventional postfix notation, but it would be 3 / 6 in true reverse Polish notation? Itman

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)

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)

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)

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)

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)

I Second this. Yehoodig (talk) 05:04, 18 February 2012 (UTC)

I don't agree. At present "postfix notation" redirects here, but we should rather split this into two articles, one about the theory and concepts of postfix notations in general, and another (this one) about "Reverse Polish Notation" (RPN) implementations as entry method (in calculators and likewise) specifically. There's quite a bit more on both topics which isn't currently covered by this combined article, and which cannot easily be added at present, as the structure of the combined article is a mess. This can be improved significantly by splitting the two topics covered here into separate articles. --Matthiaspaul (talk) 12:16, 25 August 2015 (UTC)

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. BJ^Talk 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! BJ^Talk 01:33, 11 June 2008 (UTC)

Added a even more readable implementation, which I hereby place into the public domain. 84.151.255.242 (talk) 23:43, 13 January 2009 (UTC)

Ack, the example as is makes me cry a bit. First of all, it's written in Python 3.0, which makes it harder for people to read (since python 3.0 isn't used often by programmers), harder for people to use (Python 3.0 isn't installed in many places), and for no good reason-- it doesn't use anything new to 3.0 . When 3.0 becomes standard, a 2.x example can be ported-- until then, it's more confusing. I have made the very minimal changes necessary to make it run on 2.6-- the fact that such changes are so minimal (just a matter of __future__ and changing input() to raw_input()) shows that the decision to show it as pure-3.0 was bad-- when 3.0 becomes the norm, changing this example will be very trivial. Second of all, the terrible decision to use float.__div__ etc. was made-- the operator module exists for a reason. Using float's methods make it slightly faster, at the cost of generality (what if we decide we want to use decimals instead?)-- and if speed was cared for, 2.6 would be used anyway. Moving to the operator module also aids readability-- no senseless, meaningless underscores.

Also, due to the way the list is used, giving blank input results in repeating the last value. This may or may not be intended, but either way, the current way to do it is bad-- it results in a mysterious error warning when it's done on the first line. I've instead made input required. My method for doing such may not be preferred-- perhaps explicitly expanding out the looop, rather than using iter() and other python idioms, would be preferable. You could also move the exception handling around, or maybe replace the functools.partial with a lambda.

Finally, I've added an easy way to exit without nasty error messages-- EOF suffices. Scorchsaber (talk) 12:32, 3 April 2009 (UTC)

I really don't think the Python code (or any code, for that matter) belongs in the article. I'd like to remove it, but since it's been there for a while, it seems like a good idea to ask for others' input first. Dead Horsey (talk) 05:20, 19 February 2010 (UTC)

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)

Also, reference #3 to Hamblin's work is a broken link. --69.174.58.36 (talk) 19:50, 26 May 2010 (UTC)

Neutrality of pros and cons

The advantages and disadvantages are apparently written by a proponent of RPN, as all disadvantages are presented as unimportant, and claims are not verified. Meertn (talk) 14:00, 12 June 2008 (UTC)

Sections of pros and cons are discouraged. Much like a section titled "Criticism"[1], a "Disadvantages" section will become a troll magnet. It's probably wiser to integrate any facts in a "Disadvantages" or "Advantages" section into the rest of the article, properly cited, and let the reader decide. --Ds13 (talk) 17:31, 12 June 2008 (UTC)

I think the pros and cons would be useful, because it would give readers a better idea of when to use RPN and when to use infix notation. Let me make an attempt. When calculating a formula on the fly, RPN requires fewer keystrokes to compute the same formula (or in simple cases, no more keystrokes) and allows for intermediate calculations. When writing a formula to be seen all at once, such as on a spreadsheet, infix notation is much easier to read. It all boils down to the right tool for the job. Bostoner (talk) 00:39, 8 January 2011 (UTC)

Actually, in simple calculations (adding 3 numbers together for example) RPN requires more keystrokes. "1 enter 2 enter 3 + +" is 7 keystrokes. "1 + 2 + 3 =" is only 6. Besides which, what is and isn't simple is open to interpretation, and probably not usefull to base encyclopeadic 'fact' on anyway. MrZoolook (talk) 12:24, 14 April 2014 (UTC)

That simple calculation can also be done with 6 keystrokes using RPN: "1 enter 2 + 3 +". Blutackey (talk) 04:12, 8 December 2014 (UTC)

Question

What if you wanted to add 34 and 4? What would the RPN be then, 344+? —Preceding unsigned comment added by 138.23.202.6 (talk) 17:05, 3 June 2009 (UTC)

RPN makes use of a separator, which is not shown here. It is the 'enter' key on these calculators. Using the lotus convention of enter as ~, we have 34~4+, giving 38. Note that the algebraic is 34+4= (where the numeric entries are terminated by +,= or ~,+). The graphics do not make this clear.

Because RPN works a stack in a predefined way, there is no need for brackets (nesting is done by enters ~), or for order of precedence (all binary operators are on Y,X). --Wendy.krieger (talk) 10:50, 27 August 2009 (UTC)

This should be noted somewhere (obvious) in the main entry. Also rather than simple spaces, the example should be "3 [ent] 4 [ent] + [ent]" for clarity. —Preceding unsigned comment added by 138.162.0.44 (talk) 00:28, 6 May 2011 (UTC)

RPN language different from RPN operating system

In 1988 i implememted a functioning RPN calculator in BASIC (on the tandy 100).

The RPN language might be correctly implemented by a LIFO stack as this example show.

 x PUSH y PUSH  POPA POPB c=b+a  PUSHC
            W V U T ...
  x  PUSH   x  W V U T ...
  y  PUSH   y  x  W V U T ...
  POPA      x  W V U T ...           a
  POPB      W  V U T ...            b,a
  c=b+a     W  V U T ...           c=b+a
  PUSHC     c  W V U T ...
  
 x PUSH POPA c=sin(a) PUSHC

The implementation uses a stack of registers that move up and down, including additional user friendly registers, like L. In the implementation i used, the registers were placed in an array, of the form (A, L, X, Y, Z, T, K). A and K were not directly accessable to the user: A is where all answers were returned, and K was used for a kind of recall arithmetic with registers of fixed value (eg Recall * pi)

The first example runs

    ( A, L, X, Y, Z, T)    [stack lift enabled]
 p  ( A, L, p, X, Y, Z)    T lost
 ~  ( A, L, p; p, X, Y)    stack lift disabled (;)
 q  ( A, L, q, p, X, Y)    stack lift enabled (,)
 +  (p+q,L, q, p, X, Y)    set flags LastX, StkD, MoveOk
    ( r ,L, q, p, X, Y)    r is resolved for display (MoveOk)
    ( r, q, r, p, X, Y)    flag LastX is now cleared
    ( r, q, r, X, Y, Y)    flag StkD is now cleared

The second example runs

    ( A, L, X, Y, Z, T)
 p  ( A, L, p, X, Y, Z)    stack lift enabled
sin ( r, L, p, X, Y, Z)    r = sin(p), set LastX, MoveOk
    ( r, p, r, X, Y, Z)    flag LastX clears.

These examples use a fixed stack and an extra value A. A is only moved to X when the function returns MoveOk. One might clear MoveOk, eg on taking the square root of a negative number.

--Wendy.krieger (talk) 11:09, 23 August 2009 (UTC)

Cultural References

If there came to be a cultural references section, it should contain a reference to: http://xkcd.com/645/

And I disagree with the cartoon. I think the bread is the operator, so from left to right, it should read: sausage mustard (floating in space) bread

121.73.5.66 (talk) 04:48, 6 October 2009 (UTC)

No worries. There won't be a cultural reference section. 129.128.221.64 (talk) 15:46, 7 October 2009 (UTC)

I just showed my gf that comic, then brought her to this article to explain why it's funny. She took one look at the example and said "thirtyfour plus?", which is the perfect example of why this notation is flawed. Logically, the operand makes the perfect delimiter. —Preceding unsigned comment added by 24.141.181.248 (talk) 07:39, 8 October 2009 (UTC)

History of implementations

National Semiconductor also had calculator models that used RPN in the 70's.Halconen (talk) 16:52, 11 November 2009 (UTC)

Modern Russian calculators

I would like to find out where/how the modern Russian calculators Elektronika MK-152 and MK-161 can be purchased.--109.193.211.159 (talk) 21:25, 24 July 2011 (UTC)

Practical Implications section

A lot of the entries in here are confusing at best and debatable at worst. For instance, "it is not possible to simply copy the expression from paper into the machine" -- this presumes the expression is given in some other notation, doesn't it? "Reverse Polish notation also reflects the way calculations are done on pen and paper" similarly makes undocumented and unclear assumptions about how calculations are done on paper. "Users must know the size of the stack" is simply untrue; what is true is that users who exhaust the stack will get incorrect answers, but I'll bet most buyers of HP calculators have no idea what the stack size is. I could go on, but my real point is that this seems to be a collection of observations various Wikipedia editors have made, which is not very Wikipedia-like, and I think readers would be better served by citations from sources. "The concept is easy to teach" is a debatable statement and probably not falsifiable; "According to Dijkstra, the concept is easy to teach --" assuming he did say so and an appropriate reference can be found -- "because..." would be nice and encyclopedic. --Chronodm (talk) 17:52, 5 October 2011 (UTC)

The writen form is the algebraic form, as eg 5+3=, where the rpn goes 5~3+, with the sign after the opeators. The practical implementation of RPN is different to the theoretical one. some common RPN tricks, like filling the stack by a ~ ~ ~, and x<>y, are not in the theory. It does indeed reflect the manner of calculation, since the operands must exist before the operator. Wendy.krieger (talk) 07:12, 7 October 2011 (UTC)

The algebraic form isn't the only "written form". (See e.g. how addition of three-digit numbers is taught in elementary school, which is arguably as similar to RPN as it is to algebraic notation.) And "reflect" in this sense should mean "closely correspond to", which now that you've tried to clarify, I don't think is the intent. As for how it's implemented, I would be in favor of a separate section on implementation, so long as it had good references. Chronodm (talk) 23:34, 25 October 2011 (UTC)

The actual process of calculation (eg multiplying 324 * 162), has nothing to do with the writing of it. The manner is not any of the several ways of doing this calculation (eg 324*324=104976; /2 = 52488 is one possible way), but rather to do with the way it is written (eg 324 * 162 = vs 324~162*). Under RPN, each key does exactly one thing, since the operands are always in place in the registers. The equal sign in algebraic depends heavily on what operations are still open, eg 2 + 3*5 = has both an addition and a multiplication open when the equal sign is pressed, while 2~3~5*+ has only the addition open at the time.

I'd favour a section on implementation too. I wrote one in basic, using the 15C as a basis. There are some differences between the rpn notation, and the rpn operating system. The essential difference is that the stack is limited, memories are available, as is the lastX register. One can roll the stack, as well as exchange values.

The actual RPN calculator has nothing to do with the objects it works with. The same logic, for example, can be used to control something like matrices for example. Basically, it's about things like how to do a x~y& (binary function), x# (single function), and then defining where the answers and flags ought be set. The stack algorithm simply waits for the function to happen (with a return to A), and then looks at the flags, and moves things like L<X<A, Y<Z<T, etc, according to what the function asks to happen. Every function is evaluated to A=X&Y, or A=f(x), and then some program is supposed to 'construct' A (eg construct the display string for the current base), before passing it to the stack move function.

Whether stack lift and drop happens depends on the function. The rpn '%', which calculates X <- X% of Y, does not generate a stack drop, which allows one to immediately follow it by a + or -, to allow %, %+ and %- to be done quickly. I had a version of divide a~b\, that did the same thing, that allows one to rapidly test prime factors one after the other.

  119~2\3\5\7\      would show 119/2, 119/3, 119/5 and 119/7, because the operator did not enable either stack lift or drop.

Memory arithmetic, though not part of the RPN, was modelled on the same way. A register above T (K), was used for 'recall-only' arithmetic, to allow for example, 2 rcl*pi. The value being recalled was moved there before the arithmetic. In practice, K was also used to roll the stack (eg K<T<Z<Y<X<K), and in exchanges (K<Y<X<K). On the other hand, recalls and memory exchange must go through A, to build the display string (ie A<M<X<A or A<X<M<A, the move A<X does the string build.

Once this is understood, every function simply sets A, and changes or sets flags. The rpn stack manager looks at the flags, and does things accordingly. There's about six or seven flags in use. Wendy.krieger (talk) 08:14, 26 October 2011 (UTC)

DC arbitrary precision desk calculator

Add to the "Current implementations" section dc

Link Dc_(computer_program)

Example:

dc -e "2 3 4 + * p"

which will output 14

The dc utility is very useful when there is a need to do arithmetic calculations in the shell scripts. Larytet (talk) 08:30, 17 July 2012 (UTC)

Less keystrokes?

Under the "Practical implications" section, it is stated that RPN requires less keystrokes. Is this REALLY correct? Surely, including the keystroke to seperate numbers, 3 enter 4 enter 5 + + in RPN is actually 1 MORE keystroke then 3 + 4 + 5 =. MrZoolook (talk) 12:08, 14 April 2014 (UTC)

Not really, as you would normally type 3 enter 4 + 5 + in RPN (in both, Classical RPN as well as Entry RPN). While your entry example is correct postfix notation as well, it consumes one stack level more than necessary (3 instead of just 2), something that doesn't matter in postfix notation in general (and in RPL), but can matter a lot in RPN, as in a typical implementation, you only have 4 stack levels to play with.

--Matthiaspaul (talk) 11:16, 6 September 2015 (UTC)

Intimidating and possibly unpronounceable?

The deadpan assertion that "people who speak English but not Polish find his family name intimidating and possibly unpronounceable" made me chuckle, but it clearly needs a ref. Is it meant as a joke? I see from the diff that it was added by an anonymous user a few months ago.--Lemuellio (talk) 13:36, 10 January 2015 (UTC)

Sounds like a facetious edit to me, and I can't find any sources that indicate it is in any way true, so I've removed it and added a reference for the shortened statement. Trimethylxanthine (talk) 03:46, 14 February 2015 (UTC)

Algorithm -- If there is only one value in the stack?

This Algorithm fails if an operator can take only one argument. For example the boolean NOT, or inverse. The Algorithm needs some massaging, but I don't feel qualified. — Preceding unsigned comment added by 137.28.222.145 (talk) 19:15, 23 June 2015 (UTC)

Here a number of operands of the particular operation is significant. Special:Contributions/RippleSax (talk) 11:41, 10 December 2015 (UTC)

Usage

So reverse polish notation always used with second stack: for converting from arithmetic expression and for evaluating. PPN describes relations between data and commands (as in computer architecture). With polish notation easier to search templates (if it is instruction set architecture) and for example decompile this templates because they are typical and they can be assumed to be known. For this operation stack also needed. Expressions which user inputs in editor for compilation/interpretation may be simplified this way: convert to rpn with stack, evaluate with stack but only partially in places where expression may be simplified (executing of the constant expressions and subexpressions on time of rpn stack conversion for reducing cost) 93.92.200.193 (talk) 11:41, 10 December 2015 (UTC)