#!/usr/bin/env python

import string, copy

closing  = { '(': ')', '[': ']' }
DEBUG=0

###############################################################################
# Classes:

class Unknow:
    name = ""

    def __init__( self, name ):
        self.name = name
    # __init__()

    def __str__( self ):
        return "???%s???" % self.name
    # __str__()

    def __repr__( self ):
        return "<Unknow: %s>" % self.name
    # __repr__()

    def assign( self, values ):
        raise Exception( "Is not possible to assign values to Unknow objects!" )
    # assign()

    def eval( self ):
        raise Exception( "Is not possible to evaluate Unknow objects!" )
# Unknow



class Constant:
    value = None

    def __init__( self, value=None ):
        self.value = value
    # __init__()

    def __str__( self ):
        return str( self.value )
    # __str__()

    def __repr__( self ):
        return "<Constant: %s; Type: %s>" % ( self.value,
                                              self.value.__class__.__name__ )
    # __repr__()

    def assign( self, values ):
        pass # Ignore
    # assign()

    def eval( self ):
        return self.value
    # eval()
# Constant



class String( Constant ):
    def __str__( self ):
        s = String( self.value )
        s.inc_quote()
        return s.value
    # __str__()    

    def __repr__( self ):
        return "<String: %r>" % self.value
    # __repr__()    

    def dec_quote( self ):
        s = self.value
        p = 0
        while p < len( s ):
            c = s[ p ]
            if c in ( '"', "'" ):
                if p > 0 and s[ p - 1 ] == '\\':
                    s = s[ : p - 1 ] + s[ p : ]
                else:
                    s = s[ : p ] + s[ p + 1 : ]
            p += 1
            
        self.value = s
    # dec_quote()

    def inc_quote( self ):
        s = self.value
        p = 0
        while p < len( s ):
            c = s[ p ]
            if c in ( '"', "'" ):
                s = s[ : p ] + '\\' + s[ p : ]
                p += 1
            p += 1
            
        self.value = '"' + s + '"'
    # inc_quote()    
# String



class Integer( Constant ):
    def __repr__( self ):
        return "<Integer: %s>" % self.value
    # __repr__()    
# Integer



class Float( Constant ):
    def __repr__( self ):
        return "<Float: %s>" % self.value
    # __repr__()    
# Float



class Variable:
    name = ""
    value = None
    
    def __init__( self, name ):
        self.name = name
    # __init__()

    def __str__( self ):
        return str( self.name )
    # __str__()

    def __repr__( self ):
        return "<Variable: %s=%r>" % ( self.name, self.value )
    # __repr__()

    def assign( self, values ):
        self.value = values[ self.name ]
    # assign()

    def eval( self ):
        return self.value
    # eval()
# Variable



class Operator:
    name = ""
    priority = 0
    
    def __init__( self, name ):
        self.name = name
    # __init__()

    def __str__( self ):
        return "__%s__" % self.name
    # __str__()

    def __repr__( self ):
        return "<%s: %s>" % ( self.__class__.__name__, self.name )
    # __repr__()

    def assign( self, values ):
        pass # Ignore
    # assign()
# Operator



class BinaryOperator( Operator ):
    param1 = None
    param2 = None

    def __init__( self, name, param1=None, param2=None ):
        self.name = name
        self.param1 = param1
        self.param2 = param2
    # __init__()
    
    def __str__( self ):
        r = ""
        if self.param1:
            r += str( self.param1 ) + " "

        r += "__%s__" % self.name
        
        if self.param2:
            r += " " + str( self.param2 )
            
        return r
    # __str__()

    def __repr__( self ):
        return "<%s: %s; Parameter1: %r; Parameter2: %r>" % ( self.__class__.__name__, self.name, self.param1, self.param2 )
    # __repr__()

    def eval( self, param1, param2 ):
        pass
    # eval()

    def assign( self, values ):
        try:
            if self.param1:
                self.param1.assign( values )
        except AttributeError:
            pass
        
        try:
            if self.param2:
                self.param2.assign( values )
        except AttributeError:
            pass        

    # assign()
# BinaryOperator



class BinaryOperator_Or( BinaryOperator ):
    name     = "or"
    priority = 1

    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()

    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 or param2
    # eval()
# BinaryOperator_Or



class BinaryOperator_And( BinaryOperator ):
    name     = "and"
    priority = 1

    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()
    
    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 and param2
    # eval()
