This algorithm is great.
I was working on a new metric alert evaluation system and built an expression parser for things like:
system.disk.free{*} / 1024 by {host}
x + y * z => (x + y) * z
x + (y * z)
After implementing it I noticed my results were different than the reference system... and that's when I discovered we did arithmetic wrong in the main app and had for years.
So I had to hard code a toggle for whether to do math properly :(. It's a sort of Hippocratic oath when it comes to these things... first do no harm, and even if it was wrong, people were relying on the existing functionality, and changing it would likely result in sudden alerts for folks.
In the end we did fix it in the main app, but you always feel kind of dirty writing code like that.
I implemented this as a class assignment in Univac 1100 assembly language in the late 70s. I always thought it was a cool algorithm. I had an HP scientific calculator at the time and was a fan of RPN.
It's a neat algorithm :) When learning Go I made an implementation of Shunting-Yard at some point: https://github.com/DylanMeeus/GoPlay/blob/master/ExpressionP...
As part of something else I was trying. As I was just learning Go at that point, the code is not that clean :D But AFAIK it did work. My memory is a bit hazy on that :)
This is one of those algorithms that everyone should understand or memorize. I had variations of this algorithm in the coding interviews or coding challenges of 6 companies (!) my last cycle.
Hah, a few years ago I learned Go by building a simple programming language (super basic with Lua-like syntax) and definitely used this article to help me. I made a slight modification so it could support functions with multiple arguments. Fun times.
I was hoping for an algorithm that solves railway shunting problems. Anyone know of something that does that?
The original paper is a good read to get some insight into the thought process: https://www.cs.utexas.edu/~EWD/MCReps/MR35.PDF
My blog links to some runnable Python code for this algorithm, with tests:
Code for the Shunting Yard Algorithm http://www.oilshell.org/blog/2017/04/22.html
https://github.com/bourguet/operator_precedence_parsing
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.
They're both nicer than grammar-based approaches when you have many levels of precedence, like C.
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.
Trivia: The original C compilers used the shunting yard algorithm. IIRC the source made reference to Dijikstra.
[1] http://www.oilshell.org/blog/2017/03/31.html