Developing.ru

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

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

Что-то вроде следующего фрагмента (так как эта функция стопудово работать не будет (реализовать ещё не пробовал), просьба считать её псевдокодом ):


string deriv (tree *root) {
if (isdigit(root->data))
return '0';
string oper = root->data;
switch (oper[0]) {
case 'x': return '1';
case '+':
case '-': return deriv(root->left) + oper + deriv(root->right);
case '*': '(' + deriv(root->left) + ")*(" + str(root->right) + ")+(" + deriv(root->right) + ")*(" + str(root->left) + ')';
case '/': "((" + deriv(root->left) + ")*(" + str(root->right) + ")-(" + deriv(root->right) + ")*(" + str(root->left) + "))/((" + str(root-right) + ")*(" + str(root-right) + "))";
default : return oper + '(' + str(root-left) + ")*(" + deriv(root->right) + ')';
}
}
где string str(tree *root) {...} - функция перевода дерева в строчку, а root->data типа string.

Больше специфики. Функция - полином?

Производную функции sin(1/x)*e^x/ ln x * J0(x) * delta
где J0 - бессель а delta - дельта-функция дирака оно тоже будет
находить?

Для того, чтобы работать с полиномами, возьмите PCCTS, там есть ПРИМЕР разбора полинома.

Нет, функция - не полином

Тоды надо:

1. Трясти спецификацию, типа как именно представлена функция. А именно - какие функции там могут содержаться.

2. Описывать грамматику разбора мат. выражения. Чтобы облегчить задачу, можно уже готовую грамматику PCCTS взять за основу и туда добавлять то, что надо (sin/cos/exp/ln)