# BinaryOperator_And



class BinaryOperator_Plus( BinaryOperator ):
    name     = "+"
    priority = 2

    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()    
    
    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 + param2
    # eval()
# BinaryOperator_Plus



class BinaryOperator_Minus( BinaryOperator ):
    name     = "-"
    priority = 2

    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()
    
    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 - param2
    # eval()
# BinaryOperator_Minus



class BinaryOperator_Multiply( BinaryOperator ):
    name     = "*"
    priority = 3
    
    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()

    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 * param2
    # eval()
# BinaryOperator_Multiply



class BinaryOperator_Divide( BinaryOperator ):
    name     = "/"
    priority = 3

    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()
    
    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 / param2
    # eval()
# BinaryOperator_Divide



class BinaryOperator_Module( BinaryOperator ):
    name     = "%"
    priority = 4

    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()
    
    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 % param2
    # eval()
# BinaryOperator_Module



class BinaryOperator_Power( BinaryOperator ):
    name     = "**"
    priority = 5
    
    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()

    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 ** param2
    # eval()
# BinaryOperator_Power



class BinaryOperator_Equal( BinaryOperator ):
    name     = "=="
    priority = 0
    
    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()

    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 == param2
    # eval()
# BinaryOperator_Equal



class BinaryOperator_NotEqual( BinaryOperator ):
    name = "!="
    priority = 0
    
    def __init__( self, param1=None, param2=None ):
        BinaryOperator.__init__( self, self.name, param1, param2 )
    # __init__()

    def eval( self, param1=None, param2=None ):
        param1 = param1 or self.param1
        param2 = param2 or self.param2
        try:
            param1 = param1.eval()
        except AttributeError:
            pass
        try:
            param2 = param2.eval()
        except AttributeError:
            pass
        
        return param1 != param2
    # eval()
# BinaryOperator_NotEqual



class UnaryOperator( Operator ):
    param = None

    def __init__( self, name, param=None ):
        self.name = name
        self.param = param
    # __init__()
    
    def __str__( self ):
        r = "__%s__" % self.name
        
        if self.param:
            r += " " + str( self.param )
        
        return r
    # __str__()

    def __repr__( self ):
        return "<%s: %s; Parameter: %r>" % ( self.__class__.__name__, self.name, self.param )
    # __repr__()
    
    def eval( self, param ):
        pass
    # eval()

    def assign( self, values ):
        try:
            if self.param:
                self.param.assign( values )
        except AttributeError:
            pass
    # assign()    
# UnaryOperator


class UnaryOperator_Not( UnaryOperator ):
    name     = "not"
    priority = 999
    
    def __init__( self, param=None ):
        UnaryOperator.__init__( self, self.name, param )
    # __init__()

    def eval( self, param=None ):
        param = param or self.param
        try:
            param = param.eval()
        except AttributeError:
            pass

        return not param
    # eval()
# UnaryOperator_Not



class Function:
    name       = ""
    parameters = None
    function   = None

    def __init__( self, name, parameters=None ):
        self.name = name
        self.parameters = parameters or []
    # __init__()

    def __str__( self ):
        s = "%s(" % self.name
        for p in self.parameters:
            for e in p:
                s = "%s %s" % ( s, e )
            s += ","
        return s[ : -1 ] + " )"
    # __str__()

    def __repr__( self ):
        return "<Function: %s (%s); Parameters: %r>" % ( self.name,
                                                         self.function,
                                                         self.parameters )
    # __repr__()

    def assign( self, values ):
        self.function = values[ self.name ]
        for p in self.parameters:
            p.assign( values )
    # assign()

    def eval( self ):
        pars = tuple( [ e.eval() for e in self.parameters ] )
        return  self.function( * pars )
    # eval()
# Function



