Shunting-Yard Animation (opens in new tab)

(somethingorotherwhatever.com)

57 pointss129115d ago16 comments

16 comments

Note the shunting yard algorithm is an iterative (as opposed to recursive) version of Pratt parsing (and also precedence climbing which is virtually identical). However as normally stated it does not do proper error checking - it will accept totally invalid input.

That isn't a fundamental limit of the algorithm though; you can easily add error checking, as I did here: https://github.com/Timmmm/expr/blob/1b0aef8f91460974d526b5ba...

I'm not really sure why this is omitted.

alter_igel15d ago

I'm not familiar with the algorithm and I don't see much explanation on the site (at least on mobile) but AFAICT this is turning parenthesized infix expressions into reverse Polish notation. In other words, it takes human-readable mathematical formulas and converts them into something a simple stack-based machine can compute in one forward pass.

It also appears that separate digits aren't interpreted as decimal numerals (i.e. (1)(3) is the sequence 1,3 and not 13) which can look a bit misleading.

justinpombrio15d ago

Yeah, it's a parsing algorithm for parsing infix (etc.) expressions. If you've seen a parsing library refer to "precedence climbing" or "operator precedence parsing", it's doing this (or something very similar).

If you want to enter the number `13`, that should be one token, but there's no way to make a `13` token in this UI. You need to stick to single digits for this site to work correctly.

lelanthran15d ago

> It also appears that separate digits aren't interpreted as decimal numerals (i.e. (1)(3) is the sequence 1,3 and not 13) which can look a bit misleading.

I didn't find it misleading; it says it operates on tokens, not digits.

IIAOPSW15d ago

Hold up. you can't just have the train take the parenthesis off screen and hand wave away what happens to those cars. What happens when your forced to keep the garbage of a computation because you can't delete anything?

(https://en.wikipedia.org/wiki/Reversible_computing)

talkingtab15d ago

This is great! As a kid I used to love HO scale model trains. There is an old movie of me on my birthday looking at my train set with eyes as big as plates. Fast forward, and I love networking and programming. I recognized that networking is just trains on Ethernet or Wifi, but now realize even the programming is just the same. Still making things go places and go around after all this time.

xerox13ster15d ago

Go to the national train museum in Scranton, PA. I got to see (through critical thinking, not necessarily an outright display) how the modern career of software engineering has its roots in the telegraph lines, built along the rail lines, which eventually became the phone lines they used when timetables broke down. Follow that through to Bell Labs and C, etc....

abd-nh15d ago

I made a basic demo of this years go: https://abdnh.github.io/shunting-yard-algorithm-demo/

rembicilious15d ago

If I start the train and then type a nested bracket expression like 2+(2-(3/5)) the train jumps the track

pimlottc15d ago

I can’t figure out how to make it start processing the input on mobile Safari, am I missing something?

dcrazy15d ago

Drag the speed slider to the right.

dcrazy15d ago

I typed `100+88/4` and the resulting output was `100884+/`. Should the algorithm be inserting a symbol to delineate operands?

justinpombrio15d ago

It treated that as

    1 0 0 + 8 8 / 4

which is nonsensical, but it has no error detection so it rolled with it. Really `100` should be its own token, but there's no way to input that.

dcrazy15d ago

How would one typically implement this tokenization? Pre-pass on the input? My initial thought was to push an operand-terminator token when encountering an operator, but it was unclear to me whether it should be pushed to the stack or the output.

j / k navigate · click thread line to collapse

16 comments

timhh15d ago

That isn't a fundamental limit of the algorithm though; you can easily add error checking, as I did here: https://github.com/Timmmm/expr/blob/1b0aef8f91460974d526b5ba...

I'm not really sure why this is omitted.

alter_igel15d ago

It also appears that separate digits aren't interpreted as decimal numerals (i.e. (1)(3) is the sequence 1,3 and not 13) which can look a bit misleading.

justinpombrio15d ago

If you want to enter the number `13`, that should be one token, but there's no way to make a `13` token in this UI. You need to stick to single digits for this site to work correctly.

lelanthran15d ago

> It also appears that separate digits aren't interpreted as decimal numerals (i.e. (1)(3) is the sequence 1,3 and not 13) which can look a bit misleading.

I didn't find it misleading; it says it operates on tokens, not digits.

IIAOPSW15d ago

(https://en.wikipedia.org/wiki/Reversible_computing)

talkingtab15d ago

xerox13ster15d ago

abd-nh15d ago

I made a basic demo of this years go: https://abdnh.github.io/shunting-yard-algorithm-demo/

rembicilious15d ago

If I start the train and then type a nested bracket expression like 2+(2-(3/5)) the train jumps the track

pimlottc15d ago

I can’t figure out how to make it start processing the input on mobile Safari, am I missing something?

dcrazy15d ago

Drag the speed slider to the right.

dcrazy15d ago

I typed `100+88/4` and the resulting output was `100884+/`. Should the algorithm be inserting a symbol to delineate operands?

justinpombrio15d ago

It treated that as

    1 0 0 + 8 8 / 4

which is nonsensical, but it has no error detection so it rolled with it. Really `100` should be its own token, but there's no way to input that.

dcrazy15d ago

j / k navigate · click thread line to collapse