tutorials.de Buch-Aktion 05/2012
ERLEDIGT
NEIN
ANTWORTEN
0
ZUGRIFFE
1279
EMPFEHLEN
  • An Twitter übertragen
  • An Facebook übertragen
  1. 22.05.10 17:23 #1
    OnlyFoo OnlyFoo ist offline Mitglied Brokat
    Registriert seit
    Feb 2005
    Beiträge
    470
    Hey

    Meine Formel wird im Prinzip durch eine Verschachtelung von Ausdrücken dargestellt. Jeder Ausdruck hat einen Operator (Multiplikation, Addition, etc) und ein oder mehrere Argumente, die wiederum Ausdrücke oder Operanden sein können. Jeder Ausdruck und jeder Operand hat dann eine Methode, mit der eine differenzierte Version nach einer Variablen von sich selbst zurück gibt. Also z.B.
    Code python:
    1
2

    # Ableiten von 3*x^2 nach x
Multiplication( Power(Operand('x'), Operand(2)), Operand(3)).derive('x')

    Hier der Code
    Code python:
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314

    # -*- encoding: utf8 -*-
 
import math
        
class Operator(object):
    def __init__(self, name, *arguments):
        if len(arguments) < 1:
            raise Exception( "Es wird mindestens ein Operand benötigt" )
        
        self.arguments = arguments or []
        self.name = name
    
    def depends(self, on):
        return any(o.depends(on) for o in self.arguments)
    
    def __str__(self):
        return self.name.join(
            (("%s" if precedence(a) >= precedence(self) else "(%s)") % str(a))
                for a in self.arguments )
    
    @property
    def calcable(self):
        return all(a.calcable for a in self.arguments)
    
    def __in__(self, what):
        return what in self.arguments
    
    
class UnaryFunction(Operator):
    def __init__(self, name, arg):
        super(UnaryFunction, self).__init__(name, arg)
    
    def __str__(self):
        return "%s(%s)" % (self.name, str(self.operand))
    
    @property
    def operand(self):
        return self.arguments[0]
    
    def derive(self, on):
        if self.name == 'sin':
            return Multiplication(
                UnaryFunction('cos', self.operand),
                self.operand.derive(on))
        
        if self.name == 'cos':
            return Multiplication(
                Operand(-1),
                UnaryFunction('sin', self.operand),
                self.operand.derive(on))
        
        if self.name == 'sqrt':
            # 0.5 x^{-0.5} * x'
            return Multiplication(
                Operand(0.5),
                Power(self.operand, Operand(-0.5)),
                self.operand.derive(on))
        
        if self.name == 'ln':
            return Division(
                self.operand.derive(on),
                self.operand)
        
        if self.name == 'exp':
            return Multiplication(
                self,
                self.operand.derive(on))
        
        return Multiplication(
            UnaryFunction( self.name + "'", self.operand ),
            self.operand.derive(on))
 
    @property
    def calcable(self):
        return super(UnaryFunction,self).calcable and hasattr(math, self.name)
    
    def simplify(self):
        result = UnaryFunction(self.name, self.operand.simplify())
        return result.calc() if result.calcable else result
    
    def calc(self):
        return Operand(getattr(math, self.name)( self.operand.calc().value))
 
 
class Division(Operator):
    def __init__(self, divident, divisor):
        super(Division, self).__init__('/', divident, divisor)
    
    @property
    def divident(self):
        return self.arguments[0]
    
    @property
    def divisor(self):
        return self.arguments[1]
    
    def derive(self,on):
        return Division(
            Addition(
                Multiplication( self.divident.derive(on), self.divisor ),
                Multiplication( Operand(-1), self.divident, self.divisor.derive(on) ) ),
            Power(self.divisor, Operand(2)))
    
    def simplify(self):
        divisor = self.divisor.simplify()
        divident = self.divident.simplify()
        
        if divisor == ZERO:
            raise Exception( "Game Over, du hast das Universum zerstört" )
        
        elif divisor == ONE:
            result = divident
        else:
            result = Division(divident, divisor)
            
        return result.calc() if result.calcable else result
        
    def calc(self):
        return Operand(self.divident.calc().value / float(self.divisor.calc().value))
 