class Expression:
    elements = None

    def __init__( self, elements=None ):
        self.elements = elements or []
    # __init__()

    def __str__( self ):
        r = "( "
        for e in self.elements:
            r += str( e ) + " "
        return r + ")"
    # __str__()

    def __repr__( self ):
        r = "<Expression: "
        for e in self.elements:
            r += repr( e ) + " "
        if len( self.elements ) > 0:
            r = r[ : -1 ]
        return r + ">"
    # __repr__()
        
    def append( self, element ):
        self.elements.append( element )
    # append()

    def __getitem__( self, index ):
        return self.elements.__getitem__( index )
    # __getitem__()

    def assign( self, values ):
        for e in self.elements:
            e.assign( values )
    # assign()

    def build( self ):
        elements = self.elements

        if len( elements ) < 2:
            return

        prios = []
        for op in operators.values():
            if op.priority not in prios:
                prios.append( op.priority )

        prios.sort()        
        cpos = 0
        epos = len( elements )
        
        # Transform the elements list in a elements tree, with the lowest
        # priority operator at the root
        while len( elements ) > 1: # at the end, only the root
            e = elements[ cpos ]

            # is this element a {Binary,Unary}Operator and we are parsing
            # its priority right now?
            if issubclass( e.__class__, ( BinaryOperator, UnaryOperator )) \
                   and e.priority == prios[ -1 ]:
                # Yes, remove its parameter from list and add them to the
                # operator, building a tree.
                # Remove the operands from the list.
                if issubclass( e.__class__, BinaryOperator ):
                    e.param1 = elements[ cpos - 1 ]
                    e.param2 = elements[ cpos + 1 ]
                    del elements[ cpos + 1 ]
                    del elements[ cpos - 1 ]
                    cpos -= 1
                    epos = len( elements )
                else:
                    e.param = elements[ cpos + 1 ]
                    del elements[ cpos + 1 ]
                    epos = len( elements )
            elif issubclass( e.__class__, Expression ):
                e.build()
            if cpos < epos - 1:
                cpos += 1
            else:
                cpos = 0
                prios.pop() # remove last priority, we already parsed all
        #
    # build()

    def eval( self ):
        if len( self.elements ) == 1:
            return self.elements[ 0 ].eval()
        elif len( self.elements ) == 0:
            return None
        elif len( self.elements ) > 0:
            return [ e.eval() for e in self.elements ]            
    # eval()
# Expression



class List( list ):
    def __str__( self ):
        r = "( "
        for i in self:
            r += str( i ) + ", "
        if len( self ) > 0:
            r = r[ : -2 ]        
        r += " )"
        return r
    # __str__()

    def __repr__( self ):
        r = "<List: "
        for i in self:
            r += repr( i ) + ", "
        if len( self ) > 0:
            r = r[ : -2 ]
        r += " >"
        return r
    # __repr__()

    def assign( self, values ):
        for e in self:
            e.assign( values )
    # assign()
# List
        




###############################################################################
# Setup

l = locals()
binary_operators = {}
unary_operators  = {}
operators        = {}
for c in l.keys():
    C = l[ c ]
    if   c.startswith( "BinaryOperator_" ):
        binary_operators[ C.name ] = C
        operators[ C.name ] = C
    elif c.startswith( "UnaryOperator_" ):
        unary_operators[ C.name ] = C
        operators[ C.name ] = C





###############################################################################
# Functions:

def expression_parser( s ):
    """
    Parse the expression 's' and return a list of it's parts, each being
    a list with the first element as it's type, the second as it's name and
    the second as it parameters (functions).
    """
    s    = s.strip()
    e    = Expression()
    name = ""
    type = ""
    lc   = ""
    cpos = 0
    epos = len( s )

    while cpos < epos:
        c = s[ cpos ]
        
        if c not in [ " ", "'", '"' ] + closing.keys():
            name += c
        else:
            if c == " " and lc == " ": continue
            
            if name and c not in closing.keys():
                e.append( identify_symbol( name, c ) )
                name = ""
                
            elif c in ( '"', "'" ):
                s, r = string_parser( s[ cpos : ] )
                r = String( r )
                e.append( r )
                name = ""
                epos = len( s )
                cpos = 0

            elif c in closing.keys():
                s, r = tuple_parser( s[ cpos : ] )
                element = identify_symbol( name, c )
                if isinstance( element, Function ):
                    if not isinstance( r, List ):
                        r = List() + [ r ]

                    element.parameters = r
                    r = element
                #else:
                    # is Sub-expression?
                    #if len( r ) == 1 and r[ 0 ].__class__ == Expression:
                    #    r = r[ 0 ]
                e.append( r )
                name = ""
                epos = len( s )
                cpos = 0

        lc    = c
        cpos += 1
    # while cpos < epos
    
    if name:        
        e.append( identify_symbol( name, None ) )

    #e.build()
    return e
