reedbeta at December 11th, 2011 14:57 — #1
I wrote an article about an algorithm that doesn't seem to be very widely known, but should be! It's called the "shunting-yard algorithm" and is used to parse arithmetic expressions in infix notation. Check out the article here: http://www.reedbeta.com/blog/2011/12/11/the-shunting-yard-algorithm/
smile_ at December 11th, 2011 18:48 — #2
Ha ha, for my parsers I've reinvented the wheel and created modification of this algorithm with combined operand/operation stack. In my stack I have operands (A) or operands with incomplete operation (A+). Each stack element have 'level' which corresponds to operator precedence and incoming operator combines stack elements with level higher than operator level. At the end of expression I put dummy operator with lowest level.
For example, parsing token sequence A * B + C * D [end]
(A*B)+ <- A* and B have higher level than +
(A*B)+ C* D
((A*B)+(C*D))= <- (A*B)+, C* and D have higher level than [end]
If someone decides to use my version instead of original I can give additional details.
roel at December 12th, 2011 05:39 — #3
That was an interesting read, Reed. Haven't heard of it in CS classes either.
fireside at December 12th, 2011 06:15 — #4
I think, particularly with indy games, these kinds of solutions may be used more often.
stainless at December 12th, 2011 07:40 — #5
Interesting, quick and simple to code as well
However I still just "Use the Forth Luke"
You can write a Forth interpreter in very little code
oisyn at December 12th, 2011 09:35 — #6
Ah yes, one of the legacies of the famous Dutch computer scientiest Edsger Dijkstra
I never heard of this algorithm until I happened to see a forum post that referenced it
Funny, was it this one? http://devmaster.net/forums/topic/12081-fast-math-expression-parser/page\_\_view\_\_findpost\_\_p\_\_65660
reedbeta at December 12th, 2011 13:18 — #7
Yes, .oisyn, that was indeed the one.