C# Logische Auswertung eines Strings (Taschenrechner)

[DeepComputer]

Hallo,

ich bin etwas am Verzweifeln. Wie kann ich einen String, den ich in einen Taschenrechner eingebe, logisch-mathematisch auswerten?

Also wenn ich zB "6+(8*2)/3" eingebe, dass das Program den Ausdruck eben nach den Regeln der Mathematik auswertet und ein Ergebnis liefert.

Jeder Vorschlag ist erfreulich.
Hier ist das rep auf github https://github.com/OneMillionthUsername/primetest_gmp_wpf/issues/1

Die Methode ist fast leer und fehlerhaft. Ich versuche irgendwie den String zu splitten (in Zahlen und Operatoren) und dann wieder "logisch" zusammen zu führen, aber ich habe noch keinen Algorithmus gefunden. Ich bin etwas planlos.

 

[WingX]

Das Stichwort hier ist Parser. Lies dich da mal ein, das Thema ist unheimlich vielschichtig und spannend.

 

[efcoyote]

Wie schon erwähnt ist Parser das Zauberwort. Einen recht guten Einstieg bietet mMn Superpower. Dort findest du auch ein ausprogrammiertes Beispiel (IntCalc) für solche mathematischen Ausdrücke.

Etwas ausführlicher ist es in seinem Blog erklärt.

 

[benneq]

Parser ist die eine Sache. In diesem Fall würde ich noch den Suchbegriff AST (abstract syntax tree) vorschlagen. Das ist zwar eher was aus dem Compilerbau, aber genau genommen baust du da ja ein Art Mini Compiler für Mathematische Formeln, der z.B. Klammerung und Punkt-vor-Strich berücksichtigen soll.

 

[whyme]

Würde mit Regex.Split die Rechenzeichen trennen und dann die einzelen substrings nach den Rechenregeln (Klammern und Punkt vor Strich) abarbeiten.

 

[Amaoto]

Es gibt hier direkt von Microsoft einen Artikel darüber: https://docs.microsoft.com/de-de/ar...a-split-and-merge-expression-parser-in-csharp

Natürlich gibt's auch unzählige fertige Parser, die du nutzen könntest (z.B. "math parser" als Suchbegriff), je nachdem, was das Ziel ist.

 

[tollertyp]

Würde mit Regex.Split die Rechenzeichen trennen und dann die einzelen substrings nach den Rechenregeln (Klammern und Punkt vor Strich) abarbeiten.

Also manuelles Parsen kann man auch machen, aber ist nicht trivial. Hab so etwas mal Ende der 90er in Delphi gemacht. Schön war der Code nicht, aber hat einigermaßen funktioniert. Nur weil ich voreilig war, die Aufgabe hieß es einen Funktionsplotter zu machen. Und ich hab dann direkt angefangen. Aber eigentlich war die Aufgabe nur Funktionen dem Schema ax^4 + bx^3 + cx^2 + dx + e zu plotten, und dass man a, b, c, d und e halt als Nutzereingabe entgegennimmt.

 

[Yuuri]

Was Fertiges ist bspw. mXparser.

 

[Raijin]

Oh ja, Taschenrechner programmieren. Das hat vermutlich jeder mit Programmierhintergrund schon mal in der Schule, Ausbildung oder im Studium gemacht

Zu meiner Zeit habe ich das noch zu Fuß programmiert. String zunächst anhand der Klammern splitten und den Inhalt der Klammern abermals auf Klammern prüfen bzw. anschließend nach Punkt-vor-Strich anhand der Rechenzeichen splitten und mit der Auswertung beginnen.

In Spaghetticode sieht das aber wirklich hässlich aus, mit Rekursion ist es hingegen in wenigen Zeilen erledigt, die Auswerte-Funktion ruft sich also auf jeder Ebene - erst Klammern, dann Punkt, dann Strich - selbst auf und am Ende ribbeln sich die Ergebnisse nach oben hin wieder auf und man hat das Ergebnis. Ein Paradebeispiel für das Prinzip der Rekursion.


Tiefer sollten wir mit Tips aber nicht einsteigen, da ein Taschenrechner wie erwähnt nicht selten als Aufgabe in Schule/Ausbildung/Studium dient. Es geht dabei darum, das Problem zu verstehen und eine Lösung dafür zu erarbeiten, auch wenn das Ergebnis am Ende womöglich noch Fehler enthält (zB Punkt-vor-Strich nicht beachtet, o.ä.). Daher weiß ich auch nicht ob die Hinweise auf fertige Parser zielführend sind.

 

[DeepComputer]

Danke für die Tipps, werde ich mir dann durchlesen!

 

[Marcel^]

Wie Rajin schon anmerkt: Klammern (Rekursion!) vor Punkt vor Strich.

Drösel Dir das Problem abstrakt (wie in der Zeile oben) auf, unterteile es in einzelne Aufgaben, gehe diese nacheinander an.

 

