Day 18: Operation Order
Haskell: Part 1 (00:55:04, rank 2966), Part 2 (01:59:47, rank 3719)
I really enjoyed this one. For part 1, I rolled my own recursive parser and things went okay, despite struggling with Parsec as usual. Part 2 caught me out a little, since I thought maybe treating * as an implicit left parenthesis might work, and it actually did pass a few of the test cases. However, soon enough I realised it wasn't going to work, and remembered a few algorithms from the compiler construction course back in college. And by "remembered", I mean "remembered the existence of" -- I still had to look up Djikstra's shunting yard algorithm on Wikipedia. From there, it was pretty straightforward, although I mixed up the order of pops/pushes on the output and operator stacks several times. The last part was then implementing a function (calc') that walks the output queue and calculates the result of each expression using a stack that's passed down through recursive calls.