logo标签列表

将一个多项式的语法树转换为其按Horner方案计算的解析树

algorithmexpression-treescompiler-optimizationparse-treeexpression-templates
3

请问是否能提供一种算法，该算法可以接受一个（二进制）解析树以计算单变量多项式表达式，并返回一个等效的解析树，使得该解析树可根据Horner规则来求解该多项式表达式。

预期使用情况是在表达式模板中。想法是对于矩阵x，从以下解析树中获得：

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

将被优化为相应的解析树

a + x *( b + x( c + x*d))
这个表达式是不是单项式基？ - Shahbaz
@Shahbaz 不完全正确，因为它作为带有+和*操作的解析树可用。 - san
算法是离线的吗？它应该有多高效？ - Shahbaz
@Shahbaz，这本质上是一个优化过程，将在多次多项式求值中分摊。因此，它不需要非常快。也许最好的方法是从树中获取单项式系数，然后使用标准的Horner方法。 - san
我相信如果你将表达式展开为单项式，那么应用霍纳法则就会变得轻而易举。 - Shahbaz
显示剩余4条评论
3个回答
3
您可以使用以下转换方法。
假设：多项式的解析树按照指数递增的顺序排列。如果此假设不成立，则可以在解析树中交换部分多项式以使该假设成立。
假设：解析树包含变量的指数形式（例如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替换x ^ k 子树）

然后在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)

方法一：应用上述变换。

方法二：将方程式中的正指数部分和负指数部分分开，并分别应用上述变换（对于负指数一侧，需要“翻转”运算数并将乘法替换为除法）。

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)更加复杂。

你在回答中付出了很多努力，因此得到了点赞，但我真正关注的是由+和*组成的表达式树。 - san
@san - 将上面的每个 x^k 替换为相应的 x*x*...*x 子树，并计算它们的数量（获取 k），或者逐个删除一个 *x（并对每个已删除的应用上述算法，使用 x）直到它们全部消失。 - Attila
@san，你不是说这棵树不是单项式形式吗？ - Shahbaz
相反，这个解决方案假定表达式已经处于单项式形式，并根据霍纳法则直接转换树。 - Shahbaz
@Shahbaz 确实。我在读行间，意识到合并连续的 '*' 可以很容易地得到“单项式”表达式树。 - san
显示剩余8条评论
2
你只需要应用以下规则，直到无法再应用为止。
((x*A)*B)     -> (x*(A*B))
((x*A)+(x*B)) -> (x*(A+B)))
(A+(n+B))     -> (n+(A+B))  if n is a number

这里需要合并的是子树 A 和 B。

以下是用 OCaml 实现此操作的代码：

type poly = X | Num of int | Add of poly * poly | Mul of poly * poly

let rec horner = function
  | X -> X
  | Num n -> Num n
  | Add (X, X) -> Mul (X, Num 2)
  | Mul (X, p)
  | Mul (p, X) -> Mul (X, horner p)
  | Mul (p1, Mul (X, p2))
  | Mul (Mul (X, p1), p2) -> Mul (X, horner (Mul (p1, p2)))
  | Mul (p1, p2) -> Mul (horner p1, horner p2) (* This case should never be used *)
  | Add (Mul (X, p1), Mul (X, p2)) -> Mul (X, horner (Add (p1, p2)))
  | Add (X, Mul (X, p))
  | Add (Mul (X, p), X) -> Mul (X, Add (Num 1, horner p))
  | Add (Num n, p)
  | Add (p, Num n) -> Add (Num n, horner p)
  | Add (p1, Add (Num n, p2))
  | Add (Add (Num n, p1), p2) -> Add (Num n, horner (Add (p1, p2)))
  | Add (p1, p2) -> horner (Add (horner p1, horner p2))
这真的很优雅和通用。你知道这三个转换是否已经在任何地方被证明是足够的吗？ - san
1

您可以通过递归函数获得树的单项式系数。根据霍纳定理将这些系数转换并得到表达式会很简单。

我可以给您一个简单的递归函数来计算这些值，尽管可能存在更有效率的方法。

理论内容

首先，让我们制定表达式E：

E = a0 + a1x + a2x^2 + ... + anx^n

可以写成一个（n+1）元组：

(a0, a1, a2, ..., an)

