Eine Rechenaufgabe lösen mit PHP
Ich bastle gerade an einem kleinen Script, das aus einer Reihe Zahlen und arithmetischen Operatoren eine Rechenaufgabe erstellt und löst. Die Rechenaufgabe besteht nicht nur aus Additionen oder Subtraktionen, sondern enthält im einfachen Beispiel auch Multiplikationen, wobei dann auf die Punkt-vor-Strichrechung geachtet werden muss, was das ganze doch etwas erschwert.
Zuerst Beispielcode, damit ihr versteht was ich vorhabe:
<?php
$numbers = array(5, 19, 45, 6, 7, 21);
$operators = array('*', '+', '-', '*', '+');
// String bauen
$mathString = '';
foreach ($numbers as $id => $number) {
if ($id < count($numbers)-1) {
$mathString .= $number . $operators[$id];
} else {
$mathString .= $number;
}
}
// $mathString ist nun '5*19+45-6*7+21'
Nun ist die Aufgabe, aus dem String $mathString das Ergebnis auszurechnen. Die einfachste und schnellste Lösung ist natürlich eval() (oder vergleichbare Funktionen wie create_function() oder assert() ). Folgender Code löst die Rechenaufgabe und gibt das Ergebnis aus:
eval('echo ' . $mathString . ';');
Wenn man nun eval() und Konsorten nicht benutzen möchte oder darf oder kann, wie lautet dann der PHP Code, um eine solche Rechenaufgabe zu lösen? Die beiden oben gezeigten Arrays sind natürlich nur Beispiele, der Algorithmus sollte auch mit anderen Zahlen funktionieren.
Folgende Dinge sind zu beachten:
- $numbers ist ein Array aus unbekannt vielen Zahlen. Im einfachen Fall nur positive Zahlen, im etwas schwierigeren Fall auch negative
- $operators beinhaltet so viele Operatoren wie nötig sind für die Rechnung (also count($numbers)-1 viele). Um es nicht allzu komplex zu machen beschränken wir uns auf die Addition, Subtraktion und Multiplikation (+, – und *)
- Es gilt die Punkt vor Strichrechung zu beachten
- In unserem Fall hier kommen keine Klammern vor.
Wie sieht das ganze nun aus wenn auf die einfache, aber unschöne eval() Lösung verzichtet wird? eval() ist deshalb unschön weil die Zahlen und Operatoren oder gar der ganze $mathString aus Usereingaben kommen könnten, dann muss man sehr gut filtern um keine Sicherheitslücke beim Einsatz von eval() zu erstellen. Oder auf manchen Systemen ist eval() sogar verboten (disabled_functions).
Soll das pur in PHP geschrieben sein? Sonst könnte man diesen String nehmen und mit Javascript ausrechnen lassen.
Sascha
30 Mai 11 at 08:45
@Sascha: PHP in diesem Fall, ich brauche verlässlich das Ergebnis.
Michael Kliewe
30 Mai 11 at 08:46
Mal versucht: http://pastebin.com/heFtYN4x
Die kurze Erklärung: Erst nen AST bauen und den dann auflösen.
KingCrunch
30 Mai 11 at 09:16
in dem Fall könnte UPN (bzw. Engl. RPN) ein ansatz zur lösung sein.
auf phpclasses.org findet man dazu interessante Klassen die dein problem händeln könnten
http://www.phpclasses.org/package/5584-PHP-Evaluate-expressions-in-Reverse-Polish-Notation.html
http://www.phpclasses.org/package/4078-PHP-Evaluate-reverse-polish-notation-expressions.html
Uwe
30 Mai 11 at 09:35
Nimm die Datenbank zur Hilfe:
$math = ‚5*19+45-6*7+21‘;
$result = mysql_query(‚SELECT ‚ . $math . ‚ AS Ergebnis‘);
$ergebnis = mysql_fetch_object($result);
print $ergebnis->Ergebnis;
Michael
30 Mai 11 at 09:42
eh ja, datenbank verwenden ist ja auch viel sicherer als so n eval…
naja, ich versteh nicht, warum du n string daraus bastelst, und ihn dann parsen willst, und nicht die einzelnen elemente nimmst, und berechnest
pseudocode:
value = 0
for elementindex in numbers:
if operators[elementindex] == „+“:
value += int(numbers[elementindex])
else if operators[elementindex] == „-„:
value -= int(numbers[elementindex])
else if operators[elementindex] == „*“:
value *= int(numbers[elementindex])
else if operators[elementindex] == „/“:
value /= int(numbers[elementindex])
pharno
30 Mai 11 at 09:52
@pharno
Ja, die DB ist da wesentlich sicherer, als eval(). Da du die hier nur für einfache Rechenoperationen brauchst, legt man sich einen Benutzer an, der nur das kann, bzw. der nichts kann, was er nicht soll. Also nur ein paar kleine SELECT Anweisungen. Bei eval() kann jederzeit jeder beliebige Code ausgeführt werden. Das ist schon ein signifikanter Unterschied.
Michael
30 Mai 11 at 09:56
@pharno: Punkt-vor-Strich-Rechnung. Zudem ist der Algorithmus auch falsch:
$numbers = array(1,2);
$operators = array(‚*‘);
Richtig: 1 * 2
Bei dir: 0 * 1 (inklusive „undefined index“, wenn versucht wird den Operator mit elementindex=1 abzurufen)
KingCrunch
30 Mai 11 at 09:57
@Micheal: Nein, die DB ist nich sicherer (SQL-injection)
KingCrunch
30 Mai 11 at 09:58
@KingCrunch
Ja, die „SQL-injection“ gibt es 🙂
Deswegen auch die Beschneidung der Rechte. Da hier die DB nur zum Rechnen genutzt wird, bist du nicht auf eine produktive „MySQL Instanz“ angewiesen. Da sehe ich eigentlich keine Probleme.
Michael
30 Mai 11 at 10:03
Da ja die Operatoren (und die erlaubten Zahlen) bekannt sind, kann ich doch den auszuwertenden String ziemlich profan auf Gültigkeit prüfen. Sofern dann sichergestellt ist, daß die Eingabe valide ist sehe ich kein Problem darin, das dann durch eval() zu jagen.
Den „ich finde eval() blöd“-Disclaimer schenke ich mir mal…
danielj
30 Mai 11 at 10:09
Ich find Michaels Lösung sehr elegant uns sehe da auch kein Sicherheitsrisiko. Wie er sagt, muss man das Query ja nicht mit einem WRITE-User auf der Produktions-DB ausführen.
Phil
30 Mai 11 at 10:31
Kellerautomat!
Harald
30 Mai 11 at 11:55
Bzgl. Tonkentree aufbauen kann dir die PHP Tokenizer Funktion hilfreich sein: http://www.php.net/manual/de/function.token-get-all.php
Martin Prebio
30 Mai 11 at 12:17
Wie wärs mit nem Parser?
http://blog.oncode.info/2007/10/25/eine-eigene-programmiersprache-erschaffen-lexer-und-parser-in-php/
Henning
30 Mai 11 at 13:38
Wie wäre es dafür die Wolfram|Alpha API zu nutzen? Ich habe das noch nie ausprobiert, aber auf den ersten Blick jedenfalls sieht das meiner Meinung nach nach einem guten Ansatz aus:
http://products.wolframalpha.com/developers/
Grüße!
Jan M.
30 Mai 11 at 14:59
Ich habe mich auch an dem Problem versucht und einen Parser in PHP geschrieben: http://pastebin.com/yqQPUxPA
Die Fehlerbehandlung ist bisher nur rudimentär, aber ansonsten gibt er für dein Beispiel das korrekte Ergebnis aus.
Andre
30 Mai 11 at 20:24
Ist weder sonderlich elegant, noch schön, sondern mehr so die Holzhammermethode, aber kein eval und es rechnet richtig.
while(strpos($mathString, "*")!=false) {
preg_match_all("/([\d]+)\*([\d]+)/", $mathString, $x);
$mathString=str_replace($x[1][0].'*'.$x[2][0], (int)$x[1][0]*(int)$x[2][0], $mathString);
}
while(strpos($mathString, "/")!=false) {
preg_match_all("/([\d]+)\/([\d]+)/", $mathString, $x);
$mathString=str_replace($x[1][0].'/'.$x[2][0], (int)$x[1][0]/(int)$x[2][0], $mathString);
}
while(strpos($mathString, "-")!=false) {
preg_match_all("/([\d]+)\-([\d]+)/", $mathString, $x);
$mathString=str_replace($x[1][0].'-'.$x[2][0], (int)$x[1][0]-(int)$x[2][0], $mathString);
}
while(strpos($mathString, "+")!=false) {
preg_match_all("/([\d]+)\+([\d]+)/", $mathString, $x);
$mathString=str_replace($x[1][0].'+'.$x[2][0], (int)$x[1][0]+(int)$x[2][0], $mathString);
}
Oliver
30 Mai 11 at 22:13
Hier ist meine Lösung: http://pastebin.com/37LWPEzW
DSB
30 Mai 11 at 23:01
Tsts, da habe ich im Eifer des Gefechts doch glatt die genaue Aufgabenstellung überlesen.
<<Nun ist die Aufgabe, aus dem String $mathString das Ergebnis auszurechnen.
Ich bin in obiger Lösung davon ausgegangen, dass die Arrays gegeben sind. Aber gut, packen wir halt 2 preg_splits dazu: http://pastebin.com/DmQGU5rG
DSB
30 Mai 11 at 23:41
Nana, schön brav den String einlesen! 🙂
http://pastebin.com/R6gZ2pJ1
Paul
30 Mai 11 at 23:43
Yagni. 😉
DSB
31 Mai 11 at 00:56
Google! 🙂
http://pastebin.com/x2zyymHJ
Marcel
31 Mai 11 at 05:00
„funktional“ macht irgendwie keinen Spass mit PHP 🙁
http://pastebin.com/vw5VhN4C
Florian
31 Mai 11 at 07:48
Habe ein wenig an KingCrunchs Ansatz weitergebaut:
– http://pastebin.com/UmXeC1fN
Der Code steht nun irgendwo da, wo’s vom lustigen Hacken zu Arbeit übergehen würde.
mermshaus
31 Mai 11 at 08:46
😉 Hab auch mal gebastelt… Funktioniert auch mit Floats und negativen Zahlen
http://pastebin.com/BANdDB08
Johannes
31 Mai 11 at 13:29
Also wenn, dann würde ich schon versuchen, ein _ganzes_ Problem zu lösen. Also auch Klammerung und Division. Ohne entsteht sonst schnell ein Algorithmus (siehe obige preg-Lösung), die später nicht mehr zu verallgemeinern ist. Finde ich irgendwie Quark so an die Sache ranzugehen. Ich würde auch einen Baum der Operationen als Objekte aufbauen.
nik
31 Mai 11 at 15:06
Die Preglösung ist sogar sehr einfach zu verallgemeinern: Um Klammen einzubauen müsste man den Algorithmus nur rekursiv auf alle Klammernpaare anwenden – von Innen nach Außen.
Und Division ist bereits drin ;).
Johannes
31 Mai 11 at 15:35
Hier mit klammern 😉
http://pastebin.com/vH8fG0UF
Johannes
31 Mai 11 at 15:55
Wer Lust auf weitere Knobelaufgaben hat: http://www.mayflower.de/de/top-coders 🙂
Dan
31 Mai 11 at 21:43
@Dan Erledigt
Oliver
1 Jun 11 at 01:50
Wenn das Gewinnspiel vorbei ist, darfst du mir gerne mal c) erklären, Oliver. Ich stecke da SO übel fest… 🙁
Dan
1 Jun 11 at 13:57
Ich glaube, da ist auch ein Fehler in der Beschreibung, deshalb hab ich mal zwei Lösungen angegeben.
Oliver
1 Jun 11 at 14:01
Habe gerade die 3 Aufgaben gelöst, waren echt nicht ohne, aber durchaus machbar. c) ist leider zu ungenau, es gibt 2 Lösungen: die erste ist relativ einfach, und an der zweiten knoble ich noch, ist eine eklige Formel glaub ich. Mal sehen ob ich das noch rauskriege, sonst schick ich nur die einfache Lösung, ist auch richtig, wenn auch nicht optimal, aber danach wird ja nicht speziell gefragt.
Tolle Sache, hoffe du hast c) mittlerweile auch lösen können Dan.
Michael Kliewe
2 Jun 11 at 01:09
@Michael
Ich hatte bei c) reingeschrieben, dass die Formulierung „jeweils in einer eigenen Tabelle“ verwirrend ist, denn das könnte ja bedeuten, dass jeder User eine eigene Tabelle mit seinen Verbindungen hätte, was ja wahrscheinlich nicht gemeint war.
Formel hab ich auch keine, nur die Kardinalität auf die vorgegebene Einheit umgerechnet.
Oliver
2 Jun 11 at 01:29
@Oliver: Hmm, das fand ich nicht fraglich. Ich grüble drüber nach was mit „Kontakt“ gemeint ist. Wenn Person A die Person B als Kontakt hat, hat dann automatisch Person B auch Person A als Kontakt? Bei sozialen Netzen ist es häufig so dass diese Verbindung automatisch bidirektional ist. Aber in der Realität kann ich Michael Schumacher kennen, aber der kennt mich nicht. Das beeinflusst evtl. die Kardinalität wenn man solche bidirektionalen Verbindungen nicht doppelt speichern will.
Michael Kliewe
2 Jun 11 at 01:44
Ja, das auch, ich bin mal vom WKW Modell ausgegangen, also wenn zwei sich kennen sind das zwei Verbindungen.
Oliver
2 Jun 11 at 02:02
Ich hatte inzwischen irgendwann aufgegeben. a) und b) sind recht einfach, mit ein bisschen Hirnschmalz geht das. Bei c) musste ich passen, irgendwann hatte ich das Ergebnis 3 Tryte oder so 😉
Dan
2 Jun 11 at 17:52
c) ist meiner Ansicht nach einfach teilweise Auslegungssache. Ich sehe zwei Möglichkeiten, die Aufgabe zu lösen, die hinsichtlich der Formulierung aber beide gleich viel oder wenig Sinn ergeben. Ich habe die Lösung gewählt, die die Information, dass jeder Nutzer 33 Kontakte hat, berücksichtigt.
mermshaus
2 Jun 11 at 20:10
Ich würde den ganzen Quatsch einfach an Google als Suchanfrage schicken, sollen die sich doch damit rumschlagen:
http://www.google.de/?q=2%2B4*4*5%2B2 bzw.
http://www.google.de/?q=2%2B4*4*5%2B2#sclient=psy&hl=de&site=&source=hp&q=2%2B4*4*5%2B2&btnG=Google-Suche&aq=f&aqi=&aql=&oq=2%2B4*4*5%2B2&pbx=1
Dax
4 Jun 11 at 02:21
Alles außer eval ist nur die Neuerfindung des Rades. Warum sollte man sich einen eigenen Parser bauen der im Endeffekt unperformanter ist, zumal es auch mit eval „elegante“ Lösungswege gibt ( http://www.php.net/manual/de/function.eval.php#75389 ).
php
6 Jun 11 at 09:03
@php: dann rechne mal -4–3 mit eval, einige der vorgeschlagenen Lösungen schaffen das sehr wohl. Einen gewissen mehrwert gibt es hier also schon. Zudem ist eval oftmals auf webhostings zurecht deaktiviert.
Michael Engel
7 Jun 11 at 10:46
Doofe auto korrektur… -4 – – 3 (minus 4 minus minus 3)
Michael Engel
7 Jun 11 at 10:47
@Michael: ack!
Zumal es sich ja imho nur um ein kleines Rätsel handelt, nicht um Code der produktiv eingesetzt werden soll. Bei den gezeigten Ansätzen lässt sich aber z.B. auch sehr einfach weitere Funktionalität wie z.B. das Berechnen von Fakultäten, sinus, cosinus, tangens, was-auch-immer einbauen. Sicher, auch eval kann das – wenn man weitere php funktionen zulässt… aber ich kann mir sehr wohl einige Problemstellungen vorstellen, bei denen man mit eval selbst beim besten Willen keine chance mehr hat.
Johannes
7 Jun 11 at 10:53
Ich hätte ja die Grammatik in https://code.google.com/p/antlrphpruntime/ gekippt, das gibt zumindest Stilpunkte 🙂
Liebe Grüße
Johann
Johann-Peter Hartmann
27 Jun 11 at 16:57
Meine Lösung ist auf Codekickers zu sehen
http://codekicker.de/news/php-Rechenaufgabe-loesen-PHP-arithmetik-eval-rechenaufgabe
Mit Klammern und teilen.
Grüße,
Tekin
cYbercOsmOnauT
1 Aug 11 at 22:12
Achja.. an negative Zahlen und Fehlerbehandlung hatte ich auch gedacht 😉
cYbercOsmOnauT
1 Aug 11 at 22:36