Funktionsparser

Hier den folgenden Text als pdf-Datei.

Motivation

Bei der Arbeit an meinem Plotterskript für Pstricks stieß ich auf die Problematik, dass ich eine Funktion mit mehreren Variablen zeichnen wollte. Dazu schaute ich als erstes in die Dokumentation für PST-3dplot, um zu sehen, wie es intern in Pstricks realisiert ist. Leider gab es hier nicht die Möglichkeit einfach als Parameter algebraic anzugeben, um in der gewohnten algebraischen Notation den Funktionsterm aufzuschreiben.

Da ich mich nicht so recht mit der umgekehrt-polnische-Notation (UPN) anfreunden konnte, schlug mir Stephan vor, doch einen Funktionsparser zu schreiben, der die algebraische Notation in die umgekehrt-polnische-Notation umwandelt. Dieses Skript eröffnet dem dem Plotterskript viele neue Möglichkeiten eröffnet, z.B. auch die Umwandlungen beliebiger Funktionsausdrücke in die UPN.

Tja, da stand ich nun vor einem großen Problem, was gelöst werden sollte. Wie geht man denn da heran? Was für einen Algorithmus nutzt man dafür? Ist es nicht doch einfacher die UPN zu lernen und sich nicht einen Algorithmus auszudenken zu müssen? Aber man wächst ja an seinen Aufgaben...

Zu zweit spielten wir mehrere Ansätze durch, bis wir dann auf die folgende Lösung kamen:

Der Algorithmus

Ein algebraischer Ausdruck wird zunächst in seine Einzelteile aufgeteilt. Handelt es sich um eine Zahl mit einem Vorzeichen, eine Rechenoperation, eine Funktion, einen Klammerterm öffnende oder schließende Klammer?

Dies ist die Funktion des tokenizers. Die vom tokenizer gefundenen Formelteile werden anschließend vom regelwerk schrittweise zu größeren Termen zusammengesetzt. Dies geschieht nach den Regeln der Mathematik, z.B. Punkt vor Strichrechnung, und wird solange wiederholt, bis nur noch ein Term übrig bleibt oder die Funktion regelwerk einen Fehler findet.

Die Regeln der regelwerk-Funktion sind die folgenden:

Ausdrücke der Form ( Liste ) werden in den Ausdruck Liste verwandelt und das Regelwerk wird rekursiv auf die Liste angewendet.
Ausdrücke der Form Term Term werden in den Term (Term Term) verwandelt.
Ausdrücke der Form Term * Term oder Term / Term werden in den Term (Term * Term) bzw. (Term / Term) verwandelt.
Ausdrücke der Form Funktion Term werden in den Term (Funktion (Term)) verwandelt.
Ausdrücke der Form Term + Term oder Term - Term werden in den Term (Term + Term) bzw. (Term - Term) verwandelt.
Ausdrücke der Form -Term werden in den Term (0 - Term) verwandelt.

Die Funktion regelwerk sucht in jedem Durchlauf eine anwendbare Regel und führt diese aus. Dabei wird die Regel mit der kleinsten Nummer zuerst probiert. Trifft eine Regel zu, so wird diese angewendet und die Funktion startet neu mit der ersten Regel. Wenn eine Regel an mehreren Stellen anwendbar ist, so wird sie an der am weitesten links stehenden Stelle angewendet. Der Prozess wird wiederholt, bis nur noch ein Term übrig ist oder keine Regel mehr anwendbar ist. Im letzteren Fall war die Ausgangsformel nicht gültig und es wird ein Fehler ausgegeben.

Mit dieser regelwerk-Funktion wird gleichzeitig parallel ein Rechenbaum aufgebaut, bei dem im Knoten immer die Operation steht. Die Blätter bestehen aus Zahlen oder Variablen. Bei den Funktionen wird der Funktionsname der Knoten und der rechte Teilbaum bleibt undefiniert.

Die Funktion polnisch liefert dann die UPN, indem der aufgebaute Rechenbaum ausgelesen wird.

Das Abfallprodukt des regelwerk ist ein vollständig geklammerter Rechenausdruck.

Beispiele

Hier nun ein paar Beispiele:


Rechenausdruck	Rechenausdruck, vollst ändig geklammert	UPN

2*(3+4)	(2*(3+4))	2 3 4 + *

2+(x+2)^2	(2+((x+2)^2))	2 x 2 + 2 ^ +

(x+2)^2+2	(((x+2)^2)+2)	x 2 + 2 ^ 2 +

2+sin(2(x+3))3	(2+(sin((2(x+3))3)))	2 2 x 3 + * 3 * sin +

Tab. 1: Beispiele für den Funktionsparser

Programmcode

Und hier nun der vollständige Programmcode in Perl:

