algorithm - 符号微分算法

Question

因此，我正在尝试创建一种算法来执行符号微分，以获得给定函数的精确导数。我选择了反向波兰表示法来存储表达式，因为它节省了我构建实际表达式树的空间和时间。 我会用一个具体的例子来说明我的问题，我会手工淡化我的算法；因此，如果您期待一个简单的问题或对答案一无所知，请停止阅读并离开(我不需要对这个问题进行盲目的否决)。

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|-|^|] 进行推导。在这种情况下，我还必须将每个运算符节点的结果存储在不同的堆栈中，然后它们以正确的顺序合并它们。

有人可以推荐一种更有效的方法吗？

Answer 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|0\s\+\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"