是否存在从表达式中提取子表达式的算法？

Question

假设我的表达式是：

v = ((((x * 3) * y) * 5) * z) + 5

而且我想通过将子表达式移动到不同的变量中来尽可能减少 v 中的操作量，但保持 y 必须只出现在 v 中，如：

a = x * 3
b = 5 * z
v = ((a * y) * b) + 5

有算法可以实现吗？

Answer 1

如果程序仅限于带有加、减、次的直线程序，那么您可以将 v 的值确定为 y 中的多项式，并使用 Horner 方法对其进行计算。

这里有一些粗略的 Python 作为说明。

import operator


class Formula:
    def __init__(self, s=0):
        self.s = str(s)

    def __repr__(self):
        return "Formula({!r})".format(self.s)

    def __str__(self):
        return self.s

    def __add__(self, other):
        if isinstance(other, int):
            other = Formula(str(other))
        if not isinstance(other, Formula):
            return NotImplemented
        if other.s == "0":
            return self
        return Formula("({}) + ({})".format(self, other))

    def __radd__(self, other):
        return self + other

    def __mul__(self, other):
        if isinstance(other, int):
            other = Formula(str(other))
        if not isinstance(other, Formula):
            return NotImplemented
        if other.s == "0":
            return 0
        if other.s == "1":
            return self
        return Formula("({}) * ({})".format(self, other))

    def __rmul__(self, other):
        return self * other


class Polynomial:
    def __init__(self, *coefs):
        self.coefs = coefs

    def print_program(self):
        v = 0
        for i, coef in enumerate(reversed(self.coefs)):
            c = Formula("c{}".format(i))
            print("{} = {}".format(c, coef))
            v *= Formula("y")
            v += c
        print("v = {}".format(v))

    def __add__(self, other):
        if isinstance(other, int):
            other = Formula(other)
        if isinstance(other, Formula):
            other = Polynomial(other)
        if not isinstance(other, Polynomial):
            return NotImplemented
        coefs = list(map(operator.add, self.coefs, other.coefs))
        if len(self.coefs) > len(other.coefs):
            coefs.extend(self.coefs[len(other.coefs) :])
        if len(other.coefs) > len(self.coefs):
            coefs.extend(other.coefs[len(self.coefs) :])
        return Polynomial(*coefs)

    def __radd__(self, other):
        return self + other

    def __mul__(self, other):
        if isinstance(other, int):
            other = Formula(other)
        if isinstance(other, Formula):
            other = Polynomial(other)
        if not isinstance(other, Polynomial):
            return NotImplemented
        coefs = [0] * (len(self.coefs) + len(other.coefs) - 1)
        for i, ci in enumerate(self.coefs):
            for j, cj in enumerate(other.coefs):
                coefs[i + j] += ci * cj
        return Polynomial(*coefs)

    def __rmul__(self, other):
        return self * other


x = Formula("x")
y = Polynomial(0, 1)
z = Formula("z")

v = ((((x * 3) * y) * 5) * z) + 5
v.print_program()

输出为

c0 = (((x) * (3)) * (5)) * (z)
c1 = 5
v = ((c0) * (y)) + (c1)

是否存在从表达式中提取子表达式的算法？

Does an algorithm for extracting sub expressions from an expression exist?

algorithm

math

expression

mathematical-optimization

compiler-optimization