为值和数学运算列表查找（或强制）数学表达式

Question

所以我有一个包含一些值的列表，例如[230, 67, 34, 60, 2, 10]
还有一个操作列表[operations.add, operations.sub, operations.mul, operations.div]和result number，我事先就知道了。你知道吗

找到所有可能给出结果的数学表达式的最佳方法是什么。你知道吗

例如，如果结果是154，则一种可能的解决方案是60*2+34。你知道吗

我在设计这个算法时遇到的问题是，我事先不知道表达式将使用哪些值和运算，哪些不使用，或者可能全部使用。
如果您能提供一些python代码，我们将不胜感激。
提前谢谢

Answer 1

您可以创建一个表示所有可能组合的树，其中一个节点表示数字或运算符。然后，通过对生成的树执行DFS或BFS，您可以找到所有节点，这样由从根到节点的路径表示的表达式计算出所需的值。下面是Python中的代码：

class Node():
    def __init__(self, type, val, parent, children):
        self.type = type
        self.value = val
        self.parent = parent
        self.children = children
        self.total = None


def expandBranch(node, numList, opList):

    if len(numList) == 0:
        return

    if node.type == "Operator" or node.type is None:
        for i in range(len(numList)):
            newList = numList[:]
            num = newList.pop(i)
            newNode = Node("Number", num, node, [])
            node.children.append(newNode)
            expandBranch(newNode, newList, opList)
    else:
        for op in opList:
            newNode = Node("Operator", op, node, [])
            node.children.append(newNode)
            expandBranch(newNode, numList, opList)


def dfs(node, result):

    if len(node.children) == 0:
        return

    if node.type == "Number":
        if node.parent.type == None:
            node.total = node.value
        elif node.parent.value == "+":
            node.total = node.parent.total + node.value
        elif node.parent.value == "-":
            node.total = node.parent.total - node.value
        elif node.parent.value == "*":
            node.total = node.parent.total * node.value
        elif node.parent.value == "/":
            node.total = node.parent.total / node.value
        else:
            pass # should never come here
        if node.total == result:
            output = []
            while node.parent is not None:
                output.insert(0, node.value)
                node = node.parent
            print(output)
            return
    elif node.type == "Operator":
        node.total = node.parent.total
    else:
        pass # root node, nothing to do

    for child in node.children:
        dfs(child, result)


def main():
    nums = [230, 67, 34, 60, 2, 10]
    ops = ["+", "-", "*", "/"]
    root = Node(None, None, None, [])
    expandBranch(root, nums, ops)
    dfs(root, 154)

if __name__ == "__main__":
    main()

输出：

[230, '+', 10, '/', 2, '+', 34]
[67, '+', 10, '*', 2]
[67, '*', 10, '/', 230, '*', 60, '+', 34]
[67, '/', 230, '+', 60, '*', 2, '+', 34]
[67, '/', 230, '+', 2, '*', 60, '+', 34]
[34, '-', 67, '*', 2, '+', 230, '-', 10]
[34, '-', 67, '*', 2, '-', 10, '+', 230]
[34, '-', 2, '*', 67, '/', 10, '-', 60]
[34, '/', 230, '+', 67, '+', 10, '*', 2]
[34, '/', 230, '+', 10, '+', 67, '*', 2]
[34, '/', 60, '+', 67, '+', 10, '*', 2]
[34, '/', 60, '+', 10, '+', 67, '*', 2]
[34, '/', 2, '+', 67, '+', 60, '+', 10]
[34, '/', 2, '+', 67, '+', 10, '+', 60]
[34, '/', 2, '+', 60, '+', 67, '+', 10]
[34, '/', 2, '+', 60, '+', 10, '+', 67]
[34, '/', 2, '+', 10, '+', 67, '+', 60]
[34, '/', 2, '+', 10, '+', 60, '+', 67]
[60, '*', 2, '+', 34]
[60, '/', 230, '+', 67, '+', 10, '*', 2]
[60, '/', 230, '+', 10, '+', 67, '*', 2]
[60, '/', 34, '+', 230, '-', 67, '-', 10]
[60, '/', 34, '+', 230, '-', 10, '-', 67]
[60, '/', 34, '-', 67, '+', 230, '-', 10]
[60, '/', 34, '-', 67, '-', 10, '+', 230]
[60, '/', 34, '-', 10, '+', 230, '-', 67]
[60, '/', 34, '-', 10, '-', 67, '+', 230]
[60, '/', 34, '*', 67, '+', 10, '*', 2]
[60, '/', 34, '*', 10, '+', 67, '*', 2]
[2, '*', 60, '+', 34]
[10, '+', 230, '/', 2, '+', 34]
[10, '+', 67, '*', 2]
[10, '*', 67, '/', 230, '*', 60, '+', 34]
[10, '/', 230, '+', 60, '*', 2, '+', 34]
[10, '/', 230, '+', 2, '*', 60, '+', 34]
[10, '/', 67, '+', 60, '*', 2, '+', 34]
[10, '/', 67, '+', 2, '*', 60, '+', 34]

代码相当粗糙，可能需要改进。注意，整数除法将出现在代码中。另外请注意，当您向原始列表中添加更多数字时，程序将以指数级的速度变慢。你知道吗