S3E23: The Shunting Yard Algorithm and Its Slow-Motion Player

In this episode we take an introductory look at an exciting and, as far as I can tell, not so well developed idea in computer science known as "algorithms animation and/or visualization". To that end we use the Shunting Yard algorithm as an ice breaker. Some level of familiarity with this algorithm is required because in this episode we do not deep-dive into all of Shunting Yard's nooks and crannies. Instead, we take a fairly enumerative look at the notions that go into the design of that algorithm, the arithmetic expressions, the operator's arity, precedence, associativity, a stack and a queue, but we expect that our viewers are not complete newbies with these notions. Next, we consider the three popular notations: infix, prefix, postfix. Again, way more can be said about those. Then, we look at the two stages of the Shunting Yard algorithm: the conversion of the input material given in the infix form into the equivalent material outputted in either the prefix or the postfix form. Here we try to drive the following point home: the tactical advantage of the prefix and the postfix forms over their infix counterpart is the "I came, I saw, I executed" property. That is, in both prefix and postfix notations the physical location of an operator is equated to its order (or moment) of evaluation. When a prefix or a postfix-compiled expression is processed, the moment we encounter an operator, that is the moment when we execute it. Right then and there. Put slightly differently, prefix and postfix notations are parentheses or brackets free. Next, we look at two sample computations: one of these computations is based on the prefix notation and the other such computation is based on the postfix notation. Lastly, I share with the audience my take on the slow-motion player of the Shunting Yard algorithm with which the user has a full control over the step-by-step process of evaluation an input arithmetic expression. The links to all the relevant code are in the comments section: a deep tutorial on how to develop software gradually, the Java code that implements an arithmetic expression evaluator, and the Java code for the said slow-motion player. Give it a try. Share your, better, idea on how to animate the Shunting Yard algorithm or any other computer science algorithm!