[wenc]

> 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.

[abecedarius]

A good way to rederive table-driven expression parsing on the spot is to start with recursive descent and notice how it makes a recursive call for every level of precedence, even the levels where "nothing happens" because there's no operator of that precedence level at this place in the input. Use the table to call the "right place in the grammar" directly. This works out to be the precedence-climbing algorithm.

I guess you'd get to the shunting yard from there by turning the remaining recursion into an explicit stack, but I haven't worked that out to check.

[wenc]

That sounds about right. I usually use this simple snippet as my starting point [1]. As you can see, to implement a working stack evaluator one has to do a little bit more than just handle infix operators.

[1] PyParsing Simple Calc - see the evaluateStack() function. https://github.com/pyparsing/pyparsing/blob/master/examples/...