Follow

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: somethingorotherwhatever.com/s

youtube.com/watch?v=gHniHE_Hvh

· · Web · 2 · 10 · 9

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.

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,
the order goes the other way for exponentiation:
1 ^ 2 ^ 3 = 1 ^ (2 ^ 3)

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

@christianp
So… the algorithm isn't considering this constraint. Fine. Space for further research :)

@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\)

@christianp
I even switched to browser view to check whether something got lost in transmission 😅

@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“

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.

@christianp
Thanks. Important fact in certain circumstances.

@christianp
Especially the order and arguments can change depending on how you put the brackets.

Sign in to participate in the conversation
Mathstodon

The social network of the future: No ads, no corporate surveillance, ethical design, and decentralization! Own your data with Mastodon!