Shunting-yard algorithm
en.wikipedia.org
Shunting-yard algorithm
1–10 of 27 posts
Re: Shunting-yard algorithm
#2I was hoping for an algorithm that solves railway shunting problems. Anyone know of something that does that?
Re: Shunting-yard algorithm
#3This 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.
Re: Shunting-yard algorithm
#4I was hoping for an algorithm that solves railway shunting problems. Anyone know of something that does that? https://en.wikipedia.org/wiki/Train_shunting_puzzle
train shunting problems seem like a variation of tower of hanoi https://en.wikipedia.org/wiki/Tower_of_Hanoi
Re: Shunting-yard algorithm
#5I was hoping for an algorithm that solves railway shunting problems. Anyone know of something that does that? https://en.wikipedia.org/wiki/Train_shunting_puzzle
This is really interesting. Found: https://www.researchgate.net/publication/225576076_Shunting_...
I wonder what real railway yards do.
Re: Shunting-yard algorithm
#6This 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.
Re: Shunting-yard algorithm
#7My 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.
Re: Shunting-yard algorithm
#8I 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.
Re: Shunting-yard algorithm
#9This 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} The naive approach to parsing will result in the wrong order of operations, since they'll just be done in the order they appear: x + y * z => (x + y) * z Rather than: x + (y * z) As it should be. The shunting yard algorithm will rearrange the expressions.…
Just the other day I was thinking about how all this infix business is needlessly complicated and leads to subtle bugs and hard to understand code. Like every time I encounter an uncommon operator in some language I have to lookup its precedence. So much time wasted trying to satisfy this silly familiarity with math notation. Only imagine how much easier things could be if all infix operators were, for example, left associative and had the same precedence. No more parsing bugs, no implicit orders and behaviors to remember, consistent order, even more natural and familiar than the math notation allowing to focus on things that matter and forget about dealing with precedence and associativity.
Re: Shunting-yard algorithm
#10This 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.
> This is one of those algorithms that everyone should understand or memorize.
Understand... perhaps; it is a fascinating algorithm. It's also not complicated at all.
Memorize? Perhaps for code challenges, interviews and special occasions like that... but I haven't found it to be useful enough to commit to memory because in order to parse truly arbitrary expressions, you need to remember much more than just the the shunting yard rules.
I say this as someone who authored a mathematical modeling DSL in grad school and had implement this algorithm to correctly parse arbitrarily complicated math expressions. I was deep in the weeds of this. But I don't think I would have been able to reproduce it from memory even during that time. (also, I had to implement a more general version of the algorithm that dealt with function composition, multi-argument functions, unary operators, special keywords like sum/product over sets, etc.)
Of course nowadays I'm so lazy that I just do "import asteval" in Python. The reason is that once you get beyond the simple operators, arbitrary math expression parsing can be quite hard to get right, and I prefer using something that's heavily tested with no unhandled corner cases.