funktionsparser.pl
1 #!/usr/bin/perl -w 2 ################################################################## 3 # 4 # Funktionsparser 5 # 6 # Autoren: Stephan Hoehrmann, Xenia Rendtel 7 # 8 # VERSION 2 9 # Letzte Aenderung: 20.07.2009 10 # 11 # Dieser Parser ersetzt eine Funktion in umgekehrter polnischer Notation. 12 # dazu wird ein Baum nach dem folgenden Prinzip erstellt: 13 # Zunaechst wird die Zeichenkette mit der Funktion tokenizer in 14 # ihre Einzelteile zerlegt. 15 # Dabei wird unterschieden, ob es sich um einen Term, einen Operator, 16 # eine Funktion, eine oeffnende oder schliessende Klammer oder eine Variable handelt. 17 # Dann wird diese neu gewonnene Liste mit dem 18 # folgenden Algorithmus in einen Baum verwandelt: 19 # 20 # 0. Solange Liste nicht leer, suche von Position 0 aufsteigend 21 # durch die Liste mit folgenden Kriterien: 22 # 1. ( Liste ) wird zu einem Ausdruck der Form Liste ohne Klammern, 23 # auf die der Algorithmus erneut angewendet wird. goto 0. 24 # 2. Term\|Variable ^ Term\|Variable wird zu einem Term mit dem Inhalt 25 # (Term\|Variable ^ Term\|Variable) 26 # 3. Term\|Variable mal\|geteilt Term\|Variable wird zu einem Term 27 # mit dem Inhalt (Term\|Variable mal\|geteilt Term\|Variable). goto 0 28 # 4. Funktion Term\|Variable wird zu einem Term 29 # mit dem Inhalt (Funktion Term\|Variable). goto 0 30 # 5. Term\|Variable plus\|minus Term\|Variable wird zu einem Term 31 # mit dem Inhalt (Term\|Variable plus\|minus Term\|Variable). goto 0 32 # 6. plus\|minus Variable wird zu einem Term 33 # mit dem Inhalt (0 plus\|minus Variable). goto 0 34 # 7. Fertig! 35 # Es wird dabei Schritt fuer Schritt ein Baum mit aufgebaut. 36 ################################################################## 37 use strict; 38 use warnings; 39 use Data::Dumper; 40 use Math::Trig; 41 use Math::Complex; 42 use POSIX qw /floor ceil/; 43 44 my @funktionpolnisch; 45 46 ### Wichtige Funktionen: 47 48 sub abrunden { 49 my ( $wert, $schritt ) = @_; 50 return $schritt * floor( $wert / $schritt ); 51 } 52 53 sub aufrunden { 54 my ( $wert, $schritt ) = @_; 55 return $schritt * ceil( $wert / $schritt ); 56 } 57 58 sub fakultaet { 59 my ($n) = shift; 60 61 if ( ( $n == 1 ) \|\| ( $n == 0 ) ) { 62 return 1; 63 } 64 elsif ( $n < 0 ) { 65 return "Fehler"; 66 } 67 else { 68 return $n * fakultaet( $n - 1 ); 69 } 70 } 71 72 sub round { 73 my ($zahl) = shift; 74 return int( $zahl + 0.5 ); 75 } 76 77 # Die Funktion tokenizer erstellt aus einem String eine 78 # Liste mit den einzelnen Rechenoperationen des Strings 79 sub tokenizer { 80 my ($text) = @_; 81 my ( $token, $vorzeichen ); 82 my @listevontokens; 83 $vorzeichen = 1; 84 $text =~ s/ //g; 85 $text = lc($text); 86 while ( $text ne "" ) { 87 if ( ( $text =~ /^([-+]?[0-9]+(\.[0-9]+)?([eE][-+]?[0-9]+)?)/ ) 88 && ( $vorzeichen == 1 ) ) 89 { 90 91 # Zahlen mit Vorzeichen 92 $token = $1; 93 $vorzeichen = 0; 94 push @listevontokens, 95 { 96 'Inhalt' => $token, 97 'Typ' => "Term", 98 'Baum' => { 99 'knoten' => $token, 100 'links' => undef, 101 'rechts' => undef 102 } 103 }; 104 } 105 elsif (( $text =~ /^([0-9]+(\.[0-9]+)?([eE][-+]?[0-9]+)?)/ ) 106 && ( $vorzeichen == 0 ) ) 107 { 108 109 # Zahlen ohne Vorzeichen 110 $token = $1; 111 $vorzeichen = 0; 112 push @listevontokens, 113 { 114 'Inhalt' => $token, 115 'Typ' => "Term", 116 'Baum' => { 117 'knoten' => $token, 118 'links' => undef, 119 'rechts' => undef 120 } 121 }; 122 } 123 124 elsif ( $text =~ /^(\^)/ ) { 125 126 # Hochzeichen 127 $token = $1; 128 $vorzeichen = 1; 129 push @listevontokens, 130 { 131 'Inhalt' => $token, 132 'Typ' => "hoch", 133 'Baum' => { 134 'knoten' => $token, 135 'links' => undef, 136 'rechts' => undef 137 } 138 }; 139 } 140 141 elsif ( $text =~ /^([-])/ ) { 142 143 # Operatoren 144 $token = $1; 145 $vorzeichen = 1; 146 push @listevontokens, 147 { 148 'Inhalt' => $token, 149 'Typ' => "minus", 150 'Baum' => { 151 'knoten' => $token, 152 'links' => undef, 153 'rechts' => undef 154 } 155 }; 156 } 157 elsif ( $text =~ /^([+])/ ) { 158 159 # Operatoren 160 $token = $1; 161 $vorzeichen = 1; 162 push @listevontokens, 163 { 164 'Inhalt' => $token, 165 'Typ' => "plus", 166 'Baum' => { 167 'knoten' => $token, 168 'links' => undef, 169 'rechts' => undef 170 } 171 }; 172 } 173 elsif ( $text =~ /^([])/ ) { 174 175 # Operatoren 176 $token = $1; 177 $vorzeichen = 1; 178 push @listevontokens, 179 { 180 'Inhalt' => $token, 181 'Typ' => "mal", 182 'Baum' => { 183 'knoten' => $token, 184 'links' => undef, 185 'rechts' => undef 186 } 187 }; 188 } 189 elsif ( $text =~ /^([:\/])/ ) { 190 191 # Operatoren 192 $token = $1; 193 $vorzeichen = 1; 194 push @listevontokens, 195 { 196 'Inhalt' => $token, 197 'Typ' => "geteilt", 198 'Baum' => { 199 'knoten' => $token, 200 'links' => undef, 201 'rechts' => undef 202 } 203 }; 204 } 205 elsif ( $text =~ 206 /^(sin\|cos\|tan\|acos\|asin\|log\|ln\|ceiling\|floor\|truncate\|round\|sqrt\|abs\|fact\|exp)/ 207 ) 208 { 209 210 # Funktionen 211 $token = $1; 212 $vorzeichen = 1; 213 push @listevontokens, 214 { 215 'Inhalt' => $token, 216 'Typ' => "Funktion", 217 'Baum' => { 218 'knoten' => $token, 219 'links' => undef, 220 'rechts' => undef 221 } 222 }; 223 } 224 elsif ( $text =~ /^(\()/ ) { 225 226 # oeffnende Klammer 227 $token = $1; 228 $vorzeichen = 1; 229 push @listevontokens, 230 { 231 'Inhalt' => $token, 232 'Typ' => "(", 233 'Baum' => { 234 'knoten' => $token, 235 'links' => undef, 236 'rechts' => undef 237 } 238 }; 239 } 240 elsif ( $text =~ /^(\))/ ) { 241 242 # schliessende Klammer 243 $token = $1; 244 $vorzeichen = 0; 245 push @listevontokens, 246 { 247 'Inhalt' => $token, 248 'Typ' => ")", 249 'Baum' => { 250 'knoten' => $token, 251 'links' => undef, 252 'rechts' => undef 253 } 254 }; 255 } 256 257 elsif ( $text =~ /^([a-z][0-9a-z])/ ) { 258 259 # Variable 260 $token = $1; 261 $vorzeichen = 0; 262 push @listevontokens, 263 { 264 'Inhalt' => $token, 265 'Typ' => "Term", 266 'Baum' => { 267 'knoten' => $token, 268 'links' => undef, 269 'rechts' => undef 270 } 271 }; 272 } 273 else { 274 275 # Rest 276 $token = $text; 277 $vorzeichen = 1; 278 push @listevontokens, 279 { 280 'Inhalt' => $token, 281 'Typ' => "Rest", 282 'Baum' => { 283 'knoten' => $token, 284 'links' => undef, 285 'rechts' => undef 286 } 287 }; 288 } 289 290 #print "Token " . $token . "\n"; 291 $text = substr $text, length $token; 292 } 293 return @listevontokens; 294 } 295 296 # Ein vollstaendig geklammerter Ausdruck wird ausgegeben. 297 sub ausgabeliste { 298 my (@liste) = @_; 299 my $listenlaenge = scalar @liste; 300 my $i; 301 printf("'"); 302 for ( $i = 0 ; $i < $listenlaenge ; $i++ ) { 303 printf( "%s", $liste[$i]{'Inhalt'} ); 304 printf(" ") if ( $i < $listenlaenge - 1 ); 305 } 306 print "'\n "; 307 308 } 309 310 # Der eigentliche Algorithmus 311 sub regelwerk { 312 my (@liste) = @_; 313 my ( @klammerterm, $i, $j, $gefunden, $klammerauf, $klammerzu, 314 $klammertiefe ); 315 316 do { 317 $gefunden = 0; 318 if ( !$gefunden ) { 319 320 $klammerzu = $klammerauf = $klammertiefe = 0; 321 322 # Klammern: 323 # Wenn eine oeffnende Klammer gefunden wurde, dann wird der Zaehler klammertiefe erhoeht, 324 # bei einer schliessenden Klammer erniedrigt. 325 # Bei korrekter Klammerung ist der Zaehler am Ende 0 326 # und es wird die regelwerk-Funktion auf den Inhalt der Klammer angewendet. 327 328 for ( $i = 0 ; $i < scalar @liste ; $i++ ) { 329 330 if ( $liste[$i]{'Typ'} eq "(" ) { 331 if ( ( $klammertiefe == 0 ) ) { 332 $klammerauf = $i; 333 } 334 $klammertiefe++; 335 } 336 if ( $liste[$i]{'Typ'} eq ")" ) { 337 $klammertiefe--; 338 if ( $klammertiefe == 0 ) { 339 $klammerzu = $i; 340 } 341 } 342 343 } 344 ## Fehler wenn klammertiefe != 0 muss noch bearbeitet werden 345 346 if ( $klammerauf != $klammerzu ) { 347 348 @klammerterm = (); 349 for ( $j = $klammerauf + 1 ; $j <= $klammerzu - 1 ; $j++ ) { 350 push @klammerterm, 351 { 352 'Inhalt' => $liste[$j]{'Inhalt'}, 353 'Typ' => $liste[$j]{'Typ'}, 354 'Baum' => { 355 'knoten' => $liste[$j]{'Baum'}{'knoten'}, 356 'links' => undef, 357 'rechts' => undef 358 } 359 }; 360 } 361 362 splice( @liste, $klammerauf, $klammerzu - $klammerauf + 1, 363 regelwerk(@klammerterm) ); 364 $gefunden = 1; 365 366 } 367 368 } 369 if ( !$gefunden ) { 370 371 # Potenzieren 372 for ( $i = 0 ; $i < scalar @liste - 2 ; $i++ ) { 373 374 if ( ( $liste[$i]{'Typ'} eq "Term" ) 375 && ( $liste[ $i + 1 ]{'Typ'} eq "hoch" ) 376 && ( $liste[ $i + 2 ]{'Typ'} eq "Term" ) 377 && ( !$gefunden ) ) 378 { 379 380 splice( 381 @liste, $i, 3, 382 { 383 'Inhalt' => "(" 384 . $liste[$i]{'Inhalt'} 385 . $liste[ $i + 1 ]{'Inhalt'} 386 . $liste[ $i + 2 ]{'Inhalt'} . ")", 387 'Typ' => "Term", 388 'Baum' => { 389 'knoten' => $liste[ $i + 1 ]{'Baum'}{'knoten'}, 390 'links' => $liste[$i]{'Baum'}, 391 'rechts' => $liste[ $i + 2 ]{'Baum'} 392 } 393 } 394 ); 395 $gefunden = 1; 396 } 397 } 398 } 399 if ( !$gefunden ) { 400 401 # Multiplikation und Division 402 for ( $i = 0 ; $i < scalar @liste - 2 ; $i++ ) { 403 if ( 404 ( $liste[$i]{'Typ'} eq "Term" ) 405 && ( ( $liste[ $i + 1 ]{'Typ'} eq "mal" ) 406 \|\| ( $liste[ $i + 1 ]{'Typ'} eq "geteilt" ) ) 407 && ( $liste[ $i + 2 ]{'Typ'} eq "Term" ) 408 && ( !$gefunden ) 409 ) 410 { 411 splice( 412 @liste, $i, 3, 413 { 414 'Inhalt' => "(" 415 . $liste[$i]{'Inhalt'} 416 . $liste[ $i + 1 ]{'Inhalt'} 417 . $liste[ $i + 2 ]{'Inhalt'} . ")", 418 'Typ' => "Term", 419 'Baum' => { 420 'knoten' => $liste[ $i + 1 ]{'Baum'}{'knoten'}, 421 'links' => $liste[$i]{'Baum'}, 422 'rechts' => $liste[ $i + 2 ]{'Baum'} 423 } 424 } 425 ); 426 $gefunden = 1; 427 } 428 } 429 } 430 if ( !$gefunden ) { 431 432 # Funktion 433 for ( $i = 0 ; $i < scalar @liste - 1 ; $i++ ) { 434 if ( ( $liste[$i]{'Typ'} eq "Funktion" ) 435 && ( $liste[ $i + 1 ]{'Typ'} eq "Term" ) 436 && ( !$gefunden ) ) 437 { 438 if ( $liste[$i]{'Inhalt'} eq "exp" ) { 439 splice( 440 @liste, $i, 2, 441 { 442 'Inhalt' => "(" 443 . exp(1) . "\^" 444 . $liste[ $i + 1 ]{'Inhalt'} . ")", 445 'Typ' => "Term", 446 'Baum' => { 447 'knoten' => "^", 448 'links' => { 449 'knoten' => exp(1), 450 'links' => undef, 451 'rechts' => undef 452 }, 453 'rechts' => $liste[ $i + 1 ]{'Baum'} 454 } 455 } 456 ); 457 } 458 else { 459 splice( 460 @liste, $i, 2, 461 { 462 'Inhalt' => "(" 463 . $liste[$i]{'Inhalt'} 464 . $liste[ $i + 1 ]{'Inhalt'} . ")", 465 'Typ' => "Term", 466 'Baum' => { 467 'knoten' => $liste[$i]{'Baum'}{'knoten'}, 468 'links' => $liste[ $i + 1 ]{'Baum'}, 469 'rechts' => undef 470 } 471 } 472 ); 473 } 474 $gefunden = 1; 475 } 476 } 477 } 478 if ( !$gefunden ) { 479 480 # Addition und Subtraktion 481 for ( $i = 0 ; $i < scalar @liste - 2 ; $i++ ) { 482 if ( 483 ( $liste[$i]{'Typ'} eq "Term" ) 484 && ( ( $liste[ $i + 1 ]{'Typ'} eq "plus" ) 485 \|\| ( $liste[ $i + 1 ]{'Typ'} eq "minus" ) ) 486 && ( $liste[ $i + 2 ]{'Typ'} eq "Term" ) 487 && ( !$gefunden ) 488 ) 489 { 490 splice( 491 @liste, $i, 3, 492 { 493 'Inhalt' => "(" 494 . $liste[$i]{'Inhalt'} 495 . $liste[ $i + 1 ]{'Inhalt'} 496 . $liste[ $i + 2 ]{'Inhalt'} . ")", 497 'Typ' => "Term", 498 'Baum' => { 499 'knoten' => $liste[ $i + 1 ]{'Baum'}{'knoten'}, 500 'links' => $liste[$i]{'Baum'}, 501 'rechts' => $liste[ $i + 2 ]{'Baum'} 502 } 503 } 504 ); 505 $gefunden = 1; 506 } 507 } 508 } 509 if ( !$gefunden ) { 510 511 # Term mit Vorzeichen 512 for ( $i = 0 ; $i < scalar @liste - 1 ; $i++ ) { 513 if ( 514 ( 515 ( $liste[$i]{'Typ'} eq "plus" ) 516 \|\| ( $liste[$i]{'Typ'} eq "minus" ) 517 ) 518 && ( $liste[ $i + 1 ]{'Typ'} eq "Term" ) 519 ) 520 { 521 splice( 522 @liste, $i, 2, 523 { 524 'Inhalt' => "(0" 525 . $liste[$i]{'Inhalt'} 526 . $liste[ $i + 1 ]{'Inhalt'} . ")", 527 'Typ' => "Term", 528 'Baum' => { 529 'knoten' => $liste[$i]{'Baum'}{'knoten'}, 530 'links' => { 531 'knoten' => 0, 532 'links' => undef, 533 'rechts' => undef 534 }, 535 'rechts' => $liste[ $i + 1 ]{'Baum'} 536 } 537 } 538 ); 539 $gefunden = 1; 540 } 541 } 542 } 543 544 } while ($gefunden); 545 546 ausgabeliste(@liste); 547 return @liste; 548 } 549 550 # polnische Notation wird ausgegeben. 551 sub polnisch { 552 my $ref = shift; 553 554 # suche links (rekursiv) 555 if ( defined( $$ref{'links'} ) ) { 556 polnisch( $$ref{'links'} ); 557 } 558 559 # suche rechts (rekursiv) 560 if ( defined( $$ref{'rechts'} ) ) { 561 polnisch( $$ref{'rechts'} ); 562 } 563 564 # Ausgabe des Knotens 565 print " $$ref{'knoten'}"; 566 } 567 568 sub rechenbaum_ausrechnen { 569 my $baum = shift; 570 my $variablen = shift; 571 572 print $$baum{'knoten'} . "\n"; 573 if ( $$baum{'knoten'} eq "" ) { 574 return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) 575 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen ); 576 } 577 elsif ( $$baum{'knoten'} eq ":" ) { 578 return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) / 579 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen ); 580 } 581 582 elsif ( $$baum{'knoten'} eq "/" ) { 583 return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) / 584 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen ); 585 } 586 elsif ( $$baum{'knoten'} eq "+" ) { 587 return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) + 588 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen ); 589 } 590 elsif ( $$baum{'knoten'} eq "^" ) { 591 return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) 592 *rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen ); 593 } 594 595 elsif ( $$baum{'knoten'} eq "-" ) { 596 return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) - 597 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen ); 598 } 599 elsif ( defined $$variablen{ $$baum{'knoten'} } ) { 600 return $$variablen{ $$baum{'knoten'} }; 601 } 602 elsif ( $$baum{'knoten'} eq "sin" ) { 603 return sin( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 604 } 605 elsif ( $$baum{'knoten'} eq "cos" ) { 606 return cos( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 607 } 608 elsif ( $$baum{'knoten'} eq "tan" ) { 609 return tan( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 610 } 611 elsif ( $$baum{'knoten'} eq "asin" ) { 612 return arcsin( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 613 } 614 elsif ( $$baum{'knoten'} eq "acos" ) { 615 return acos( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 616 } 617 elsif ( $$baum{'knoten'} eq "log" ) { 618 return log( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 619 } 620 elsif ( $$baum{'knoten'} eq "ceiling" ) { 621 return aufrunden( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ), 622 1 ); 623 } 624 elsif ( $$baum{'knoten'} eq "floor" ) { 625 return abrunden( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ), 626 1 ); 627 } 628 elsif ( $$baum{'knoten'} eq "truncate" ) { 629 if ( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) < 0 ) { 630 return aufrunden( 631 rechenbaum_ausrechnen( $$baum{'links'}, $variablen ), 1 ); 632 } 633 else { 634 return abrunden( 635 rechenbaum_ausrechnen( $$baum{'links'}, $variablen ), 1 ); 636 } 637 638 } 639 elsif ( $$baum{'knoten'} eq "round" ) { 640 return round( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 641 } 642 643 elsif ( $$baum{'knoten'} eq "sqrt" ) { 644 return sqrt( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 645 } 646 647 elsif ( $$baum{'knoten'} eq "abs" ) { 648 return abs( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 649 } 650 651 elsif ( $$baum{'knoten'} eq "fact" ) { 652 return fakultaet( 653 rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 654 } 655 656 elsif ( $$baum{'knoten'} eq "exp" ) { 657 return exp( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) ); 658 } 659 660 else { # ACHTUNG: Keine Fehlerbehandlung!!! 661 return $$baum{'knoten'}; 662 } 663 664 } 665 666 sub funktionsausgabe { 667 my $funktionsausdruck = shift; 668 my @ergebnis = regelwerk( tokenizer($funktionsausdruck) ); 669 670 if ( scalar @ergebnis != 1 ) { 671 printf("Fehler \n"); 672 ausgabeliste(@ergebnis); 673 } 674 else { 675 polnisch( $ergebnis[0]{'Baum'} ); 676 print "\n"; 677 } 678 } 679 680 my @ergebnis = regelwerk( tokenizer("(x-2)(x+2)") ); 681 print rechenbaum_ausrechnen( 682 $ergebnis[0]{'Baum'}, 683 { 684 'x' => 2, 685 'y' => 2, 686 'pi' => pi() 687 } 688 ) 689 . "\n"; 690 691 funktionsausgabe("(x-2)*(x+2)");