[DeepComputer]

Tiefer sollten wir mit Tips aber nicht einsteigen, da ein Taschenrechner wie erwähnt nicht selten als Aufgabe in Schule/Ausbildung/Studium dient. Es geht dabei darum, das Problem zu verstehen und eine Lösung dafür zu erarbeiten, auch wenn das Ergebnis am Ende womöglich noch Fehler enthält (zB Punkt-vor-Strich nicht beachtet, o.ä.). Daher weiß ich auch nicht ob die Hinweise auf fertige Parser zielführend

Ja, ich glaube "irgendwie" würde ich es auch lösen können. Aber es würde bestimmt nicht schön aussehen ^^

 

[Raijin]

Je nachdem in welchem Kontext sich die Aufgabe bewegt - sei es ein privates Projekt, Schule, Ausbildung oder Studium - ist aber unter Umständen genau das das Ziel der Aufgabe. Es ist noch kein Programmierer vom Himmel gefallen, aber Copy&Paste kann jeder

Deswegen schrieb ich ja gerade, dass mein erster Ansatz damals hässlich, lang und unübersichtlich war, aber genau aus diesem Grund kam ich selbst und ohne Input von Außen auf die Idee mit der Rekursion, weil mir auffiel, dass ich ja eigentlich immer wieder dasselbe von neuem mache, endlos verschachtelt. Ein besseres Verständnis für rekursive Funktionsaufrufe kann man kaum bekommen, wenn man selbst merkt, dass man sonst mit ewig langem Spaghetticode gegen die Wand läuft.

Schöner Quellcode kommt in den seltensten Fällen durch Copy&Paste, sondern durch das Verständnis der Vorgänge und dementsprechende Optimierung durch Nutzung aller von der Programmierumgebung zur Verfügung gestellter Möglichkeiten. Genau das ist das Ziel solcher Aufgaben im Kontext des Lernens. Ansonsten kann man ja auch direkt den Windows-Taschenrechner benutzen, nicht wahr?

Das heißt im übrigen mitnichten, dass man sich später niemals öffentlicher Quellen oder vorgefertigter Libraries bedient. Es ist vollkommen legitim und auch sinnvoll, diese Abkürzung zu nehmen, wenn man denn die grundsätzlichen Fähigkeiten, die Ergebnisse zu reproduzieren (nicht zu verwechseln mit kopieren), sein Eigen nennen kann.

 

[BeBur]

Parser ist die eine Sache. In diesem Fall würde ich noch den Suchbegriff AST (abstract syntax tree) vorschlagen. Das ist zwar eher was aus dem Compilerbau, aber genau genommen baust du da ja ein Art Mini Compiler für Mathematische Formeln, der z.B. Klammerung und Punkt-vor-Strich berücksichtigen soll.

Ja, ganz genau so macht man das. Ich bezweifel auch, dass andere Ansätze für beliebige Rechnungen zielführend sind.
Hm, naja vllt auch mit Rekursion, ka .

 

[DeepComputer]

nope, fehl post.
Ist doch nicht so einfach...

 

[BeBur]

Falls das nicht klar geworden ist: So rein "linear" im Sinne einer For-Schleife kannst du das Problem nicht abhandeln, weil Ausdrücke beliebig verschachtelt sein können: (4+4)*((4-6/2)*2 +1).
Rekursion basiert ja darauf, dass du komplizierteres solange herunter brichst, bis du weißt, was du machen sollst.
rechne(4*4) ist z.B. klar. Aber rechne(4*(2+2)) wird zu rechne(4*rechne(2+2)). Etc. d.h. du musst dir überlegen, welche Fälle es allgemein geben kann und wie du die erkennst.
rechne(4*(2+2/4)) ist entsprechend rechne(4*rechne(2+rechne(2/4))). Die Funktion ruft sich andauernd selber auf, bis sie dann bei 2/4 ankommt, das ist 0,5 und wird zurück gegeben, dann hast du rechne(4*rechne(2+0,5)) und 2+0,5 da kannst du nun auch ein Ergebnis zurück geben. etc.

 

[DeepComputer]

Ja, mein Problem war, dass ich drauf gekommen bin, dass ich Rekursion nicht verstanden habe.
Ich sitze schon die ganze Zeit an diesem Programm und hab schon 2 mal oder so von neu angefangen.
Es hat so halbwegs funktioniert und dann hab ich mich die ganze Zeit gewundert warum der compiler wieder rückwärts läuft.. Ich hab dann nachgelesen, dass die Rekursion eben alles irgendwie auch rückwärts durchläuft. Dann hab ich die rekursiven Aufrufe durch "return input" ersetzt

Also es ist echt nicht so leicht wie man meinen möchte! Ich hätte mir oft ein Befehl gewunschen um die Rekursionsschleife sofort zu verlassen.

 

[BeBur]

