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

6 favourites 1 retweet

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…

3 favourites 0 retweets

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.

2 favourites 0 retweets

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.

2 favourites 0 retweets

In reply to @christianp

In the second, the addition must happen after the multiplication, so it's held back.

1 favourite 0 retweets

In reply to @christianp

In the third, brackets ensure that the addition happens first.

3 favourites 0 retweets

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,

3 favourites 1 retweet

In reply to @christianp

the order goes the other way for exponentiation:
1 ^ 2 ^ 3 = 1 ^ (2 ^ 3)

2 favourites 0 retweets

View this tweet on twitter.com

This tweet as JSON