Freemat. Добавим функциональности

Недавно, просматривая список функций в FreeMat, я заметил там упоминание о массиве ячеек, отдалённо напоминающем списки из Lisp-а. И появилось желание попробовать сделать что-нибудь для работы с символьными выражениями... например, функцию для дифференцирования функции аналитически... Итак, дайте бубен, будут танцы! :)

Для упрощения задачи введём следующие ограничения: рассматриваются арифметические операции типа +, -, *, /, а также функции с одним аргументом: sin, cos, exp, log (натуральный логарифм). Набор функция при желании можно расширить. Также будем считать, что в арифметических операция участвуют 2 аргумента, т.е. отрицательное число -x должно быть записано в виде  0-x. Сильно вдоваться в алгоритмы не буду, кому интересно, можете посмотреть второй том "Введения в мир Lisp", в частности, описание Maxim-ы и вычисления производной.

Представлю сразу итоговую функцию:

Из неё видно, что для решения поставленной задачи я сначала разбиваю выражение на составляющие (токены), преобразую их постфиксную (обратную польскую) нотацию, затем формирую древовидную структуру, применяю к ней алгоритм дифференцирования и преобразую результат в строку в обычной (инфиксной) форме. 

Функция str2cell() получает на вход строку, содержащую математическое выражение и разбивает его на составляющие, возвращая результат в виде массива ячеек со строками. Самым простым способом реализации в FreeMat будет использование регулярных выражений.

Регулярное выражение в данной функции распознаёт подстроки 3-х типов:

(\w+) - слова,

(\d+(\.\d+)?((e|E)(\+|\-)?\d+)?) - числа целые и с плавающей точкой, но без знака,

([^\w\s]) - одиночные разделители (знаки операций, скобки).

Далее следует преобразование инфиксного порядка следования в постфиксный, для чего служит следующая функция.

Сначала подготавливается стек и пустой выходной список. Затем список токенов последовательно анализируется, и если это константа или переменная, сразу помещается в выходной список (выражение список{end+1} добавляет ячейку в конец и помещает в неё значение), если знак операции или функция, то из стека извлекаются более приоритетные операции, а затем текущий знак сам помещается в стек, открывающая скобка также отправляется в стек, а закрывающая приводит к извлечению из стека всех операций до следующей открывающей скобки. Приоритет и количество операция определяет функция operations() :

Самый низкий приоритет имеют переменные и константы (в принципе, они могут вообще не учитываться), самый высокий - функции.
В преобразованиях используется стек, который эмулируется также на основе списка ячеек. Для работы с ним определены следующие функции.
1) инициализация стека

2) помещение значения

3) извлечение значения

4) считывание "верхнего" значения без извлечения

Обратите внимание на амперсанд (&) перед именем стека, он позволяет передавать аргументы по ссылке, т.е. изменять сам передаваемый объект, а не его копию.

Далее постфиксная последовательность токенов преобразуется в дерево.

Здесь данные последовательно записываются в стек, если встречается знак операции или функция, соответствующее количество аргументов извлекается из стека, преобразуется в отдельный массив строк либо, при возможности, вычисляется функцией simplify(), и результат возвращается в стек. После всех итераций в стеке остаётся только одно значение, которое и считывается в конце. 

Функция simplify() определяет, когда выражение состоит из чисел и определяет его значение с помощью встроенной функции eval().

Сейчас немного поговорим о списках. В отличие от Lisp, у нас имя функции (оператора) стоит в конце списка, отчасти потому, что так получилось при формировании постфиксной нотации, отчасти, т.к. в конец массива ячеек FreeMat добавить значение проще всего... Этот момент нужно помнить при применении лисповских алгоритмов. Собственно, дифференцирование будет заключаться в замене одних выражений другими по следующим правилам:

(x y +)' -> (x' y' +)

(x y *)' -> ((x' y *) (x y' *) +)

(x y /)' -> (((x' y *) (x y' * ) -) (y y *) /)

(x f)'   -> (x' (x f') *)

Здесь апостраф обозначает дифференцирование. Вот что получится в итоге.

Собственно, всю работу выполняет функция rdiff(), которая рекурсивно вызывает себя для каждого листа нашего дерева и выполняет замену в соответствии с перечисленными выше правилами. Функция diff_tree() осталась после отладки, я не стал её удалять, т.к. она имеет более говорящее название, однако без неё вполне можно было обойтись. Подстановку для производных функций осуществляет dstr(), определённая в этом же файле.

Также обратите внимание на использовании функции try_simp(). Её код я не привожу, т.к. идея тривиальна, а реализация не умещается на экране моего нетбука)) Её назначение в применении преобразований типа "x + 0 = x", "x * 1 = x" и т.п. 

Наконец, необходимо преобразовать полученное дерево в удобочитамую (более-менее) строку. Данная задача решается следующей функцией.

Здесь также происходит рекурсивный обход дерева с одновременной заменой постфиксных списков инфиксными строками. Результат не будет идеально удобен для восприятия, но компьютер его поймёт. 

Итак, всё готово, можно проверить. 

Все описанные функции можно найти по данной ссылке. Удачи!)