Stack Machines: Notation Polish Reverse calculator

Related, the Shunting-yard algorithm (http://en.wikipedia.org/wiki/Shunting-yard_algorithm) is a clever algorithm for converting infix expressions into Reverse Polish or Polish Notation, that only takes linear time.

Interesting read.

You can make this run infix notation by adding a simple front end. Reasonable quality description here: http://scriptasylum.com/tutorials/infix_postfix/algorithms/i...

Although that bit is built into my brain now after using RPN/RPL calculators for the last 20 years. I wouldn't swap RPN/RPL for anything.

RPN can also be viewed as a serialization mechanism for expression trees, and with the addition of a 'dup' operator, directed acyclic graphs (aka DAGs). The notation is used by both the JVM (with typed operators) and the CLR (with operators whose type is inferred from the operands on the stack). Evaluating the stack symbolically results in rehydrating the source tree.

Hey I made something like this a while back too! Except I'm not so sure mine is "Reverse" PN, it might just be standard PN...

https://github.com/codeandiron/calculator

Not bad. Although it took me a minute to figure out what language the example code was in. I'd suggest a note to mention that it's PHP. (And also, possibly, using a different language, but that's a matter of taste.)

Very well done with both the content and the quality of the visuals. It strikes me how brief this explanation of RPN is, but still with clarity.

shame there is no mention of how you can convert from infix to postfix by also using a stack... this completes the link to familiar everyday programming languages. :)

http://scriptasylum.com/tutorials/infix_postfix/algorithms/i...

"Notation Polish Reverse"

I see what you did there!