My blog links to some runnable Python code for this algorithm, with tests:<p><i>Code for the Shunting Yard Algorithm</i> <a href="http://www.oilshell.org/blog/2017/04/22.html" rel="nofollow">http://www.oilshell.org/blog/2017/04/22.html</a><p><a href="https://github.com/bourguet/operator_precedence_parsing" rel="nofollow">https://github.com/bourguet/operator_precedence_parsing</a><p>It seems like there are 2 common algorithms for expressions: the shunting yard algorithm and Pratt parsing [1]. As best as I can tell, which one you use is a coin toss. I haven't been able to figure out any real difference.<p>They're both nicer than grammar-based approaches when you have many levels of precedence, like C.<p>But it doesn't seem like there is any strict relationship between the two algorithms, which is interesting. I guess there are other places where that happens, like there being at least two unrelated algorithms for topological sort.<p>Trivia: The original C compilers used the shunting yard algorithm. IIRC the source made reference to Dijikstra.<p>[1] <a href="http://www.oilshell.org/blog/2017/03/31.html" rel="nofollow">http://www.oilshell.org/blog/2017/03/31.html</a>