然后，我们定义了两个操作：

  • 加法：给定两个表达式 E1 = (a0, ..., an) 和 E2 = (b0, ..., bm)，则 E1 + E2 对应的元组为：

              {(a0+b0, a1+b1, ..., am+bm, a(m+1), ..., an) (n > m)
E1 + E2 = {(a0+b0, a1+b1, ..., an+bn, b(n+1), ..., bm) (n < m)
          {(a0+b0, a1+b1, ..., an+bn)                  (n = m)

    即，有 max(n,m)+1 个元素，第 i 个元素的计算方式为（使用类 C 语言的语法）：

    i<=n?ai:0 + i<=m?bi:0

  • 乘法：给定两个表达式 E1 = (a0, ..., an) 和 E2 = (b0, ..., bm)，则 E1 * E2 对应的元组为：

    E1 * E2 = (a0*b0, a0*b1+a1*b0, a0*b2+a1*b1+a2*b0, ... , an*bm)

    即，有 n+m+1 个元素，第 i 个元素的计算方式为：

    sigma over {ar*bs | 0<=r<=n, 0<=s<=m, r+s=i}
递归函数因此被定义如下：
tuple get_monomial_coef(node)
    if node == constant
        return (node.value)  // Note that this is a tuple
    if node == variable
        return (0, 1)        // the expression is E = x
    left_expr = get_monomial_coef(node.left)
    right_expr = get_monomial_coef(node.right)
    if node == +
        return add(left_expr, right_expr)
    if node == *
        return mul(left_expr, right_expr)

在哪里

tuple add(tuple one, tuple other)
    n = one.size
    m = other.size
    for i = 0 to max(n, m)
        result[i] = i<=n?one[i]:0 + i<=m?other[i]:0
    return result

tuple mul(tuple one, tuple other)
    n = one.size
    m = other.size
    for i = 0 to n+m
        result[i] = 0
        for j=max(0,i-m) to min(i,n)
            result[i] += one[j]*other[i-j]
    return result

注意：在实现mul时，j应该从0迭代到i，同时以下条件也必须满足：
j <= n (because of one[j])
i-j <= m (because of other[i-j]) ==> j >= i-m

因此，j 可以从 max(0,i-m) 和 min(i,n)（等于 n，因为 n <= i）开始。

C++ 实现

既然你有了伪代码，实现就不难了。对于元组类型，简单的 std::vector 就足够了。因此：

vector<double> add(const vector<double> &one, const vector<double> &other)
{
    size_t n = one.size() - 1;
    size_t m = other.size() - 1;
    vector<double> result((n>m?n:m) + 1);
    for (size_t i = 0, size = result.size(); i < size; ++i)
        result[i] = (i<=n?one[i]:0) + (i<=m?other[i]:0);
    return result;
}

vector<double> mul(const vector<double> &one, const vector<double> &other)
{
    size_t n = one.size() - 1;
    size_t m = other.size() - 1;
    vector<double> result(n + m + 1);
    for (size_t i = 0, size = n + m + 1; i < size; ++i)
    {
        result[i] = 0.0;
        for (size_t j = i>m?i-m:0; j <= n; ++j)
            result[i] += one[j]*other[i-j];
    }
    return result;
}

vector<double> get_monomial_coef(const Node &node)
{
    vector<double> result;
    if (node.type == CONSTANT)
    {
        result.push_back(node.value);
        return result;
    }
    if (node.type == VARIABLE)
    {
        result.push_back(0.0);
        result.push_back(1);  // be careful about floating point errors
                              // you might want to choose a better type than
                              // double for example a class that distinguishes
                              // between constants and variable coefficients
                              // and implement + and * for it
        return result;
    }
    vector<double> left_expr = get_monomial_coef(node.left);
    vector<double> right_expr = get_monomial_coef(node.right);
    if (node.type == PLUS)
        return add(left_expr, right_expr);
    if (node.type == MULTIPLY)
        return mul(left_expr, right_expr);
    // unknown node.type
}

vector<double> get_monomial_coef(const Tree &tree)
{
    return get_monomial_coef(tree.root);
}

注意：此代码未经测试，可能包含错误或不足的错误检查。请确保您理解它并自己实现它，而不是复制粘贴。
从这里开始，您只需要根据此函数提供的值构建表达式树即可。
是的，这个想法应该可行，已点赞。我会暂时不接受，希望有一个直接解决问题而不需要形成单项式系数元组的解决方案。 - san
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接