Re:Stack Machines: Notation Polish Reverse calculator
by jliechti1 on Monday December 02, 2013 @08:33AM
(#6833485)
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.
Re:Stack Machines: Notation Polish Reverse calculator
by thu on Monday December 02, 2013 @09:45AM
(#6833892)
I have once modified the Shunting-yard algorithm to parse distfix expressions (https://github.com/noteed/syntactical). Agda is quite famous for offering distfix (or mixfix) operators.
Re:Stack Machines: Notation Polish Reverse calculator
by barrkel on Monday December 02, 2013 @09:24AM
(#6833765)
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.
Re:Stack Machines: Notation Polish Reverse calculator
by thu on Monday December 02, 2013 @09:42AM
(#6833876)
Python'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)
Re:Stack Machines: Notation Polish Reverse calculator
by Lazare on Monday December 02, 2013 @09:06AM
(#6833669)
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.)
Re:Stack Machines: Notation Polish Reverse calculator
by jheriko on Monday December 02, 2013 @10:36AM
(#6834246)
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. :)
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.
https://github.com/codeandiron/calculator
I see what you did there!
http://scriptasylum.com/tutorials/infix_postfix/algorithms/i...