funktionsparser.pl

#!/usr/bin/perl -w
##################################################################
#
# Funktionsparser
#
# Autoren: Stephan Hoehrmann, Xenia Rendtel
#
# VERSION 2
# Letzte Aenderung: 20.07.2009
#
# Dieser Parser ersetzt eine Funktion in umgekehrter polnischer Notation.
# dazu wird ein Baum nach dem folgenden Prinzip erstellt:
# Zunaechst wird die Zeichenkette mit der Funktion tokenizer in
# ihre Einzelteile zerlegt.
# Dabei wird unterschieden, ob es sich um einen Term, einen Operator,
# eine Funktion, eine oeffnende oder schliessende Klammer oder eine Variable handelt.
# Dann wird diese neu gewonnene Liste mit dem
# folgenden Algorithmus in einen Baum verwandelt:
#
# 0. Solange Liste nicht leer, suche von Position 0 aufsteigend
# durch die Liste mit folgenden Kriterien:
# 1. ( Liste ) wird zu einem Ausdruck der Form Liste ohne Klammern,
# auf die der Algorithmus erneut angewendet wird. goto 0.
# 2. Term|Variable ^ Term|Variable wird zu einem Term mit dem Inhalt
# (Term|Variable ^ Term|Variable)
# 3. Term|Variable mal|geteilt Term|Variable wird zu einem Term
# mit dem Inhalt (Term|Variable mal|geteilt Term|Variable). goto 0
# 4. Funktion Term|Variable wird zu einem Term
# mit dem Inhalt (Funktion Term|Variable). goto 0
# 5. Term|Variable plus|minus Term|Variable wird zu einem Term
# mit dem Inhalt (Term|Variable plus|minus Term|Variable). goto 0
# 6. plus|minus Variable wird zu einem Term
# mit dem Inhalt (0 plus|minus Variable). goto 0
# 7. Fertig!
# Es wird dabei Schritt fuer Schritt ein Baum mit aufgebaut.
##################################################################
use strict;
use warnings;
use Data::Dumper;
use Math::Trig;
use Math::Complex;
use POSIX qw /floor ceil/;

