The Shunting-Yard Algorithm

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Dec 11, 2011 at 19:57

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/

6 Replies

Please log in or register to post a reply.

6eaf0e08fe36b2c23ca096562dd7a8b7
0
__________Smile_ 101 Dec 11, 2011 at 23:48

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
A*
A*   B
(A*B)+         <-  A* and B have higher level than +
(A*B)+   C
(A*B)+   C*
(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.

6aa952514ff4e5439df1e9e6d337b864
0
roel 101 Dec 12, 2011 at 10:39

That was an interesting read, Reed. Haven’t heard of it in CS classes either.

A638aa42130293f319eda7fa4ba121f4
0
fireside 141 Dec 12, 2011 at 11:15

I think, particularly with indy games, these kinds of solutions may be used more often.

B5262118b588a5a420230bfbef4a2cdf
0
Stainless 151 Dec 12, 2011 at 12:40

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

340bf64ac6abda6e40f7e860279823cb
0
_oisyn 101 Dec 12, 2011 at 14:35

Ah yes, one of the legacies of the famous Dutch computer scientiest Edsger Dijkstra :)

.edit:

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 ;)

A8433b04cb41dd57113740b779f61acb
0
Reedbeta 167 Dec 12, 2011 at 18:18

Yes, .oisyn, that was indeed the one. ;)