Inchworm Evaluation, Or Evaluating Prefix-Expressions with a Queue

mgcadmin 02-25-2026

The relation between stacks and expression evaluation is well established. Stack based evaluation is employed by every computer at some level. Infix and Postfix expressions lend themselves naturally to evaluation with a stack. But what about the stacks brother, the queue? That question has been kicking around in my head for a while and every once in a while bubbles back up to the surface.

If we look to the world of theoretical computer science and automata theory, we can observe the work of Emil Post and his tag machines. Interesting and heady stuff for sure, but not quite where I'm going with this post. Instead, I want to show an algorithm that quite literally, came to me in a dream.

 

---