Вычислитель маленького языка с мемоизацией

Программа program — список определений функций вида ИМЯ(П1, П2, …) = ВЫРАЖЕНИЕ (параметров один или больше). Выражение:

• if A ОП B then X else Y, где ОП — <, <=, >, >=, == или !=; вычисляется только выбранная ветка; else относится к ближайшему if, а ветка тянется до конца выражения;
• иначе арифметика: + и - (слабее), *, /, % (сильнее), операции одного уровня выполняются слева направо; унарный минус; скобки; целые неотрицательные числа; имена параметров; вызовы ИМЯ(выр, выр, …). / — деление с округлением вниз, % — остаток; в тестах их операнды неотрицательны, а делитель положителен. Пробелы между элементами необязательны.

Вызовы функций программы мемоизируются: результат для одного и того же имени с теми же аргументами вычисляется один раз за весь вызов evaluate и дальше берётся из памяти, в том числе в следующих запросах. Каждый запрос в queries — выражение без параметров. Верните для каждого запроса [значение, вычисления], где «вычисления» — сколько раз во время этого запроса вычислялось тело какой-нибудь функции (промахи памяти).

Программы корректны, рекурсия заканчивается, глубина вызовов не больше 100, все промежуточные значения по модулю меньше 10¹⁵.

Пример: ["fib(n) = if n < 2 then n else fib(n - 1) + fib(n - 2)"], ["fib(10)", "fib(12)"] → [[55, 11], [144, 2]].

Источник: задача CodeShare