Задача о расстановке знаков в выражении

from itertools import product
inp, ops, answ = '1_2_3_4_5', '+*', 29
 
tmpl = list(inp)
for ops in product(ops, repeat=inp.count('_')):
    tmpl[1::2] = ops
    s = ''.join(tmpl)
    if eval(s) == answ:
        print(f"{s}={answ}")
 
# output: 1*2*3*4+5=29

from itertools import permutations, product
inp, ops, answ = '1_2_3_4_5', '+*', 29
 
vals = list(map(int, inp.split('_')))
nops = len(vals) - 1
tmpl = list(inp)
unique = set()
 
# всевозможные сочетания операций
for ops in product(ops, repeat=nops):
    # всевозможные приоритеты этих операций
    for prior in(permutations(range(nops))):
        # алгоритм сортировочной станции
        # ru.wikipedia.org/wiki/Алгоритм_сортировочной_станции
        sout, stack = [], []
        for v, op, p in zip(vals, ops, prior):
            sout.append(v)
            while stack and stack[-1][1] >= p:
                sout.append(stack.pop())
            stack.append((op, p))
        sout.append(vals[-1])
        sout.extend(stack)
 
        # вычисление выражения из инфиксной записи, которая лежит в sout
        # можно вычислять только строку, а математику - eval, тогда код короче будет
        stack = []
        for t in sout:
            if isinstance(t, int):
                stack.append((t, str(t)))
            else:
                y, yv = stack.pop()
                x, xv = stack.pop()
                view = '(' + xv + t[0] + yv + ')'
                if t[0] == '+': stack.append((x+y, view))
                if t[0] == '*': stack.append((x*y, view))
 
        # финальная проверка ответа
        result, view = stack[0]
        if result == answ: 
            unique.add(f'{view} == {result}')
 
print('\n'.join(unique))
# (1*((2*(3*4))+5)) == 29
# (1*(2+(3*(4+5)))) == 29
# (1*(((2*3)*4)+5)) == 29
# ((((1+2)+3)*4)+5) == 29
# ((((1*2)*3)*4)+5) == 29
# (((1*2)*(3*4))+5) == 29
# (((1+2)*3)+(4*5)) == 29
# ((1*((2*3)*4))+5) == 29
# (((1*(2*3))*4)+5) == 29
# ((1*2)+(3*(4+5))) == 29
# (((1+(2+3))*4)+5) == 29
# ((1*(2*(3*4)))+5) == 29