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

Question

Suppose I had the expression:

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

And I want to reduce the amount of operations as much as possible in v by moving sub expressions into different variables, yet maintaining that y must only occur in v, such as:

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

Is there an algorithm that can achieve this?

Answer 1

If the programs are limited to straight-line programs with plus, minus, times, then you could determine the value of v as a polynomial in y and evaluate it using Horner's method.

Here's some rough Python by way of illustration.

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()

The output is

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