given 4 digits, compute how to get 24 by +,-,*,/

24.py

from itertools import permutations


class Stack:
    def __init__(self):
        self.arr = []

    def push(self, val):
        self.arr.append(val)

    def pop(self):
        sz = len(self.arr)
        return self.arr.pop(sz - 1)

    def size(self):
        return len(self.arr)


def plus(a, b):
    x, y = a
    u, v = b
    return u * y + v * x, v * y


def minus(a, b):
    x, y = a
    u, v = b
    return -u * y + v * x, v * y


def multi(a, b):
    x, y = a
    u, v = b
    return x * u, v * y


def divide(a, b):
    x, y = a
    u, v = b
    return x * v, u * y


def ev(exp: str):
    stk = Stack()
    dgt = [str(i) for i in range(10)]
    for i in range(len(exp)):
        cur = exp[i]
        if cur in dgt:
            stk.push((int(cur), 1))
        else:
            a = stk.pop()
            b = stk.pop()
            if cur == '+':
                stk.push(plus(a, b))
            if cur == '-':
                stk.push(minus(a, b))
            if cur == '*':
                stk.push(multi(a, b))
            if cur == '/':
                stk.push(divide(a, b))
    x, y = stk.pop()
    assert stk.size() == 0
    if y == 0:
        return -99999999
    return x / y


def run_search(lst):
    assert len(lst) == 4
    op_lst = ['+', '-', '*', '/']
    for perm in list(permutations(lst, 4)):
        for op1 in op_lst:
            for op2 in op_lst:
                for op3 in op_lst:
                    exp1 = f"{perm[0]}{perm[1]}{op1}{perm[2]}{perm[3]}{op2}{op3}"
                    if ev(exp1) == 24:
                        print(exp1)
                    exp2 = f"{perm[0]}{perm[1]}{op1}{perm[2]}{op2}{perm[3]}{op3}"
                    if ev(exp2) == 24:
                        print(exp2)


if __name__ == '__main__':
    run_search([1, 4, 5, 6])
    run_search([3, 3, 8, 8])
    run_search([3, 3, 7, 7])