class Power(Operator):
    def __init__(self, base, exponent):
        super(Power, self).__init__('^', base, exponent)
    
    @property
    def base(self):
        return self.arguments[0]
    
    @property
    def exponent(self):
        return self.arguments[1]
    
    def derive(self, on):
        if self.exponent == ZERO:
            return ZERO
        
        if self.exponent == ONE:
            return self.base.derive(on)
        
        if self.base.depends(on) and not self.exponent.depends(on):
            return Multiplication(
                Addition(self.exponent),
                Power(self.base, Addition(self.exponent, Operand(-1))),
                self.base.derive(on))
        
        elif not self.base.depends(on) and self.exponent.depends(on):
            return Multiplication(
                UnaryFunction('ln', self.base),
                self,
                self.exponent.derive(on))
        
        elif self.base.depends(on) and self.exponent.depends(on):
            # f^g = exp(g * ln(f))
            return UnaryFunction('exp',
                Multiplication(
                    self.exponent,
                    UnaryFunction('ln', self.base))).derive(on)
            
        else:
            return ZERO
        
    def simplify(self):
        base = self.base.simplify()
        exponent = self.exponent.simplify()
        
        if base == ZERO:
            result = ZERO
        elif exponent == ZERO:
            result = ONE
        elif exponent == ONE:
            result = base
        else:
            result = Power(
                base.calc() if base.calcable else base,
                exponent.calc() if exponent.calcable else exponent)
        
        return result.calc() if result.calcable else result
    
    def calc(self):
        return Operand(self.base.calc().value ** self.exponent.calc().value)
 
 
class Addition(Operator):
    def __init__(self, *arguments):
        super(Addition, self).__init__('+', *arguments)
    
    def derive(self, on):
        return Addition( *[o.derive(on) for o in self.arguments] )
 
    def simplify(self):
        result = [op.simplify()
            for op in self.arguments
            if op and op != ZERO]
        
        if not result:
            return ZERO
        
        const = 0
        filtered = []
        for op in list(result):
            if op.calcable:
                const += op.calc().value
            elif isinstance(op, Addition):
                filtered.extend(op.arguments)
            else:
                filtered.append( op )
 
        if const:
            filtered.append( Operand(const) )
        
        result = Addition(*filtered) if len(filtered) > 1 else filtered[0]
        return result.calc() if result.calcable else result
    
    def calc(self):
        return Operand(sum(o.calc().value for o in self.arguments))
 
 
class Multiplication(Operator):
    def __init__(self, *arguments):
        super(Multiplication, self).__init__('*', *arguments)
    
    def derive(self, on):
        return Addition( *[
            Multiplication(*[(o.derive(on) if i == j else o) for i, o in enumerate(self.arguments)])
            for j in range(len(self.arguments)) ] )
    
    def simplify(self):
        result = [op.simplify()
            for op in self.arguments
            if op and op != ONE]
        
        if not result:
            return ONE
        
        if ZERO in result:
            return ZERO
        
        const = 1
        filtered = []
        for op in list(result):
            if op.calcable:
                const *= op.calc().value
            
            elif isinstance(op, Multiplication):
                filtered.extend(op.arguments)
 
            else:
                filtered.append( op )
 
        if const != 1:
            filtered.append( Operand(const) )
        
        result = Multiplication(*filtered) if len(filtered) > 1 else filtered[0]
        return result.calc() if result.calcable else result
    
    def calc(self):
        return Operand(reduce(lambda a, b: a*b,
            (o.calc().value for o in self.arguments),
            1))
    
class Operand(object):
    def __init__(self, value):
        self.value = value
    
    def depends(self, on):
        return self.value == on
    
    def derive(self, on):
        return ONE if self.depends(on) else ZERO
 
    def __str__(self):
        return str(self.value)
    
    def simplify(self):
        return self
    
    def __eq__(self, other):
        return isinstance(other, Operand) and other.value == self.value
    
    @property
    def calcable(self):
        return isinstance(self.value, (float, int, long))
    
    def calc(self):
        return self
 
precedence_list = [
    Addition,
    Multiplication,
    Division,
    Power,
    Operand,
    UnaryFunction ]
 
def precedence( what ):
    return precedence_list.index( what.__class__ )
 
ZERO = Operand(0)
ONE  = Operand(1)
 
import sys, parse
 
f = parse.instantiate( parse.parse( parse.tokenize( sys.argv[1] ) ), globals() )
print "   f(x) =", f
while str(f) != str(f.simplify()):
    f = f.simplify()
    print "        =", f
 
print
x = f.derive('x')
print "  f'(x) =", x
while str(x) != str(x.simplify()):
    x = x.simplify()
    print "        =", x

    Mein Parser ist ein einfacher "recursive descent parser" der eine einfache Grammatik
    für mathematische Ausdrücke versteht.
    Code python:
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

    # -*- encoding: utf8 -*-
 
import re
 
