面对这种编程挑战，我首先尝试回答以下问题：
- 表达式应如何表示？
- 我们可以减少可能表达的数量吗？
- 我们可以减少每个表达式的工作量吗？
表示表达式
看起来像小型编程语言的问题往往使我想到Lisp。问题是要求我们生成系列：
123(* 12 3)(+ 12 3)...(- (- 1 2) 3)
基本上在3元组
(operator, left,right)中的左右位置也可以是表达式的二进制表达式。组件的顺序实际上并不重要。Python具有元组，并且在
operator模块中具有针对各种二进制操作的功能。因此，我打算以以下形式构建表达式：
(operator.sub, (operator.sub, 1, 2), 3)
然后可以使用（主要是）简单的递归函数进行评估：
def compute(expr): if isinstance(expr, tuple): op, left, right = expr return op(compute(left), compute(right)) return expr
减少可能性
从问题描述来看，似乎给定的每位数字可能有指数级的表达。我们是否可以通过创建所有排列来消除其中的某些部分？
例如，输入一个六位数的数字和目标结果
5。在创建排列的过程中，假设从前四位数字创建了以下表达式，剩下两个要处理：
(* 42 81) '??'
3696是一个很大的数字，从这一点来看，任何表达式甚至都能够得到just的结果
5吗？我们可以完全跳过创建它们吗？
不幸的是，末尾的数字仍然可以做出重大更改：
(+ (* (* 42 81) 0) 5)
我们可能会避免一些分支，但是我们将不得不考虑大多数表达式。
减少工作
好吧，鉴于我们实际上必须获得大量表达式的结果，是否还有其他省力的方法？
让我们想象一下，我们正在逐步生成一个序列，这三个最终表达式是一个接一个地生成的：
...(* (- 8 (* 3 6)) 1)(+ (- 8 (* 3 6)) 1)(- (- 8 (* 3 6)) 1)...
它们都给出不同的结果，
[12, 13, 11]但是内部部分
(- 8 (* 3 6))是相同的，并且将永远是
12。我们的解决方案应该利用这一优势。
答案
对于需要剧透的人，我为最初的实现建立了分支，该实现从顶部开始计算每个表达式，对次要的更改进行存储，从而进行计算，最后一个对生成的表达式进行预计算的结果，以及一些小的调整。。
17.40s elapsed 6180k max mem
原始问题20.60s elapsed 6284k max mem
毫无疑问4.65s elapsed 5356k max mem
我的最初2.71s elapsed 5316k max mem
我的记忆1.50s elapsed 5356k max mem
我预先计算的
关于我的实现的一些注意事项。该
generate()函数通过考虑字符串中的每个点并创建可能的下一个状态来创建候选表达式。例如，在开始时，都移动标记，并分割第一个数字：
'3|456237490' -> '34|56237490' -> ... 3 '4|56237490' ->
每个待处理状态都被推送到一个列表，并且每次循环时都会弹出要考虑的当前状态。从最后的状态继续，接下来的可能性是再次移动标记，并拆分数字以形成三个表达式之一。
3 '45|6237490' -> ... (* 3 4) '5|6237490' -> ... (+ 3 4) '5|6237490' -> ... (- 3 4) '5|6237490' -> ...
到目前为止，我已经优先考虑了操作员的优先权。处理乘法时，我们可能需要重写现有的表达式。考虑：
(+ 1 2) '3|' -> (* (+ 1 2) 3) '' # ??? (+ (+ 1 2) 3) '' (- (+ 1 2) 3) ''
对于加法和减法，这很好，顺序无关紧要。但是，
2 * 3必须在之前发生
1 + ...。简而言之，我们需要将乘法推入内部：
(+ 1 2) 3 -> (+ 1 (* 2 3))
除了存储执行操作的功能外，还有一些巧妙的方法可以存储有关操作的更多信息。对于这个问题，这并不是真正需要的，也不需要其他可能的转换，例如组合多个表达式或排除不相关的部分。
最后的实现说明，很困难，我既使迭代的方向又使表达式的布局（最初）向后。
