kyoto_u_count_down.py

import operator
from typing import List

operator_set = set(['+', '-', '*', '/'])


class Solution():

    def count_down(self, nums: List[int], target: int):

        def backtrack(nums: List[int], curr_formula: List[str], target):
            nonlocal output

            # we have consumed all numbers in the list, check the computing result
            if len(nums) == 0:
                rpn = self.infix_to_rpn(curr_formula)
                res = self.compute_rpn(rpn)

                # if hit the target, then update output
                if res == target:
                    output = curr_formula

                return

            else:
                # dequeue the first number in the list and append into current formula as a str
                curr_formula.append(str(nums.pop(0)))

                # if ther are numbers left,
                # append an operator into the formula, pass the formula to next recurstion,
                # and then pop the operator we just added out
                if nums:
                    for op in operator_set:
                        curr_formula.append(op)
                        backtrack(nums[:], curr_formula[:], target)
                        curr_formula.pop()

                else:
                    backtrack(nums[:], curr_formula[:], target)

        output = []
        backtrack(nums[:], [], target)
        return ' '.join(output)

    def infix_to_rpn(self, infix_formula: List[str]) -> List[str]:
        """
        Convert infix to rpn using Shunting yard algorithm
        """

        output_queue = []
        ops_stack = []

        ops_priority = {
            '+': 0,
            '-': 0,
            '*': 1,
            '/': 1
        }

        for token in infix_formula:
            if token.isnumeric():
                output_queue.append(str(token))

            else:
                while len(ops_stack):
                    if ops_priority[ops_stack[-1]] >= ops_priority[token]:
                        output_queue.append(ops_stack.pop())

                    else:
                        break

                ops_stack.append(token)

        while ops_stack:
            output_queue.append(ops_stack.pop())

        return output_queue

    def compute_rpn(self, rpn_formula: List[str]) -> float:
        """
        Compute Reverse Polish notation (RPN) list
        """
        ops = {
            '+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': operator.truediv
        }

        stack = []

        for token in rpn_formula:
            if token.isnumeric():
                stack.append(token)

            else:
                num1 = float(stack.pop())
                num2 = float(stack.pop())
                sub_result = ops[token](num2, num1)
                stack.append(str(sub_result))

        return float(stack[0])


"""
Give a list of numbers and a target number,
generate a formula to get the target number using only [+, -, *, /] operators.
Also the sequence of the list of numbers cannot be changed.
If it's not possible, then reutrn an empty result.

Example:
    Input:
        nums = [6, 4, 5, 2, 1]
        target = 32

    Output:
        6 * 4 + 5 + 2 + 1

"""

sol = Solution()

nums = [6, 4, 5, 2, 1]

for target in range(64, 0, -1):
    print(f'{target} = {sol.count_down(nums, target)}')