my @funktionpolnisch;

### Wichtige Funktionen:

sub abrunden {
my ( $wert, $schritt ) = @_;
return $schritt * floor( $wert / $schritt );
}

sub aufrunden {
my ( $wert, $schritt ) = @_;
return $schritt * ceil( $wert / $schritt );
}

sub fakultaet {
my ($n) = shift;

if ( ( $n == 1 ) || ( $n == 0 ) ) {
return 1;
}
elsif ( $n < 0 ) {
return "Fehler";
}
else {
return $n * fakultaet( $n - 1 );
}
}

sub round {
my ($zahl) = shift;
return int( $zahl + 0.5 );
}

# Die Funktion tokenizer erstellt aus einem String eine
# Liste mit den einzelnen Rechenoperationen des Strings
sub tokenizer {
my ($text) = @_;
my ( $token, $vorzeichen );
my @listevontokens;
$vorzeichen = 1;
$text =~ s/ //g;
$text = lc($text);
while ( $text ne "" ) {
if ( ( $text =~ /^([-+]?[0-9]+(\.[0-9]+)?([eE][-+]?[0-9]+)?)/ )
 && ( $vorzeichen == 1 ) )
{

 # Zahlen mit Vorzeichen
 $token = $1;
 $vorzeichen = 0;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "Term",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}
elsif (( $text =~ /^([0-9]+(\.[0-9]+)?([eE][-+]?[0-9]+)?)/ )
 && ( $vorzeichen == 0 ) )
{

 # Zahlen ohne Vorzeichen
 $token = $1;
 $vorzeichen = 0;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "Term",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}

elsif ( $text =~ /^(\^)/ ) {

 # Hochzeichen
 $token = $1;
 $vorzeichen = 1;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "hoch",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}

elsif ( $text =~ /^([-])/ ) {

 # Operatoren
 $token = $1;
 $vorzeichen = 1;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "minus",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}
elsif ( $text =~ /^([+])/ ) {

 # Operatoren
 $token = $1;
 $vorzeichen = 1;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "plus",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}
elsif ( $text =~ /^([*])/ ) {

 # Operatoren
 $token = $1;
 $vorzeichen = 1;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "mal",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}
elsif ( $text =~ /^([:\/])/ ) {

 # Operatoren
 $token = $1;
 $vorzeichen = 1;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "geteilt",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}
elsif ( $text =~
	/^(sin|cos|tan|acos|asin|log|ln|ceiling|floor|truncate|round|sqrt|abs|fact|exp)/
 )
{

 # Funktionen
 $token = $1;
 $vorzeichen = 1;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "Funktion",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}
elsif ( $text =~ /^(\()/ ) {

 # oeffnende Klammer
 $token = $1;
 $vorzeichen = 1;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "(",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}
elsif ( $text =~ /^(\))/ ) {

 # schliessende Klammer
 $token = $1;
 $vorzeichen = 0;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => ")",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}

elsif ( $text =~ /^([a-z][0-9a-z]*)/ ) {

 # Variable
 $token = $1;
 $vorzeichen = 0;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "Term",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}
else {

 # Rest
 $token = $text;
 $vorzeichen = 1;
 push @listevontokens,
 {
	'Inhalt' => $token,
	'Typ' => "Rest",
	'Baum' => {
	 'knoten' => $token,
	 'links' => undef,
	 'rechts' => undef
	}
 };
}

#print "Token " . $token . "\n";
$text = substr $text, length $token;
}
return @listevontokens;
}

