RPN vs AST
Забавная история. Когда-то мы создали свой движок электронных таблиц (про это делал доклад в Харькове) и каждая формула представлена в движке в виде абстрактного синтаксического дерева (AST). Я когда-то делал бенчмарк для разных языков - https://github.com/koorchik/formula-evaluation-benchmark . Сегодня я вдруг задумался, почему формулы представлены в виде AST, а не в формате обратной польской записи (RPN). В целом, RPN вычисляется итеративно без рекурсии (нужен правда свой стек для операндов и результатов). Мне понравилась эта идея и начал думать, как загнать в RPN эксель формулу. Основной вопрос - функции с изменяемым количеством операндов. Решил, что буду просто в RPN хранить арность рядом с токеном операнда. Начал уже руками переписывать свое тестовое дерево в RPN, но тут решил загуглить, вдруг кто-то уже тестировал перформанс AST против RPN. И как же я удивился, что первой ссылкой нахожу гитхаб гист в котором бенчмарк на JavaScript. В гисте уже решена проблема арности и даже есть функция для конверта AST в RPN (а я хотел делать это руками). Читаю гист и тут до меня доходит, что я автор этого гиста - я 😂. Я написал этот бенчмарк больше года назад , увидел, что RPN медленее и забыл про него :)

ГИСТ - https://gist.github.com/koorchik/9717b893ae2134e21dbe

Относительно перформанса, то можно RPN вариант ускорить, но он все равно не будет быстрее, чем AST (это касается только JS имплементации).