4 ms·
Stack Machines: Notation Polish Reverse calculator
- blueatlas 13y agoVery 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.
- jliechti1 13y agoRelated, the Shunting-yard algorithm (http://en.wikipedia.org/wiki/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.
- thu 13y agoI have once modified the Shunting-yard algorithm to parse distfix expressions (https://github.com/noteed/syntactical https://github.com/noteed/syntactical). Agda is quite famous for offering distfix (or mixfix) operators.
- csmuk 13y agoInteresting 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/infix-postfix/ 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.
- Lazare 13y agoNot 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.)
- barrkel 13y agoRPN 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.
- thu 13y agoPython's Pickle format is similar. It interprets opcodes using a stack-based "pickle" machine. (I have started an Haskell implementation of it https://github.com/noteed/python-pickle https://github.com/noteed/python-pickle)
- camperman 13y ago"Notation Polish Reverse" I see what you did there!
- mattwritescode 13y ago+1 to you! :P
- mattholtom 13y agoHey 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 https://github.com/codeandiron/calculator
- jheriko 13y agoshame 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/infix-postfix/ http://scriptasylum.com/tutorials/infix_postfix/algorithms/i...
- igorw 13y agoHi, author here. Shunting-yard is actually what the next post in the series will be about. ;-)