基于Python的4次运算结果检查

Question

我正在努力制作一个Python程序，它可以解决如下难题：

get 23 using [1,2,3,4] and the 4 basic operations however you'd like.

我希望程序输出如下内容 # 23 reached by 4*(2*3)-1

到目前为止，我已经提出了以下方法，通过检查每个可能的2-combo和每个可能的结果，将输入列表减少1项。
使用[1,2,3,4]可以选择： [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]

使用x和y可以： (x+y),(x-y),(y-x),(x*y),(x/y),(y/x) 然后，我将迄今为止计算的操作存储在一个变量中，并对它返回的每个结果再次运行“reducing”函数，直到数组只有2个项目长：然后我可以只运行x，y->；可能的结果功能

我的问题是这种“递归”方法根本不起作用，因为我的函数在返回数组时就结束了。 如果我输入[1,2,3,4]，我会得到

[(1+2),3,4] -> [3,3,4]
[(3+3),4] -> [6,4]
# [10,2,-2,24,1.5,0.6666666666666666]

到目前为止我的代码是：

from collections import Counter

def genOutputs(x,y,op=None):
    results = []
    if op == None:
        op = str(y)
    else:
        op = "("+str(op)+")"
    ops = ['+','-','*','/','rev/','rev-']
    z = 0
    #will do every operation to x and y now.
    #op stores the last computated bit (of other functions)
    while z < len(ops):
        if z == 4:
            try:
                results.append(eval(str(y) + "/" + str(x)))
                #yield eval(str(y) + "/" + str(x)), op + "/" + str(x)
            except:
                continue
        elif z == 5:
            results.append(eval(str(y) + "-" + str(x)))
            #yield eval(str(y) + "-" + str(x)), op + "-" + str(x)
        else:
            try:
                results.append(eval(str(x) + ops[z] + str(y)))
                #yield eval(str(x) + ops[z] + str(y)), str(x) + ops[z] + op
            except:
                continue
        z = z+1
    return results

def pickTwo(array):
    #returns an array with every 2-combo
    #from input array
    vomit = []
    a,b = 0,1
    while a < (len(array)-1):
        choice = [array[a],array[b]]
        vomit.append((choice,list((Counter(array) - Counter(choice)).elements())))
        if b < (len(array)-1):
            b = b+1
        else:
            b = a+2
            a = a+1
    return vomit

def reduceArray(array):
    if len(array) == 2:
        print("final",array)
        return genOutputs(array[0],array[1])
    else:
        choices = pickTwo(array)
        print(choices)
        for choice in choices:
            opsofchoices = genOutputs(choice[0][0],choice[0][1])
            for each in opsofchoices:
                newarray = list([each] + choice[1])
                print(newarray)
                return reduceArray(newarray)

reduceArray([1,2,3,4])

Answer 1

在处理这样的问题时，最大的问题是处理操作符的优先级和括号的位置，以便从给定的集合中产生每一个可能的数字。最简单的方法是在与中缀表示法的反向波兰表示法对应的堆栈上处理操作。完成此操作后，可以递归地绘制数字和/或操作，直到所有n数字和n-1操作都已完成，然后存储结果。下面的代码生成所有可能的数字排列（不替换）、运算符排列（替换）和圆括号排列，以生成每个可能的值。请注意，这是非常低效的，因为诸如加法/乘法之类的运算符交换的结果是a + b等于b + a，因此只需要一个运算符。类似地，关联属性a + (b + c)等于(a + b) + c，但是下面的算法只是一个简单的例子，因此不会进行这样的优化

def expr_perm(values, operations="+-*/", stack=[]):
    solution = []
    if len(stack) > 1:
        for op in operations:
            new_stack = list(stack)
            new_stack.append("(" + new_stack.pop() + op + new_stack.pop() + ")")
            solution += expr_perm(values, operations, new_stack)
    if values:
        for i, val in enumerate(values):
            new_values = values[:i] + values[i+1:]
            solution += expr_perm(new_values, operations, stack + [str(val)])
    elif len(stack) == 1:
        return stack
    return solution

用法：

result = expr_perm([4,5,6])
print("\n".join(result))