Shunting-Yard Animation

timhh 8 days ago |

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_igel 8 days 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.

justinpombrio 8 days 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.

lelanthran 8 days 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.

IIAOPSW 8 days 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)

abd-nh 8 days ago |

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

talkingtab 8 days 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.

xerox13ster 7 days 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....

dcrazy 8 days ago |

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

justinpombrio 8 days 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.

dcrazy 8 days 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.

justinpombrio 8 days ago | | |

Parsing is usually implemented in two steps: first there's lexing where the input is turned into a sequence of tokens, then there's proper parsing where the sequence of tokens is turned into an abstract syntax tree. This shunting yard algorithm is part of parsing. Lexing happens before that.

For example, this input:

    13- 2  *5 + 4

would be lexed into this sequence of tokens:

    "13" "-" "2" "*" "5" "+" "4"

You could use the shunting yard algorithm to put these in a convenient postfix order:

    "13" "2" "5" "*" "-" "4" "+"

It's really easy to then turn it into an abstract syntax tree (AST). Go through each token in order: if it's a number you make it into a node and push it onto a stack; if it's a binary operator you pop two nodes off the stack and make a node out of those and the binary operator. If you write down this AST as an s-expression you get:

    (+ (- 13 (* 2 5)) 4)

fc417fc802 8 days ago | | |

While the adjacent comment provides a proper answer to the broader question I thought I'd answer you more directly. A function that consumes one or more characters and then outputs a token will suffice. You turn the character stream into a token stream (or an altered character stream) on the fly. See lisp reader macros for example.

rembicilious 8 days ago |

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

pimlottc 8 days ago |

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

dcrazy 8 days ago | |

Drag the speed slider to the right.