问题表示为：给定一个仅包含数字0-9和目标值的字符串，返回通过在数字之间添加一些二进制运算符（+，-或*）而创建的所有表达式，以便它们求和为目标值。在某些情况下，可能没有任何二进制运算符将创建有效的表达式，在这种情况下，该函数应返回一个空数组。新表达式中的数字不应包含前导零。

该函数应返回按字典顺序排序的求值为目标的所有有效表达式。

例如：

digits = "123"和target = 6，应返回： ["1*2*3", "1+2+3"]

我当前的算法如下。它有点慢，所以我正在寻找一种更有效的方法来解决该问题。我目前的算法产生操作数和运算符的所有组合。对于上面的示例，它产生

操作数：

[['1', '2', '3'], ['1', '23'], ['12', '3'], ['123']]

运营商：

{0: [()], 1: [('+',), ('-',), ('*',)], 2: [('+', '+'), ('+', '-'), ('+', '*'), ('-', '+'), ('-', '-'), ('-', '*'), ('*', '+'), ('*', '-'), ('*', '*')]}

然后，它将所有可能的操作数和运算符组合进行组合，并分别进行评估。

这些数字有一个约束，2 ≤ digits.length ≤ 10.
所以还算不错，但是对于这种长度为10的数字，它大约需要4.3秒，而该数字最多需要4秒。

我还尝试使用以下替代方法来加速eval（）函数：

if eval(temp) == target:

要么

exp_as_func = eval('lambda: ' + temp)
if exp_as_func() == target:

要么

compiled = compile(temp, '<string>', 'eval')
if compiled == target:

使用Python 3，所有这些花费的时间仍然差不多。

码：

import itertools
import time

def getValidExp(digits, target):    
    def getSign_combination(length):
        signCombo = {}
        for i in range(0, length):
            signCombo[i] = [c for c in itertools.product(('+', '-', '*'), repeat=i)]
        return signCombo

    def generate_combination(source, comb):
        res = []
        for x, action in zip(source, comb + (0,)):      
            res.append(x)
            if action == 0:
                #####IF ITS A 0, YIELD STRING.  IF NOT COMBINE NEXT ONE
                yield "".join(res)
                res = []


    #####PRODUCT GENERATES (0,0,1).  ALL COMBINATIONS.  0 MEANS BY ITSELF, 1 APPEND NEXT ITEM.

    elementCombo = [list(generate_combination(digits, c)) for c in itertools.product((0, 1), repeat=len(digits) - 1)]

    signCombo = getSign_combination(len(digits))

    result = []
    for e in elementCombo:
        signs = signCombo[len(e)-1]

        for i,sign in enumerate(signs):

            temp = [ item for tple in zip(e, sign) for item in tple ]
            temp.append(e[-1])
            temp = "".join(temp)

            try:
                if eval(temp) == target:
                    result.append(temp)
            except:
                pass

    return sorted(result)

digits = "3456237490"
target = 9180
print("Answer:", getValidExp(digits, target))

使用计算器函数（没有eval（））的代码几乎具有相同的速度：

from itertools import combinations, permutations
import itertools
import time

def getValidExp(digits, target):

    def calculate(s):
        operands, operators = [], []
        operand = ""
        for i in reversed(range(len(s))):
            if s[i].isdigit():
                operand += s[i]
                if i == 0 or not s[i - 1].isdigit():
                    operands.append(int(operand[::-1]))
                    operand = ""
            elif s[i] == '*':
                operators.append(s[i])
            elif s[i] == '+' or s[i] == '-':
                while operators and operators[-1] == '*':
                    compute(operands, operators)
                operators.append(s[i])

        while operators:
            compute(operands, operators)

        return operands[-1]

    def compute(operands, operators):
        left, right = operands.pop(), operands.pop()
        op = operators.pop()
        if op == '+':
            operands.append(left + right)
        elif op == '-':
            operands.append(left - right)
        elif op == '*':
            operands.append(left * right)

    def getSign_combination(length):
        signCombo = {}
        for i in range(0, length):
            signCombo[i] = [c for c in itertools.product(('+', '-', '*'), repeat=i)]
        return signCombo

    def generate_combination(source, comb):
        res = []
        for x, action in zip(source, comb + (0,)):
            res.append(x)
            if action == 0:
                yield "".join(res)
                res = []

    start = time.clock()

    #####PRODUCT GENERATES (0,0,1).  ALL COMBINATIONS.  0 MEANS BY ITSELF, 1 APPEND NEXT ITEM.
    elementCombo = [list(generate_combination(digits, c)) for c in itertools.product((0, 1), repeat=len(digits) - 1)]

    signCombo = getSign_combination(len(digits))

    result = []
    for e in elementCombo:
        signs = signCombo[len(e)-1]
        for i,sign in enumerate(signs):
            temp = ""
            valid = True

            for num in e:
                if num[0] == '0' and len(num) > 1:
                    valid = False
                    break

            if valid:
                for num,operator in zip(e,sign):
                    temp += num
                    temp += operator

                temp += e[-1]

                ####USING CALCULATOR CODE
                if calculate(temp) == target:
                    result.append(temp)

    print(time.clock() - start)
    return sorted(result)


digits = "3456237490"
target = 9180
print("Answer:", getValidExp(digits, target))