Решатель формул сам по себе очень интересная тренировка, и в определённый момент эта тренировка может очень пригодиться в другой задаче – конструировании новой формулы, автоматической её проверке (погрешность, просчёт значений по списку координат)… И excel вам не поможет, да и неспортивно.
Сразу оговорюсь — код сделан для ЛИСПа образца 87 года, и свежий Common LISP его категорически не поймёт, что печально… Но — 2 шага от ЛИСП-кода до понимания, как то же самое написать в более пристойном для практической задаче С# или Delphi, в ЛИСПе даётся более милое моему сердцу и глазу исполнение)
Ввод формулы с клавиатуры, против жёсткого задания в коде, имеет массу плюсов. Как осуществить его программист задумывался, пожалуй, со школьного железного стула. Задача велика, и кажется невыполнимой, но главное – начать. Начинаем>>
Обычная запись для первого шага излишне сложна. Польская форма записи – воспользуемся ей. И операции над числами запишутся в виде списков, которыми можно задать самое сложное математическое выражение:
#
Напишем решатель (solver) в рево… рекурсивном духе ЛИСПа: он будет хватать из списка первый элемент голову, и далее обрабатывать хвост в соответствии со значением головы. На вход решатель получает каждый раз формулу (a), результат предыдущего действия (b), знак © и, если предусмотреть это заранее, то и значения неизвестных параметров (xx).
Неизвестные параметры, указанные в формуле своими именами # (+ x 5)) должна заменить на значения соответствующая функция. Причём до решателя. Обзовём её предрешатель (presolver), на вход ей подаём формулу, результат (при вызове из решателя – NIL) и значение неизвестной для подстановки на место элемента ‘х’ (выделяю здесь это специально, ибо ЛИСП не различает, хвала Господу, типов данных)
И – наличие неизвестных ещё нужно подтвердить. Рождается функция поиска неизвестной, searchx, a заодно и функция реверса списка revers, ибо результат presolver-a по-умолчанию выходит задом наперёд.
Запускаем-проверяем-
-ура-работает. Но – только на простых формулах, со списками без вложенных списков, с элементами-атомами.
Можно долго думать, каким интересным образом превратить простой солвер в сложный, но мы пойдём более рациональным путём – не будем трогать работающий кусок, а станем заниматься проектом solver2 – решателем сложных формул.
Каждая сложная формула содержит в себе хотя бы один элемент-список. Но начнём с проблемы совместимости, чтобы новая функция работала хотя бы для простых вычислений. Для этого нужно формулу на вход проверить на простоту, и если простая – отправить к solver-у, а вот если сложная – подумать над ней ещё немного.
Определить прост список или не совсем поможет функция iseasy с единственным входным параметром – собственно формулой. Iseasy видит элемент не-атом – и выпадает с ответом NIL
Далее всё просто, и одновременно изящно-непонятно. Правильность работы функции очевидна, но неочевиден алгоритм. Он же таков:
— Сначала solver2 проверяет формулу целиком на простоту. Если формула проста целиком, её можно и нужно решить solver-ом.
— Далее идёт проверка – «а не атом ли голова у формулы ‘а’?» Если голова – атом бренный, то отправляем solver-у конструктор из этого атома и хвоста, требующего повторного рассмотрения solver2
— Если первые 2 проверки не прошли, что-то с формулой определённо не так (кажется и мне через 2 года после написания кода), то мы должны проверить голову формулы на простоту, и если таковая проста (НО не атом! – а значит список), отправим запустившей solver2 функции конструкцию из решённой головы и рассмотренного повторно solver2 хвоста формулы. Например, «на экран»… Наверное, это какой-то bugreport?
— Если первые 3 проверки не прошли (совсем беда, это значит что формула не проста, в голове этой формулы стоит не атом (т.е. не знак ±/*/:), и даже не список из атомов, выдадим «на экран» конструкцию из просмотренной повторно solver2 головы и хвоста, также с ревизией solver2
Запустите…
Удивитесь
Очевидно, что solver2 в приведённом коде умеет считать простые формулы. Но как, запустив его, он считает и сложные? Зрение в рекурсивном программировании весьма обманчиво.
Каждая правильная формула начинается с атома операции. Проследи за действиями ЛИСПа, читатель: solver2 начинает решать правильную сложную формулу, и отправляет на решатель конструкцию из головы этой формулы (знак), и… пересмотренного хвоста в самом себе. Хвост приходит на solver2 и, естественно, не содержит в голове атома операции. Поэтому заслуженно отправляется на дальнейшее упрощение solver2…
В чём его суть, что он делает, этот solver2? В общем-то ничего, ещё проще — он берёт список и заменяет его на число… В конце концов любая сколь угодно длинная формула, даже с 10-кратной вложенностью свернётся до простого списка, со знаком в голове и с хвостом, состоящим из одних только атомов, причём все атомы будут числами. Красиво, и абсолютно непостижимо по коду, непостижимо и на первом шаге написания функции)… За что РП и люблю.
Сразу оговорюсь — код сделан для ЛИСПа образца 87 года, и свежий Common LISP его категорически не поймёт, что печально… Но — 2 шага от ЛИСП-кода до понимания, как то же самое написать в более пристойном для практической задаче С# или Delphi, в ЛИСПе даётся более милое моему сердцу и глазу исполнение)
Ввод формулы с клавиатуры, против жёсткого задания в коде, имеет массу плюсов. Как осуществить его программист задумывался, пожалуй, со школьного железного стула. Задача велика, и кажется невыполнимой, но главное – начать. Начинаем>>
1. Как будет записываться формула?
Обычная запись для первого шага излишне сложна. Польская форма записи – воспользуемся ей. И операции над числами запишутся в виде списков, которыми можно задать самое сложное математическое выражение:
#
2+3->(+ 2 3)
2-3->(- 2 3)
2*3->(* 2 3)
2/3->(/ 2 3)
2+3+5->(+ 2 3 5)
2+3*5->(+ 2 (* 3 5))
(2+3)*5->(* (+ 2 3) 5)
2. Как оно будет работать? (простые формулы)
Напишем решатель (solver) в рево… рекурсивном духе ЛИСПа: он будет хватать из списка первый элемент голову, и далее обрабатывать хвост в соответствии со значением головы. На вход решатель получает каждый раз формулу (a), результат предыдущего действия (b), знак © и, если предусмотреть это заранее, то и значения неизвестных параметров (xx).
(defun solver (a b c xx)
((null a) b)
((equal (searchx a) NIL) (solver (presolver a NIL xx) T c xx))
((eq (atom a) T) a)
((equal c NIL) (solver (cdr (cdr a)) (car (cdr a)) (car a) xx))
((equal c ps) (solver (cdr a) (+ b (car a)) c xx))
((equal c ms) (solver (cdr a) (- b (car a)) c xx))
((equal c mu) (solver (cdr a) (* b (car a)) c xx))
((equal c di) (solver (cdr a) (/ b (car a)) c xx))
)
Неизвестные параметры, указанные в формуле своими именами # (+ x 5)) должна заменить на значения соответствующая функция. Причём до решателя. Обзовём её предрешатель (presolver), на вход ей подаём формулу, результат (при вызове из решателя – NIL) и значение неизвестной для подстановки на место элемента ‘х’ (выделяю здесь это специально, ибо ЛИСП не различает, хвала Господу, типов данных)
(defun presolver (a b xx)
((null a) (revers b))
((eq (car a) x) (presolver (cdr a) (cons xx b) xx))
((eq (equal (car a) x) NIL) (presolver (cdr a) (cons (car a) b) xx))
)
И – наличие неизвестных ещё нужно подтвердить. Рождается функция поиска неизвестной, searchx, a заодно и функция реверса списка revers, ибо результат presolver-a по-умолчанию выходит задом наперёд.
(defun searchx (a)
((null a) T)
((equal (car a) x) NIL)
(searchx (cdr a))
)
(defun revers (a b)
((null a) b)
(revers (cdr a) (cons (car a) b))
)
Запускаем-проверяем-
(solver '(ps x 2 3) NIL NIL 5)-ура-работает. Но – только на простых формулах, со списками без вложенных списков, с элементами-атомами.
3. Как оно будет работать-2? (сложные формулы)
Можно долго думать, каким интересным образом превратить простой солвер в сложный, но мы пойдём более рациональным путём – не будем трогать работающий кусок, а станем заниматься проектом solver2 – решателем сложных формул.
(defun solver2 (a xx)
((eq (iseasy a) T)
(solver a NIL NIL xx))
((eq (atom (car a)) T)
(solver (cons (car a) (solver2 (cdr a) xx)) NIL NIL xx))
((eq (iseasy (car a)) T)
(cons (solver (car a) NIL NIL xx) (solver2 (cdr a) xx)))
((eq (iseasy (car a)) NIL)
(cons (solver2 (car a) xx) (solver2 (cdr a) xx)))
)
Каждая сложная формула содержит в себе хотя бы один элемент-список. Но начнём с проблемы совместимости, чтобы новая функция работала хотя бы для простых вычислений. Для этого нужно формулу на вход проверить на простоту, и если простая – отправить к solver-у, а вот если сложная – подумать над ней ещё немного.
Определить прост список или не совсем поможет функция iseasy с единственным входным параметром – собственно формулой. Iseasy видит элемент не-атом – и выпадает с ответом NIL
(defun iseasy (a)
((null a) T)
((equal (atom (car a)) Nil) NIL)
(iseasy (cdr a))
)
Далее всё просто, и одновременно изящно-непонятно. Правильность работы функции очевидна, но неочевиден алгоритм. Он же таков:
— Сначала solver2 проверяет формулу целиком на простоту. Если формула проста целиком, её можно и нужно решить solver-ом.
— Далее идёт проверка – «а не атом ли голова у формулы ‘а’?» Если голова – атом бренный, то отправляем solver-у конструктор из этого атома и хвоста, требующего повторного рассмотрения solver2
— Если первые 2 проверки не прошли, что-то с формулой определённо не так (кажется и мне через 2 года после написания кода), то мы должны проверить голову формулы на простоту, и если таковая проста (НО не атом! – а значит список), отправим запустившей solver2 функции конструкцию из решённой головы и рассмотренного повторно solver2 хвоста формулы. Например, «на экран»… Наверное, это какой-то bugreport?
— Если первые 3 проверки не прошли (совсем беда, это значит что формула не проста, в голове этой формулы стоит не атом (т.е. не знак ±/*/:), и даже не список из атомов, выдадим «на экран» конструкцию из просмотренной повторно solver2 головы и хвоста, также с ревизией solver2
Запустите…
(solver2 '(mu (ps x 2 3) (ms x 5)) 10)Удивитесь
4. Почему оно работает? (заключение)
Очевидно, что solver2 в приведённом коде умеет считать простые формулы. Но как, запустив его, он считает и сложные? Зрение в рекурсивном программировании весьма обманчиво.
Каждая правильная формула начинается с атома операции. Проследи за действиями ЛИСПа, читатель: solver2 начинает решать правильную сложную формулу, и отправляет на решатель конструкцию из головы этой формулы (знак), и… пересмотренного хвоста в самом себе. Хвост приходит на solver2 и, естественно, не содержит в голове атома операции. Поэтому заслуженно отправляется на дальнейшее упрощение solver2…
В чём его суть, что он делает, этот solver2? В общем-то ничего, ещё проще — он берёт список и заменяет его на число… В конце концов любая сколь угодно длинная формула, даже с 10-кратной вложенностью свернётся до простого списка, со знаком в голове и с хвостом, состоящим из одних только атомов, причём все атомы будут числами. Красиво, и абсолютно непостижимо по коду, непостижимо и на первом шаге написания функции)… За что РП и люблю.
