您能否指出一种算法，该算法采用（二进制）解析树来评估单个变量中的多项式表达式，并返回一个等效的解析树，该解析树根据霍纳规则评估多项式。
预期的用例在表达式模板中。这个想法是，对于一个矩阵x，解析树从
a + bx + c * x*x + d * x*x*x...
会被优化成对应的解析树
a + x *( b + x( c + x*d))
问问题
1002 次
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)为相同的子树（如果为 1，则将子树替换为）N(k+1)jj-kkx^kx
然后再次应用该算法（*），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) 更复杂
于 2012-06-21T12:47:07.577 回答
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
whereA和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))
于 2012-06-21T15:55:18.790 回答
1
您可以通过递归函数获得树的单项式系数。转换这些系数并根据霍纳定律得到一个表达式很简单。
我可以给你一个简单的递归函数来计算这些值，即使可能存在一个更有效的函数。
理论的东西
首先，让我们制定表达式。一个表达式E：
E = a0 + a1x + a2x^2 + ... + anx^n
可以写成 (n+1) 元组：
(a0, a1, a2, ..., an)
然后，我们定义两个操作：
加法：给定两个表达式
E1 = (a0, ..., an)andE2 = (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第 th 个元素由（使用 C-ish 语法）计算：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第 th 个元素由下式计算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迭代，同时还必须满足以下条件：0i
j <= n (because of one[j])
i-j <= m (because of other[i-j]) ==> j >= i-m
因此，j可以从max(0,i-m)and min(i,n)（等于nsince 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);
}
注意：此代码未经测试。它可能包含错误或错误检查不足。确保你理解它并自己实现它，而不是复制粘贴。
从这里开始，您只需要根据此函数为您提供的值构建一个表达式树。
于 2012-06-21T12:17:19.067 回答