# 第一题：24点游戏
# 思路：对4数字和运算符全排列
# @param arr int整型一维数组
# @return bool布尔型
#
class Solution:
    def Game24Points(self , arr ):
        a = arr
        res = []

        def dfs(x):
            if x == len(a) - 1:
                res.append(a[:])
                return

            for i in range(x, len(a)):
                a[x], a[i] = a[i], a[x]
                dfs(x + 1)
                a[x], a[i] = a[i], a[x]

        dfs(0)

        def al_op(nums):
            assert len(nums) == 4
            ops = [lambda x, y: x + y,
                   lambda x, y: x - y,
                   lambda x, y: x * y,
                   lambda x, y: x / y,
                   ]
            find = False
            for i in range(4):
                for j in range(4):
                    for k in range(4):
                        if int(ops[k](ops[j](ops[i](nums[0], nums[1]), nums[2]), nums[3])) == 24:
                            find = True

            return find

        flag = False
        for r in res:
            if al_op(r):
                flag = True

        return flag

# 第二题：判断括号字符串是否正确
# 栈的经典例题，遇左括号压栈，遇右括号弹栈比较
# @param s string字符串
# @return bool布尔型
#
class Solution:
    def IsValidExp(self, s):
        # write code here
        n = len(s)
        if n == 0:
            return True
        if n % 2 == 1:
            return False

        stack = []
        for c in s:

            if c in ['(', '{', '[']:
                stack.append(c)
            elif c in [')', '}', ']']:
                tmp = stack.pop()
                if tmp == '(' and c == ')'&nbs***bsp;tmp == '{' and c == '}'&nbs***bsp;tmp == '[' and c == ']':
                    continue
                else:
                    return False

        if len(stack) == 0:
            return True
        else:
            return False


if __name__ == '__main__':
    s = Solution()
    print(s.IsValidExp("([)]"))

# 第三题：1024块钱花了N块以后，64, 16, 4, 1四种硬币，找零最少的硬币个数
# 
# @param N int整型
# @return int整型
#
class Solution:
    def GetCoinCount(self , N ):
        # write code here
        res = 0
        money = 1024 - N

        for base in [64, 16, 4, 1]:

            res += money // base
            money %= base


        return res