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