If I start the train and then type a nested bracket expression like 2+(2-(3/5)) the train jumps the track
Shunting-Yard Animation
11–17 of 17 posts
Re: Shunting-Yard Animation
#12I'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…
> 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.
Re: Shunting-Yard Animation
#13This 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.
Re: Shunting-Yard Animation
#14Note 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.
Re: Shunting-Yard Animation
#15Earlier quoted context omitted.
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.
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
"13" "-" "2" "*" "5" "+" "4"
"13" "2" "5" "*" "-" "4" "+"
(+ (- 13 (* 2 5)) 4)Re: Shunting-Yard Animation
#16Earlier quoted context omitted.
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.
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.
Re: Shunting-Yard Animation
#17This 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.
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....