Проверьте результат, используя 4 операции на основе Python

Question

Я изо всех сил пытаюсь создать программу на Python, которая может решать загадки, такие как:

, получить 23, используя [1,2,3,4] и 4 базовых операции, как вам угодно.

Я ожидаю, что программа выдаст что-то вроде # 23 reached by 4*(2*3)-1

. До сих пор я придумал следующий подход: уменьшить список ввода на 1 элемент, проверяя все возможные2-комбо, которое можно выбрать и получить любой возможный результат.
С помощью [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) Затем я сохраню вычисленную до сих пор операцию в переменной и снова запускаю функцию «сокращения» для каждого возвращаемого результата, пока массивы не будут состоять всего из 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))