所以我试图创建一个算法来执行符号微分,以获得给定函数的确切导数。我选择了反向波兰表示法来存储表达式,因为它节省了构建实际表达式树的空间和时间。我将用一个具体的例子来说明我的问题,我将手工淡化我的算法;所以,如果你想要一个简单的问题,或者对答案没有任何线索,请停止阅读并离开(我不需要对这个问题进行盲目的投票)。
Example:
Find the derivative of: F=x^3+2*x^2+x
1) Convert F to RPN form results in: x3^2x2^*+x+
2) I'll store RPN in stack as follows:
---
|+|
---
|x|
---
|+|
---
|*|
---
|^|
---
|2|
---
|x|
---
|2|
---
|^|
---
|3|
---
|x|
---
This is basically the post-order traversal of the expression tree for the F expression. For now I'm focusing on kind of simple derivation rules.
2) Pop stack (Should be an operator): [+] Rule: op0[+]op1 := d[op0]+d[op1] -> d[op0]d[op1]+
3) Get op0 (POP): [x] Rule: x := d[x] -> 1
4) APPLY: [1]
5) Get op1 (POP): [+] Rule: op0[+]op1 := d[op0]+d[op1] -> d[op0]d[op1]+
6) Get op0 (POP): [*] Rule: op0[*]op1 := d[op0]*op1+op0*d[op1] -> d[op0]op1*op0d[op1]*+
7) Get op0 (POP): [^] Rule: op1[^]op0 := op1*op0^op1-1 -> op1op0op11-^*
8) Get op1 (POP): [2]
9) Get op0 (POP): [x]
10) APPLY: [1|2|x|2|1|-|^|*]
11) Get op1 (POP): [2]
12) APPLY: // How can I apply the multiplication operator now?
所以如果我的想法是正确的,我有以下堆栈:[2|x|2|1|-|^|]是第一个操作数,[2]是第二个操作数。现在我必须执行[2|x|2|1|-|^|][2],这需要我递归这个函数。因为现在我还要对[2|x|2|1|-|^|]进行推导。在这种情况下,我还必须将每个操作节点的结果存储在不同的堆栈中,并以正确的顺序合并它们。
谁能推荐一种更有效的方法?
对于简单的多项式,我喜欢找到一个非常短的正则表达式解决方案的想法,但结果比我希望的要长…(示例JavaScript):
function dx(dt){
dt = dt.replace(/s+/g,"");
var signs = dt.match(/[+-]/g) ? dt.match(/[+-]/g) : [],
dts = dt.split(/[+-]/).map(function(x){
return x.replace(/([0-9]+)?(*)?([a-zA-Z])?(^)?([0-9]+)?/,
function(z,a,b,c,d,e){
if (!c){
return "0";
}
a = a ? Number(a) : 1;
if (!e){
return "" + a;
}
e = Number(e);
return "" + (e*a) + "*" + c
+ (e - 1 > 1 ? d + (e - 1) : "");
});
});
return dts.map(function(v,i){
return v + (signs[i] ? " " + signs[i] : "");
}).join(" ").replace(/s+s0|0s+s/g,"");
}
console.log(dx("x^3+2*x^2+x"));
console.log(dx("12x"));
console.log(dx("6"));
输出:"3*x^2 + 4*x + 1"
"12"
"0"