algorithm - 根据霍纳方案，将多项式的解析树转换为其评估的解析树

Question

能否请您指出一种算法，该算法采用(二元)解析树来评估单个变量中的多项式表达式，并返回根据霍纳规则评估多项式的​​等效解析树。

预期的用例是在表达式模板中。这个想法是，对于矩阵 x 从

获得的解析树

a + bx + c * x*x + d * x*x*x...

会被优化成相应的解析树

a + x *( b + x( c + x*d))

Answer 1

您可以使用以下转换。

假设:多项式的解析树按指数递增的顺序排列——如果这个假设不成立，可以在解析树中交换部分多项式以使假设成立

假设:解析树包含变量的指数形式(例如 x^2)而不是乘法形式(例如 x*x ), x^0 除外——简单的转换可以在两个方向之间转换

假设:多项式中的系数(如果常数)不为零——这是为了避免必须处理 (a+0*x+c*x^2 -> a+x(cx) 而不是 a+cx^2)

a+b*x^1+c*x^2+d*x^3 的解析树:

  .+..
 /    \
a   ...+....
   /        \
  *         .+..
 / \       /    \
b  ^      *      *
  / \    / \    / \
 x   1  c   ^  d   ^
           / \    / \
          x   2  x   3

转换为a+x(b+c*x^1+d*x^2)

  +
 / \
a   *
   / \
  x   +
     / \
    b   .+..
       /    \
      *      *
     / \    / \
    c   ^  d   ^
       / \    / \
      x   1  x   2

转换为a+x(b+x(c+d*x^1))

  +
 / \
a   *
   / \
  x   +
     / \
    b   *
       / \
      x   +
         / \
        c   *
           / \
          d   ^
             / \
            x   1

最后 (a+x(b+x(c+d*x))):

  +
 / \
a   *
   / \
  x   +
     / \
    b   *
       / \
      x   +
         / \
        c   *
           / \
          d   x

常见的转换是:

 .            ->    .
  .           ->     .
   .          ->      .
    +         ->      .*..
   / \        ->     /    \
  *   N(k+1)  ->    ^      +
 / \          ->   / \    / \
ck  ^         ->  x   k  ck  N'(k+1)
   / \        -> 
  x   k       -> 

其中 N'(k+1) 是与 N(k+1) 相同的子树，每个指数 j 替换为 j-k(如果k为1，将x^k子树替换为x)

然后算法再次应用 (*) 在 N'(k+1) 上，直到它的根是 *(而不是 + ), 表明达到了最终的部分多项式。如果最后的指数为 1，则将指数部分替换为 x (x^1 -> x)

(*) 这里是递归部分

注意:如果您累积跟踪 N(k+1) 子树中的指数变化，则可以将最后两个步骤放在一起来转换 N(k+1)一次递归

注意:如果你想允许负指数，那么要么

a) 提取最高的负指数作为第一项:

a*x^-2 + b*x^-1 + c + d*x + e*x^2  ->  x^-2(a+b*x+c*x^2+d*x^3+d*x^4)

并应用上述转换

或 b) 将等式的正指数部分和负指数部分分开，分别对每个部分应用上述变换(您需要“翻转”负指数部分的操作数，并将乘法替换为除法):

a*x^-2 + b*x^-1 + c + d*x + e*x^2  ->  [a+x^-2 + b*x-1] + [c + d*x + e*x^2] ->
-> [(a/x + b)/x] + [c+x(d+ex)]

这个方法看起来比a)复杂