class Token(object):
    def __init__(self, type, value):
        self.type = type
        self.value = value
 
    def __str__(self):
        return "(%s %s)" % (str(self.type), str(self.value or ""))
    
def tokenize( string ):
    tokens = []
    string = string.strip()
    while string:
        match = re.match( r'\d+|[()^/+*-]|[a-z]+', string )
        if not match:
            raise Exception( "Fehler nahe: '%s'" % string[:30] )
        
        value = match.group()
        string = string[len(value):].strip()
        if value in ("ln","sin","cos","exp"):
            tokens.append( Token("function", value) )
 
        elif re.match( r'^[a-z]+$', value ):
            tokens.append( Token("variable", value) )
        
        elif value in "/+*-^":
            tokens.append( Token("operator", value) )
 
        elif re.match( r'^\d+$', value ):
            tokens.append( Token("number", int(value)) )
 
        elif value == "(":
            tokens.append( Token("lparen", None) )
 
        elif value == ")":
            tokens.append( Token("rparen", None) )
        
        else:
            raise Exception( "Should not happen" )
 
    return tokens
 
 
def parse( tokens ):
    tokens = [None] + list(tokens)
    def peek(value = False):
        return getattr(tokens[1], 'value' if value else 'type') \
             if len(tokens) >= 2 else 'eot'
 
    def next(ttype = None):
        if ttype and peek() != ttype:
            raise Exception("Token '%s' erwartet, '%s' bekommen" % (ttype, peek()))
 
        tokens.pop(0)
        return tokens[0] if tokens else 'eot'
 
    skip = next
    
    def expression():
        return expr_addition()
        
    def expr_addition():
        a = [expr_multiplication()]
        while peek() == 'operator' and peek(True) in '+-':
            if peek(True) == '+':
                skip()
            
            a.append(expr_multiplication())
        
        return a[0] if len(a) == 1 else ['Addition'] + a
 
    def expr_multiplication():
        a = [expr_division()]
        while peek() == 'operator' and peek(True) == '*':
            skip()
            a.append(expr_division())
        
        return a[0] if len(a) == 1 else ['Multiplication'] + a
 
    def expr_division():
        a = [expr_power()]
        if peek() == 'operator' and peek(True) == '/':
            skip()
            a.append(expr_power())
 
        return a[0] if len(a) == 1 else ['Division'] + a
 
    def expr_power():
        a = [expr_function()]
        if peek() == 'operator' and peek(True) == '^':
            skip()
            a.append(expr_function())
 
        return a[0] if len(a) == 1 else ['Power'] + a
 
    def expr_function():
        if peek() == 'function':
            return ['UnaryFunction', next().value, expr_parenthesis()]
 
        return expr_operand()
    
    def expr_operand():
        if peek() == 'lparen':
            return expr_parenthesis()
 
        elif peek() in ('variable', 'number'):
            return ('Operand', next().value)
 
        elif peek() == 'operator' and peek(True) == "-":
            skip()
            return ('Multiplication', ('Operand', -1), expr_operand())
        
        raise Exception("Operand erwartet")
 
    def expr_parenthesis():
        next('lparen')
        result = expression()
        next('rparen')
        return result
    
    result = expression()
    next('eot')
    return result
 
def instantiate(ast, ctx = globals()):
    if not isinstance(ast, (tuple, list)):
        return ast
    args = [instantiate(a, ctx) for a in ast[1:]]
    return ctx[ast[0]](*args) if isinstance(ast, (tuple,list)) else ast
    Angehängte Dateien Angehängte Dateien
     
Thema nicht erledigt
« [QUIZ#15] Jellysheep (C++) [2] | [QUIZ#16] Codefan (C) »

Ähnliche Themen

  1. [Quiz#13] OnlyFoo (Python)
    Von OnlyFoo im Forum Archiv
    Antworten: 0
    Letzter Beitrag: 17.01.10, 18:07
  2. [QUIZ#12] OnlyFoo (Python)
    Von OnlyFoo im Forum Archiv
    Antworten: 0
    Letzter Beitrag: 02.11.09, 17:35
  3. [Quiz#11] OnlyFoo (python)
    Von OnlyFoo im Forum Archiv
    Antworten: 2
    Letzter Beitrag: 25.10.09, 06:22
  4. [QUIZ#10] OnlyFoo (Python)
    Von OnlyFoo im Forum Archiv
    Antworten: 1
    Letzter Beitrag: 10.10.09, 23:10
  5. [QUIZ#09] OnlyFoo (Python)
    Von OnlyFoo im Forum Archiv
    Antworten: 0
    Letzter Beitrag: 20.07.09, 12:34