A while ago over on Mastodon @davidphys1@mathstodon.xyz 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: somethingorotherwhatever.com/shunting-yard-…
In reply to @christianp
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).
youtube.com/watch?v=gHniHE…
In reply to @christianp
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.
In reply to @christianp
Here are some animations to illustrate.
In the first, operations happen left-to-right, so they appear in the same order in the output as in the input.
In reply to @christianp
In the second, the addition must happen after the multiplication, so it's held back.
In reply to @christianp
In the third, brackets ensure that the addition happens first.
In reply to @christianp
The last wrinkle for standard arithmetic is that exponentiation is right-associative: while for the other operations you work left-to-right:
1 − 2 − 3 = (1 − 2) − 3,
In reply to @christianp
the order goes the other way for exponentiation:
1 ^ 2 ^ 3 = 1 ^ (2 ^ 3)