test1.py

class Tree(object):
    def __init__(self, operator, left, right):
        self._operator = operator
        self._left = left
        self._right = right

    def eval(self):
        if not isinstance(self._operator, basestring):
            return self._operator
        (l,r) = (self._left.eval(), self._right.eval())
        if self._operator == "+":
            return l + r
        elif self._operator == "-":
            return l - r

def is_num(x):
    try:
        int(x)
        return True
    except ValueError:
        return False


import itertools as it

# all_partitions([]) => [([],[])]
# all_partitions([1]) => [ ([], [1]), ([1], []) ]
# all_partitions([1,2]) => [([],[1,2]),([1],[2]),([2],[1]),([1,2],[])]
def all_partitions(ls):
    return it.chain.from_iterable((choose_n(n, ls) for n in range(len(ls)))

# choose_n(0,[1,2]) => [([],[1,2])]
# choose_n(1,[1,2]) => [([1],[2]),([2],[1])]
# choose_n(2,[1,2,3]) => [([1,2],[3]),([1,3],[2]),([2,3],[1])]
# choose_n(5,[1,2,3]) => _|_
def choose_n(n, ls):
    if n == 0:
        yield ([],ls)
        return
    if n == len(ls):
        yield (ls,[])
        return

    for i,l in enumerate(ls):
        # l is on the left
        for left,right in choose_n(n-1,ls[i+1:]):
            yield ([l] + left, right)

        # l is on the right
        for left,right in choose_n(n, ls[i+1:]):
            yield (left, [l] + right)

# all_trees([1],[]) => Tree(1)
# all_trees([1,2],['+'])
def all_trees(nums, ops=list("+-*/")):
    """Returns maximum expression.

    Args:
      nums: The nums
    """

    if len(ops) == 0:
        yield Tree(nums[0], None, None)
        return

    for i, o in enumerate(ops):
        rest_ops = ops[:i] + ops[i+1:]
        for left_ops, right_ops in all_partitions(rest_ops):
            for left_nums, right_nums in choose_n(len(left_ops) + 1, nums):
                for left_tree in all_trees(left_nums, left_ops):
                    for right_tree in all_trees(right_nums, right_ops):
                        yield Tree(o, left_tree, right_tree)

def max_eval(nums):
    # Thelei try - catch gia tin periptwsi tou div by 0
    max((t.eval() for t in all_trees(nums)))