A while ago @davidphys1 asked why nobody had made animations of the shunting yard algorithm with cutesy trains.
There is no surer way to summon me!
I've spent some of my spare time over the bank holidays making exactly that: https://somethingorotherwhatever.com/shunting-yard-animation/
The shunting yard algorithm neatly solves the problem of translating a mathematical expression written in infix notation (operators go between the numbers/letters) to postfix notation (operators go after the things they act on).
The core problem is that you need to work out what just what an operator applies to: with the order of operations, it might be just one number, or it might a large sub-expression.
The algorithm solves this by holding operators on a separate stack until they're needed
Here are some animations to illustrate. In the first, the operations happen left-to-right, so they appear in the same order in the output as in the input.
In the second, the addition must happen after the multiplication, so it's held back.
In the third, brackets ensure that the addition happens first.
Doesn't that depend on the domain?
I mean, some rules aren't valid anymore for, say, Quaternions or Octaves…
@RyunoKi but no, I think that if I wrote an expression \(a \times b \times c\), where a, b and c are octonions and so multiplication isn't associative, I'd expect you to interpret it as \(a \times b \times c\), by convention.
I might include some brackets, to avoid relying on convention.
@RyunoKi just noticed I missed the brackets in my second-last tweet! I had trouble LaTeXing, then didn't check how it looked!
I'd expect you to interpret \( a \times b \times c\) as \((a \times b) \times c\)
„The core problem is that you need to work out what just what an operator applies to: with the order of operations, it might be just one number, or it might a large sub-expression.
The algorithm solves this by holding operators on a separate stack until they're needed“
Is that assuming „standard" arithmetic like associative multiplication? Or the lack thereof?
Like, once „computer does that“ many people rely on it without questioning the result.
@RyunoKi right, the algorithm says that multiplication is left-associative. For real numbers, it doesn't matter.
The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!