An arithmetic puzzle

题目

Given a list of integer numbers, find a correct way of inserting arithmetic signs (operators) such that the result is a correct equation. Example: With the list of numbers [2,3,5,7,11] we can form the equations 2-3+5+7 = 11 or 2 = (3*5+7)/11 (and ten others!).

解题

这题等价于以一组数字为叶子节点构造二叉树，根节点为等于号，内部节点为加、减、乘、除。叶子节点在深度优先中序优先遍历时，顺序保持与原数列相同。比如，以[2, 3, 5, 7]为叶子节点，可构造出以下二叉树：

深度优先中序遍历该二叉树得到2-3+5+7=11。

为解决该题，首先用回溯法用指定数列构造出所有二叉树。然后，逐一检验竹土木人式两边是否相等。

代码实现

from functools import reduce from operator import concat def puzzle(nums): leftAndRightNums = [] for splitPoint in range(1, len(nums)): leftAndRightNums.append((nums[:splitPoint], nums[splitPoint:])) trees = reduce(concat,[[['==',left, right] for left in buildBTrees(num[0]) for right in buildBTrees(num[1])] for num in leftAndRightNums], []) exprs = [btreeToExpr(tree)[1] for tree in trees] uniqueExprs =[] for expr in exprs: if expr not in uniqueExprs: uniqueExprs.append(expr) return [expr for expr in uniqueExprs if eval(expr)]

首先，将数列切分成左右两部份。这个切分有多种方式。然后，以二叉树形式分别罗列左右四则运算表达式。再然后，将左右二叉树与根节点等于号拼接在一起，构成完整表达等式的二叉树。再然后，将二叉树形式的等式转换为字符串形式。最后，使用Python内建的eval执行字符串形式的等式表达式，其结果是boolean型。

Eval

eval(expression, globals=None, locals=None)

实参是一个字符串，以及可选的 globals 和 locals。 globals 实参必须是一个字典。 locals 可以是任何映射对象。

expression 参数会作为一个 Python 表达式（从技术上说是一个条件列表）被解析并求值，使用 globals 和 locals 字典作为全局和局部命名空间。如果 globals 字典存在且不包含以 builtins 为键的值，则会在解析 expression 之前插入以此为键的对内置模块 builtins 的字典的引用。这意味着 expression 通常具有对标准 builtins 模块的完全访问权限且受限的环境会被传播。如果省略 locals 字典则其默认值为 globals 字典。如果两个字典同时省略，表达式会在 eval() 被调用的环境中执行。返回值为表达式求值的结果。语法错误将作为异常被报告。例如:

>>> x = 1
>> eval('x+1')
2

这个函数也可以用来执行任何代码对象（如 compile() 创建的）。这种情况下，参数是代码对象，而不是字符串。如果编译该对象时的 mode 实参是 'exec' 那么 eval() 返回值为 None 。

提示： exec() 函数支持动态执行语句。 globals() 和 locals() 函数各自返回当前的全局和本地字典，因此您可以将它们传递给 eval() 或 exec() 来使用。

另外可以参阅 ast.literal_eval()，该函数可以安全执行仅包含文字的表达式字符串。

def buildBTrees(l): if len(l) == 0: return [None] if len(l) == 1: return l ops = ['+', '-', '*', '/'] leftAndRightNums = [] for splitPoint in range(1, len(l)): leftAndRightNums.append((l[:splitPoint], l[splitPoint:])) return reduce(concat, [[[op, left, right] for op in ops for left in buildBTrees(nums[0]) for right in buildBTrees(nums[1])] for nums in leftAndRightNums], [])

左右子树的构造採用递归。先将数列切为左右两部份。然后，分别构造左右子树。最后，将所有节点、左右子树的组合都罗列出来。节点的选择有+, -, *, /。 这𥚃使用了嵌套List Comprehension，生成的结果是二维的（包含包含二叉树的列表的列表）。但结果要求是包含二叉树的列表，所以这𥚃用reduce和concat去除了一层列表包装（降维）。

functools.reduce

reduce是Python标准库提供的一个函数式的工具，其声明为：

reduce(function, iterable, initializer)

其功能是将function累积地、从左往右作用于iterable中的每一个元素。

reduce相当于如下代码：

def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        value = next(it)
    else:
        value = initializer
    for element in it:
        value = function(value, element)
    return value
def btreeToExpr(tree): if type(tree) is not list: return str(tree), str(tree) if tree[1] is None and tree[2] is None: return str(tree[0]), str(tree[0]) leftOp, leftExpr = btreeToExpr(tree[1]) rightOp, rightExpr = btreeToExpr(tree[2]) op = tree[0] if greaterPrecedence(op, leftOp): leftExpr = '('+leftExpr+')' if greaterPrecedence(op, rightOp): rightExpr = '('+rightExpr + ')' return op, leftExpr + op+rightExpr def greaterPrecedence(left, right): precedenceDict = { '==':0, '-': 1, '+': 1, '*': 2, '/': 2 } # operand precedence is greater than operator if right not in precedenceDict: return False return precedenceDict[left] > precedenceDict[right]

将二叉树形式的表达式转换为字符串形式时，要考虑四则运算符的优先级。在二叉树形式中，节点所处的深度表示了运算符的顺序。但在字符中形式中，运算符出现的顺序和运算符优先级决定了运算符被执行的顺序。所以，有时需要'(,)`使字符串形式表达式中运算符的执行顺序与二叉树中的顺序保持一致。

results matching ""

    No results matching ""