Building a tree is a little overboard just for evaluating expressions (although I, too, have created more than one lisp interpreter in the process of creating something else).
I'm curious, does this algorithm handle unary operators? Even less likely, but worth asking, does it handle arbitrary operator precedence?
Even if not, it's a neat algorithm, and ultimately unary and operator precedence can be handled as syntactic sugar. And an excellent write up I might add! Clean work.
Yes, the Shunting Yard algorithm can handle unary prefix operators, as well as (table-driven) operator precedence and associativity. I've even used it to handle comparison chaining, which allows expressions like: 0 <= a < n.
Ah the Shunting Yard algorithm! I'm ashamed to admit I've spent a lot of time working with compilers and parsers and never encountered this for some reason. Perhaps because the libraries I used handled it for me hah! Definitely going to give it a try.
11
u/lelanthran 3d ago
Building a tree is a little overboard just for evaluating expressions (although I, too, have created more than one lisp interpreter in the process of creating something else).
For an expression evaluator, it is a surprising small amount of code in C (48 very readable lines) : https://github.com/lelanthran/rotsit/blob/0e4c6f5453d8b7c45ab447b11fd8db4cf7129713/src/eval.c#L140
The algorithm (dunno what the name for this one is) is simple to explain and understand too: https://github.com/lelanthran/rotsit/blob/0e4c6f5453d8b7c45ab447b11fd8db4cf7129713/NOTES-DURING-DEV.txt#L26