# expression_parser()



def evaluate_expression( expression, values ):
    """
    Evaluate a expression 'e' composed with Expression, Variable, Constant,
    Operator, Integer, Float and Function.
    You may use expression_parser() and give a textual expression, then
    pass the returned Expression to this function.

    Parameters:
      @param expression a Expression with desired operands and operators.
      @param values a dict with the values of Variable and Function elements used in expression.

    @return the evaluated expression value.
    """
    
    expression.assign( values )
    expression.build()
    return expression.eval()
# evaluate_expression()



def identify_symbol( name, next_char ):
    """
    Identify name to be a keyword, var or function, based on the next char.
    Helper to expression_parser().

    Parameters:
       @param name the symbol you want to identify.
       @param next_char the next char following name in parsed expression.

    @return a object representing that symbol.
    """
    
    if name in operators.keys():
        return operators[ name ]()


    if next_char in ( " ", None ):
        try: # Is it an integer?
            return Integer( string.atoi( name ) )
        except:
            pass

        try: # Is it a floating point number?
            return Float( string.atof( name ) )
        except:
            pass

        if name[ 0 ] in ( '"', "'" ):
            return String( name )


        if name[ 0 ].isalpha() or name[ 0 ] == "_": 
            return Variable( name )

    elif next_char in closing.keys():
        if name:
            return Function( name )
        else:
            return List()

    
    return Unknow( name )
# identify_symbol()



def tuple_parser( s ):
    """
    Parse string 's' and return a list of lists or tuples, using 'closing'
    characters.
    Helper to expression_parser().

    Parameters:
       @param s the string with the tuple to be parsed.

    @return a list with the first argument being the string left to be parsed and the second the parsed tuple, as List object.
    """
    t = List()

    s = s.strip()
    d = closing[ s[ 0 ] ]
    s = s[ 1 : ]
    
    lpos = 0
    cpos = 0
    epos = len( s )

    e = None
    while cpos < epos:
        c = s[ cpos ]

        if c in closing.keys():
            # we will recurse

            # parse expression until now
            tmp = break_list( s[ lpos : cpos ] )
            if len( tmp ) == 1: tmp = tmp[ 0 ]

            # recurse
            s = s[ cpos : ]
            s, tr = tuple_parser( s )

            # Add recurse result to expression
            tmp.append( tr )

            # remember what we parsed so far
            e = tmp

            # fix limits
            lpos = cpos = 0
            epos = len( s )
            
        elif c == d:
            # we will stop loop

            # parse until now
            tmp = break_list( s[ : cpos ] )
            if len( tmp ) == 1: tmp = tmp[ 0 ]

            # we have something already parsed? (In nested tuples)
            if e:
                # Yes, append elements to it
                e.elements += tmp.elements
            else:
                # No, create a new element
                e = tmp

            t.append( e )
            s = s[ cpos + 1 : ]
            break
        
        cpos += 1
    # while cpos < epos

    if len( t ) == 1: t = t[ 0 ]
    return [ s, t ]
# tuple_parser()



def string_parser( s ):
    """
    Parse string 's' and return the resulting string inside it.
    Helper to expression_parser().

    Parameters:
       @param s the string with the string to be parsed.

    @return a list with the first argument being the string left to be parsed and the second the parsed string.
    """
    s = s.strip()
    d = s[ 0 ]
    s = s[ 1 : ]
    
    cpos = 0
    epos = len( s )

    depth = 1
    while cpos < epos:
        c = s[ cpos ]
        if c == d:
            if cpos > 0 and s[ cpos - 1 ] == '\\':
                s = s[ : cpos - 1 ] + s[ cpos : ]
                cpos -= 1
                epos = len( s )
            else:
                depth -= 1
            
        if depth == 0:
            break
        cpos += 1

    r = s[ : cpos ]
    s = s[ cpos + 1 : ]    
    return [ s, r ]
# string_parser()



def break_list( s ):
    """
    Split string 's' at commas and return the list, removing empty elements.
    Each element will be a expression
    Helper to expression_parser().

    Parameters:
       @param s the string with a list (comma separated values) to be parsed.

    @return a List object with non-empty elements.
    """
    l = s.strip().split( ',' )
    r = List()
    for e in l:
        e = e.strip()
        if e:
            r.append( expression_parser( e ) )
    return r
# break_list()