# Ein vollstaendig geklammerter Ausdruck wird ausgegeben.
sub ausgabeliste {
my (@liste) = @_;
my $listenlaenge = scalar @liste;
my $i;
printf("'");
for ( $i = 0 ; $i < $listenlaenge ; $i++ ) {
printf( "%s", $liste[$i]{'Inhalt'} );
printf(" ") if ( $i < $listenlaenge - 1 );
}
print "'\n ";

}

# Der eigentliche Algorithmus
sub regelwerk {
my (@liste) = @_;
my ( @klammerterm, $i, $j, $gefunden, $klammerauf, $klammerzu,
 $klammertiefe );

do {
$gefunden = 0;
if ( !$gefunden ) {

 $klammerzu = $klammerauf = $klammertiefe = 0;

# Klammern:
# Wenn eine oeffnende Klammer gefunden wurde, dann wird der Zaehler klammertiefe erhoeht,
# bei einer schliessenden Klammer erniedrigt.
# Bei korrekter Klammerung ist der Zaehler am Ende 0
# und es wird die regelwerk-Funktion auf den Inhalt der Klammer angewendet.

 for ( $i = 0 ; $i < scalar @liste ; $i++ ) {

	if ( $liste[$i]{'Typ'} eq "(" ) {
	 if ( ( $klammertiefe == 0 ) ) {
		$klammerauf = $i;
	 }
	 $klammertiefe++;
	}
	if ( $liste[$i]{'Typ'} eq ")" ) {
	 $klammertiefe--;
	 if ( $klammertiefe == 0 ) {
		$klammerzu = $i;
	 }
	}

 }
 ## Fehler wenn klammertiefe != 0 muss noch bearbeitet werden

 if ( $klammerauf != $klammerzu ) {

	@klammerterm = ();
	for ( $j = $klammerauf + 1 ; $j <= $klammerzu - 1 ; $j++ ) {
	 push @klammerterm,
	 {
		'Inhalt' => $liste[$j]{'Inhalt'},
		'Typ' => $liste[$j]{'Typ'},
		'Baum' => {
		 'knoten' => $liste[$j]{'Baum'}{'knoten'},
		 'links' => undef,
		 'rechts' => undef
		}
	 };
	}

	splice( @liste, $klammerauf, $klammerzu - $klammerauf + 1,
		regelwerk(@klammerterm) );
	$gefunden = 1;

 }

}
if ( !$gefunden ) {

 # Potenzieren
 for ( $i = 0 ; $i < scalar @liste - 2 ; $i++ ) {

	if ( ( $liste[$i]{'Typ'} eq "Term" )
	 && ( $liste[ $i + 1 ]{'Typ'} eq "hoch" )
	 && ( $liste[ $i + 2 ]{'Typ'} eq "Term" )
	 && ( !$gefunden ) )
	{

	 splice(
		@liste, $i, 3,
		{
		 'Inhalt' => "("
			. $liste[$i]{'Inhalt'}
		 . $liste[ $i + 1 ]{'Inhalt'}
		 . $liste[ $i + 2 ]{'Inhalt'} . ")",
		 'Typ' => "Term",
		 'Baum' => {
			'knoten' => $liste[ $i + 1 ]{'Baum'}{'knoten'},
			'links' => $liste[$i]{'Baum'},
			'rechts' => $liste[ $i + 2 ]{'Baum'}
		 }
		}
		);
	 $gefunden = 1;
	}
 }
}
if ( !$gefunden ) {

 # Multiplikation und Division
 for ( $i = 0 ; $i < scalar @liste - 2 ; $i++ ) {
	if (
	 ( $liste[$i]{'Typ'} eq "Term" )
	 && ( ( $liste[ $i + 1 ]{'Typ'} eq "mal" )
		 || ( $liste[ $i + 1 ]{'Typ'} eq "geteilt" ) )
	 && ( $liste[ $i + 2 ]{'Typ'} eq "Term" )
	 && ( !$gefunden )
	 )
	{
	 splice(
		@liste, $i, 3,
		{
		 'Inhalt' => "("
			. $liste[$i]{'Inhalt'}
		 . $liste[ $i + 1 ]{'Inhalt'}
		 . $liste[ $i + 2 ]{'Inhalt'} . ")",
		 'Typ' => "Term",
		 'Baum' => {
			'knoten' => $liste[ $i + 1 ]{'Baum'}{'knoten'},
			'links' => $liste[$i]{'Baum'},
			'rechts' => $liste[ $i + 2 ]{'Baum'}
		 }
		}
		);
	 $gefunden = 1;
	}
 }
}
if ( !$gefunden ) {

 # Funktion
 for ( $i = 0 ; $i < scalar @liste - 1 ; $i++ ) {
	if ( ( $liste[$i]{'Typ'} eq "Funktion" )
	 && ( $liste[ $i + 1 ]{'Typ'} eq "Term" )
	 && ( !$gefunden ) )
	{
	 if ( $liste[$i]{'Inhalt'} eq "exp" ) {
		splice(
		 @liste, $i, 2,
		 {
			'Inhalt' => "("
			 . exp(1) . "\^"
			 . $liste[ $i + 1 ]{'Inhalt'} . ")",
			 'Typ' => "Term",
			 'Baum' => {
				'knoten' => "^",
				'links' => {
				 'knoten' => exp(1),
				 'links' => undef,
				 'rechts' => undef
				},
					'rechts' => $liste[ $i + 1 ]{'Baum'}
			}
		 }
		 );
	 }
	 else {
		splice(
		 @liste, $i, 2,
		 {
			'Inhalt' => "("
			 . $liste[$i]{'Inhalt'}
			. $liste[ $i + 1 ]{'Inhalt'} . ")",
			'Typ' => "Term",
			'Baum' => {
			 'knoten' => $liste[$i]{'Baum'}{'knoten'},
			 'links' => $liste[ $i + 1 ]{'Baum'},
			 'rechts' => undef
			}
		 }
		 );
	 }
	 $gefunden = 1;
	}
 }
}
if ( !$gefunden ) {

 # Addition und Subtraktion
 for ( $i = 0 ; $i < scalar @liste - 2 ; $i++ ) {
	if (
	 ( $liste[$i]{'Typ'} eq "Term" )
	 && ( ( $liste[ $i + 1 ]{'Typ'} eq "plus" )
		 || ( $liste[ $i + 1 ]{'Typ'} eq "minus" ) )
	 && ( $liste[ $i + 2 ]{'Typ'} eq "Term" )
	 && ( !$gefunden )
	 )
	{
	 splice(
		@liste, $i, 3,
		{
		 'Inhalt' => "("
			. $liste[$i]{'Inhalt'}
		 . $liste[ $i + 1 ]{'Inhalt'}
		 . $liste[ $i + 2 ]{'Inhalt'} . ")",
		 'Typ' => "Term",
		 'Baum' => {
			'knoten' => $liste[ $i + 1 ]{'Baum'}{'knoten'},
			'links' => $liste[$i]{'Baum'},
			'rechts' => $liste[ $i + 2 ]{'Baum'}
		 }
		}
		);
	 $gefunden = 1;
	}
 }
}
if ( !$gefunden ) {

 # Term mit Vorzeichen
 for ( $i = 0 ; $i < scalar @liste - 1 ; $i++ ) {
	if (
	 (
	 ( $liste[$i]{'Typ'} eq "plus" )
	 || ( $liste[$i]{'Typ'} eq "minus" )
	 )
	 && ( $liste[ $i + 1 ]{'Typ'} eq "Term" )
	 )
	{
	 splice(
		@liste, $i, 2,
		{
		 'Inhalt' => "(0"
			. $liste[$i]{'Inhalt'}
		 . $liste[ $i + 1 ]{'Inhalt'} . ")",
		 'Typ' => "Term",
		 'Baum' => {
			'knoten' => $liste[$i]{'Baum'}{'knoten'},
			'links' => {
			 'knoten' => 0,
			 'links' => undef,
			 'rechts' => undef
			},
				'rechts' => $liste[ $i + 1 ]{'Baum'}
		 }
		}
		);
	 $gefunden = 1;
	}
 }
}

} while ($gefunden);

ausgabeliste(@liste);
return @liste;
}

