如何编写一个程序,使用9到1的数字来获取2016年的所有方法？

Question

您可以在9 8 7 6 5 4 3 2之间添加任何运算符(包括括号和+ - */**).例如, 98*76-5432*1=2016 9*8*7*(6+5-4-3)*(2-1)=2016

我写了一个像这样的程序

from __future__ import division
s = ['+','-','*','/','','(',')']

def calc(s):
    a=s.split()
    return eval(''.join(a))
a=['','9','','8','','7','','6','','5','','4','','3','','2','','1.','']

def test(tmp):
    if tmp == 20:
        try:
            z = eval(''.join(a))
            if z == 2016:
                print ''.join(a)
        except:
            pass
        return
    for i in s:
        #print a
        a[tmp] = i
        test(tmp+2)
for j in s:
    a[0] = j
    test(2)

但这是不对的,因为数字之间可能存在多个运算符.

Answer 1

对于涉及使用括号构造算术表达式的问题,有一个众所周知的技巧:通常使用反向抛光表示法更容易.

这是执行此操作的代码.

# Compute "a op b", returning None if the result
# is no good (eg: 9/0 or too big).
def do_op(a, op, b):
    if op == '+':
        return a + b
    if op == '-':
        return a - b
    if op == '*':
        return a * b
    if op == '/':
        if b == 0 or a % b != 0:
            return None
        return a // b
    if op == '**':
        # Disallow arguments that would result
        # in fractions or huge numbers, being careful
        # to allow valid results.
        if a == 1:
            return a
        if a == -1:
            return -1 if b % 2 else 1
        if a == 0 and b == 0:
            return None
        if b < 0 or b > 20 or a > 10000 or a < -10000:
            return None
        return a ** b
    assert False

# Generates expressions that result in the given target.
# ops is the a record of the operations applied so far,
# stack is the evaluation stack, and num is the first
# digit that we've not pushed yet.
def sums(ops, stack, num, target):
    if not num and len(stack) == 1:
        if stack[0] == target:
            yield ops
        return

    # If num is 7, say, try pushing 7, 76, 765, 7654, ..., 7654321.
    k = num
    for i in xrange(num, 0, -1):
        for s in sums(ops + [k], stack + [k], i-1, target):
            yield s
        k = 10 * k + (i - 1)

    # If we've less that 2 things on the stack, we can't apply
    # any operations.
    if len(stack) < 2:
        return

    # Try each of the possible ops in turn.
    for op in ['+', '-', '*', '/', '**']:
        result = do_op(stack[-2], op, stack[-1])
        if result is None:
            continue
        for s in sums(ops + [op], stack[:-2] + [result], num, target):
            yield s


# Convert a list of operations that represent an expression in RPN
# into infix notation. Every operation is bracketed, even when
# that's redundant.
def to_infix(ops):
    stack = []
    for p in ops:
        if isinstance(p, int):
            stack = stack + [p]
        else:
            stack = stack[:-2] + ['(%s%s%s)' % (stack[-2], p, stack[-1])]

    assert len(stack) == 1
    return stack[0]

# Starting with an empty stack (and no operations), with 9 as the first
# unused digit, generate all expressions that evaluate to 2016.
for s in sums([], [], 9, 2016):
    print to_infix(s)

它需要几分钟才能运行,但有很多(超过25000个)有效表达式可以评估到2016年.

我最喜欢的是(((98*76)-5432)*1).