Ich hätte mir oft ein Befehl gewunschen um die Rekursionsschleife sofort zu verlassen.

Das geht aus prinzipiellen Gründen nicht und ist auch nicht sinnvoll. Wenn ich dich richtig verstehe.
Du könntest zum ausprobieren ganz simpel inputs wie "4+5+2-6" rekursiv ausrechnen lassen.

 

[Raijin]

Rekursion läuft in etwa so:

ReverseString(string s)
{
   if (s.Length > 0)
   {
      return s[s.Length - 1] + ReverseString(s.Substring(0, s.Length - 1));
   }
   else
   {
      return s;
   }
}

Ablauf:

1. Erster Aufruf mit ReverseString mit "abc"
2. s ist länger als 0 (TRUE-Case)
3. Im TRUE-Case wird das letzte Zeichen von "abc" = 'c' genommen und es wird ReverseString("ab") angehängt

4. Zweiter Aufruf mit ReverseString mit "ab"
5. s ist länger als 0 (TRUE)
6. TRUE => Letztes Zeichen von "ab" = "b" und ReverseString vom Rest ("a") anhängen

7. Dritter Aufruf von ReverseString mit "a"
8. s ist länger als 0 (TRUE)
9. TRUE => Letztes Zeichen von "a" = "a" + ReverseString vom Rest ("")

10. Vierter Aufruf von ReverseString mit ""
11. s ist NICHT länger als 0, da "" leer ist => FALSE
12. FALSE
=> return ""

13. Wir springen zurück zu der Stelle wo ReverseString("") aufgerufen wurde - Position 9 -, dort wird dann "a" + das Ergebnis von ReverseString("") = "" zurückgegeben
=> return "a"

14. Wir springen erneut einen Aufruf zurück nach Position 6. Dort wird "b" und das Ergebnis von eben ("a") zurückgegeben
=> return "ba"

15. Wir springen erneut einen Aufruf zurück nach Position 3. Dort wird "c" und das Ergebnis von eben ("ba") zurückgegeben
=> return "cba"

16. Ende, der fertig gedrehte String lautet "cba".




Das Prinzip ist eigentlich recht banal, aber man muss es im Kopf am besten mal durchspielen.

Das erste, was nach dem Aufruf der Funktion passiert, ist der Check ob sie ein weiteres Mal aufgerufen kann. Die Frage ist also: Kann ich den aktuellen Input noch weiter aufdröseln oder kann ich direkt loslegen? Beim ReverseString ist es die Frage ob der String am Ende angelangt ist bzw. leergeräumt wurde. In deinem Fall wäre es die Prüfung ob du den verbliebenen Term noch weiter aufsplitten musst (Stichwort: Klammern und Punkt-vor-Strich).

Irgendwann wird die Frage mit "nein" beantwortet und ein weiterer Aufruf ist nicht sinnvoll, weil beispielsweise "" leer ist und leer bleiben wird, egal was wir damit tun. An dieser Stelle wird nun das erste Teilergebnis berechnet und eine Eben nach oben durchgereicht. Damit kann die Ebene darüber ihrerseits ihr Teilergebnis berechnen und abermals nach oben durchreichen. Das ribbelt sich Ebene für Ebene auf bis man auf der obersten Ebene angelangt ist und da wird erneut das Teilergebnis berechnet, das letztendlich das Endergebnis darstellt.

 

[DeepComputer]

Also für die Addition, zB x+y+z+a hab ich's schon mal hinbekommen. Aber ich hab noch immer nicht wirklich eine Ahnung was genau passiert. Es verwirrt mich, dass ich den Wert von
input = input.Replace(resultstring[1], Term(resultstring[1])); nicht sehen kann. Der compiler ersetz die Sachen zwar richtig, zeigt mir einen anderen string an. Irgendwie komisch...

private string Term(string input)
        {
            char[] scanterm = input.ToCharArray();

            while (!input.All(char.IsDigit))
            {
                for (int i = 0; i < scanterm.Length - 1; i++)
                {

                    if (scanterm[i] == '+')
                    {
                        resultstring = input.Split(scanterm[i], 2);
                        resultstring = resultstring[1].Split(scanterm[i], 2);
                        if (resultstring.Length <= 1 && resultstring[0].All(char.IsDigit))
                        {
                            resultstring = input.Split(scanterm[i], 2);
                            result = int.Parse(resultstring[0]) + int.Parse(resultstring[1]);
                            return input = input.Replace(resultstring[0] + '+' + resultstring[1], result.ToString());
ok, hier war der Fehler. Die Zeile ist redundant. return result.ToString(); tut's genauso und man sieht den input den result überschreibt.
                        }
                        resultstring = input.Split(scanterm[i], 2);
                        input = input.Replace(resultstring[1], Term(resultstring[1]));
                        scanterm = input.ToCharArray();
                    }
                }
            }
            return input;
        }