Shunting-Yard Animation

#1

Post by s1291 » Sun, May 10, 2026, 3:00 PM UTC

Shunting-Yard Animation
somethingorotherwhatever.com

Re: Shunting-Yard Animation

#2

Post by IIAOPSW » Sun, May 10, 2026, 4:54 PM UTC

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)

Re: Shunting-Yard Animation

#3

Post by dcrazy » Sun, May 10, 2026, 4:59 PM UTC

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

Re: Shunting-Yard Animation

#4

Post by alter_igel » Sun, May 10, 2026, 5:27 PM UTC

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.

Re: Shunting-Yard Animation

#5

Post by justinpombrio » Sun, May 10, 2026, 5:29 PM UTC

dcrazy wrote: post #3

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

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.

Re: Shunting-Yard Animation

#6

Post by justinpombrio » Sun, May 10, 2026, 5:33 PM UTC

alter_igel wrote: post #4

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

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.

Re: Shunting-Yard Animation

#7

Post by abd-nh » Sun, May 10, 2026, 5:52 PM UTC

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

Re: Shunting-Yard Animation

#8

Post by pimlottc » Sun, May 10, 2026, 6:37 PM UTC

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

Re: Shunting-Yard Animation

#9

Post by dcrazy » Sun, May 10, 2026, 6:42 PM UTC

pimlottc wrote: post #8

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

Drag the speed slider to the right.

Re: Shunting-Yard Animation

#10

Post by dcrazy » Sun, May 10, 2026, 6:43 PM UTC

justinpombrio wrote: post #5

dcrazy wrote: post #3

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

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.

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.