Вычисление значения выражения, заданного в виде дерева - Lisp

Формулировка задачи:

Арифметическое выражение представлено в виде дерева (листья обозначают целые числа, прочие узлы операции). Написать программу вычисления такого выражения.

Решение задачи: «Вычисление значения выражения, заданного в виде дерева»

Листинг программы

;; racket-lang.org
(define (foo op)
  (match op
    ('+ +)
    ('- -)
    ('* *)
    ('/ /)))
 
(define (eval tree)
  (if (list? tree)
      (apply (foo (car tree)) (map eval (cdr tree)))
      tree))
 
(eval '(+ (/ 4 2) (- (* 3 4) 7)))
;7

Объяснение кода листинга программы

В данном коде на языке Lisp реализована функция eval, которая вычисляет значение выражения, заданного в виде дерева. Алгоритм работы функции eval следующий:

Если переданное значение tree является списком, то функция eval вызывает саму себя, применяя функцию foo к первому элементу списка и передавая ей в качестве аргумента результат вызова eval для остальных элементов списка.
Если переданное значение tree не является списком, то функция eval возвращает его без изменений. В данном коде определена также вспомогательная функция foo, которая принимает в качестве аргумента оператор и возвращает результат вычисления соответствующей операции: сложения, вычитания, умножения или деления. В основной функции eval происходит вызов функции foo с оператором /, так как в переданном выражении присутствует деление. Результатом вычисления будет число 7.