Find Sequence Function - Refactored

"""
Not finished!
"""

from random import choice, random


class ExpressionFormConstructor(object):
    """
    BNF specificaton:
        <expr_form>     ::=     (<operator>, <operand>, <operand>)
        <operator>      ::=     "+" | "-" | "*" | "/" | "^"
        <operand>       ::=     "e" | "c" | "x"
        "e"             ::=     <expr_form>
        "c"             ::=     int
        "x"             ::=     x
    """
    non_terminating_expr_forms = (
        ('+', 'x', 'e'),
        ('-', 'x', 'e'),
        ('*', 'x', 'e'),
        ('/', 'x', 'e'))

    terminating_expr_forms = (
        ('+', 'x', 'c'),
        ('-', 'x', 'c'),
        ('*', 'x', 'c'),
        ('/', 'x', 'c'),
        ('^', 'x', 'c'))

    all_expr_forms = non_terminating_expr_forms + terminating_expr_forms

    def rand_form(self, depth=0):
        """
        rand_form() -> tuple(expr_form), list(constants)
        depth refers to maximum nested depth of expr_form
        """
        constants = []
        if depth is 0:
            expr_form = list(choice(self.terminating_expr_forms))
        else:
            expr_form = list(choice(self.all_expr_forms))

        if expr_form[1] is 'c':
            constants.append(0)
        elif expr_form[1] is 'e':
            expr_form[1], con = self.rand_form(depth - 1)
            constants.extend(con)
        else:
            pass

        if expr_form[2] is 'c':
            constants.append(0)
        elif expr_form[2] is 'e':
            expr_form[2], con = self.rand_form(depth - 1)
            constants.extend(con)
        else:
            pass
        return tuple(expr_form), constants


class ExpressionForm(object):

    symb_to_op = {'+':lambda a, b: a + b,
                  '-':lambda a, b: a - b,
                  '*':lambda a, b: a * b,
                  '/':lambda a, b: float(a) / b,
                  '^':pow}

    def __init__(self, expr_form, constants):
        self.expr_form = expr_form
        self.constants = constants # number of constants.
        self.population = [] # each individual is a unique tuple of constants.
        self.graveyard = set() # contains hash values for failed individuals.

    def __str__(self, expr_form=None, root=True):
        expr_form = self.expr_form if expr_form is None else expr_form
        symb, A, B = expr_form
        A = A if A in 'cx' else self.__str__(A, False)
        B = B if B in 'cx' else self.__str__(B, False)
        return ('%s %s %s' if root else '(%s %s %s)') % (A, symb, B)

    def evaluate(self, x, ind, expr=None, c=0):
        """
        x -> int, ind -> from self.population
        """
        symb, A, B = expr if expr else self.expr_form
        op = self.symb_to_op[symb]
        root = True if expr is None else False

        if A is 'c':
            A = ind[c]
            c += 1
        elif A is 'x':
            A = x
        else: # A is an expr_form
            A, c = self.evaluate(x=x, ind=ind, expr=A, c=c)

        if B is 'c':
            B = ind[c]
            c += 1
        elif B is 'x':
            B = x
        else: # B is an expr_form
            B, c = self.evaluate(x=x, ind=ind, expr=B, c=c)

        return op(A, B) if root else (op(A, B), c)


# ---------- testing ---------->



##from random import randint
##
##Constructor = ExpressionFormConstructor()
##
##def test():
##    Expr = ExpressionForm(*Constructor.rand_form(3))
##
##    # populate
##    for ind in range(100):
##        Expr.population.append(tuple([randint(1, 10) for constant in Expr.constants]))
##
##    # test and remove error prone individuals
##    for ind in range(len(Expr.population)):
##        try:
##            print [Expr.evaluate(x, Expr.population[ind]) for x in range(10)]
##        except (OverflowError, ZeroDivisionError, ValueError) as err:
##            print err
##            Expr.population[ind] = False
##    Expr.population = [ind for ind in Expr.population if ind]
##    print "lost:", 100 - len(Expr.population), "individuals"
##
##while True:
##    raw_input()
##    test()