# polnische Notation wird ausgegeben.
sub polnisch {
my $ref = shift;

# suche links (rekursiv)
if ( defined( $$ref{'links'} ) ) {
polnisch( $$ref{'links'} );
}

# suche rechts (rekursiv)
if ( defined( $$ref{'rechts'} ) ) {
polnisch( $$ref{'rechts'} );
}

# Ausgabe des Knotens
print " $$ref{'knoten'}";
}

sub rechenbaum_ausrechnen {
my $baum = shift;
my $variablen = shift;

print $$baum{'knoten'} . "\n";
if ( $$baum{'knoten'} eq "*" ) {
return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) *
 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen );
}
elsif ( $$baum{'knoten'} eq ":" ) {
return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) /
 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen );
}

elsif ( $$baum{'knoten'} eq "/" ) {
return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) /
 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen );
}
elsif ( $$baum{'knoten'} eq "+" ) {
return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) +
 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen );
}
elsif ( $$baum{'knoten'} eq "^" ) {
return rechenbaum_ausrechnen( $$baum{'links'}, $variablen )
 **rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen );
}

elsif ( $$baum{'knoten'} eq "-" ) {
return rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) -
 rechenbaum_ausrechnen( $$baum{'rechts'}, $variablen );
}
elsif ( defined $$variablen{ $$baum{'knoten'} } ) {
return $$variablen{ $$baum{'knoten'} };
}
elsif ( $$baum{'knoten'} eq "sin" ) {
return sin( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}
elsif ( $$baum{'knoten'} eq "cos" ) {
return cos( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}
elsif ( $$baum{'knoten'} eq "tan" ) {
return tan( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}
elsif ( $$baum{'knoten'} eq "asin" ) {
return arcsin( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}
elsif ( $$baum{'knoten'} eq "acos" ) {
return acos( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}
elsif ( $$baum{'knoten'} eq "log" ) {
return log( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}
elsif ( $$baum{'knoten'} eq "ceiling" ) {
return aufrunden( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ),
		 1 );
}
elsif ( $$baum{'knoten'} eq "floor" ) {
return abrunden( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ),
		 1 );
}
elsif ( $$baum{'knoten'} eq "truncate" ) {
if ( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) < 0 ) {
 return aufrunden(
	rechenbaum_ausrechnen( $$baum{'links'}, $variablen ), 1 );
}
else {
 return abrunden(
	rechenbaum_ausrechnen( $$baum{'links'}, $variablen ), 1 );
}

}
elsif ( $$baum{'knoten'} eq "round" ) {
return round( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}

elsif ( $$baum{'knoten'} eq "sqrt" ) {
return sqrt( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}

elsif ( $$baum{'knoten'} eq "abs" ) {
return abs( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}

elsif ( $$baum{'knoten'} eq "fact" ) {
return fakultaet(
 rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}

elsif ( $$baum{'knoten'} eq "exp" ) {
return exp( rechenbaum_ausrechnen( $$baum{'links'}, $variablen ) );
}

else { # ACHTUNG: Keine Fehlerbehandlung!!!
return $$baum{'knoten'};
}

}

sub funktionsausgabe {
my $funktionsausdruck = shift;
my @ergebnis = regelwerk( tokenizer($funktionsausdruck) );

if ( scalar @ergebnis != 1 ) {
printf("Fehler \n");
ausgabeliste(@ergebnis);
}
else {
polnisch( $ergebnis[0]{'Baum'} );
print "\n";
}
}

my @ergebnis = regelwerk( tokenizer("(x-2)*(x+2)") );
print rechenbaum_ausrechnen(
$ergebnis[0]{'Baum'},
{
'x' => 2,
'y' => 2,
'pi' => pi()
}
)
. "\n";

funktionsausgabe("(x-2)*(x+2)");

Letzte Änderung: 22.08.2009: 11:57:15 von X. Rendtel