Rekursion Ablauflogik

[RedNose84]

Hallo zusammen,

ersteinmal zu mir: Ich bin rel. Neu in Java aber da ich von C# umsteige habe ich eig. Keine großen Probleme bisher gehabt. Dennoch habe ich ein Verständnisproblem in der Ablauflogik.

Folgende beiden Funktionen:

    public void btnGleich_Click() {
        String gleichung = tbGleichung.getText();
        String[] arrGleichung = HelperClass.teileAuf(gleichung);
        int anzahl = HelperClass.findeMalZeichenAnzahl(arrGleichung);
        String[] neu = Berechne(arrGleichung,anzahl);        
    }
    
    public String[] Berechne(String[] term, int malZeichenAnzahl)
    {
        String[] newTerm = new String[term.length];
        if (malZeichenAnzahl > 0 )
        {
            int i = 0;
            while (!term[i+1].equals("*")) {
                newTerm[i] = term[i];
                i++;
            }
            newTerm[i] = HelperClass.Multipliziere(term[i], term[i+2]);
            for (int z = i+1; z<term.length-2; z++)
            {
                newTerm[z] = term[z+2];
            }
            malZeichenAnzahl--;
            Berechne(newTerm, malZeichenAnzahl);
            int t = 0;
        }
        return term;
    }

Mein Ziel ist es ein „Taschenrechner“ zu Programmieren. Man kann über eine GUI eine Gleichung eingeben und mein Algorithmus rechnet dann entsprechend die komplette Gleichung aus. Dazu habe ich einen rekursiven Algorithmus entwickelt, der soweit auch funktionstüchtig ist. Nach dem die Abbruchbedingung erreicht ist

if (malZeichenAnzahl >0

springt er auch ganz ordentlich zum „return term;“ Allerdings ruft er im debug Modus mit Einzelschrittanweisung nach und nach wieder die Funktion

Berechne(newTerm, malZeichenAnzahl);

auf. Bis der Term wieder in der Ausgangssituation ist. Erst dann wird dieser an die Usprünglich aufgerufende Variable vergeben

String[] neu = Berechne(arrGleichung,anzahl);

Wie kann das denn sein? Ich verstehe das nicht L

Die Algorithmen sind erst in der Entwicklung. Beschränkung auf mal Zeichen etc. Muss noch alles aufgebaut werden.

Kann mir irgendwer ein Tipp geben? Sehe den Wald vor lauter Bäumen mal wieder nicht L


Danke schon mal an alle hier im Forum die mir Helfen. Bin für jeden Tipp dankbar

 

[max40]

1. verstehe ich noch nicht so ganz warum du term übergibst und term unverändert zurückgibst!

2. ich glaube du brauchst da keine Rekursion, du musst doch eigentlich das term nur in einer schleife durchgehen!

also entweder habe ich es nicht verstanden oder du müsstest noch mal deine Logik überdenken.

 

[Marco13]

Allerdings ruft er im debug Modus mit Einzelschrittanweisung nach und nach wieder die Funktion
Berechne(newTerm, malZeichenAnzahl);
auf.

Kann es sein, dass da ein mißverständnis vorliegt?! Er ruft diese Funktion nicht auf, er HAT sie aufgerufen.... Wenn der Ablauf sowas ist wie

berechne(x, 2);
{
    berechne(x, 1);
    {
        berechne(x,0); RETURN
        XXX   
    }
}

dann sieht es im Debugger-Stack bei der Zeile "XXX" evtl. kurz so aus, als würde er in die Berechne-Funktion hineinhüpfen - er hüpft aber nicht hinein, sondern ist nur "auf dem Weg zurück" von der Tiefsten in die nächst-weniger-tiefe Rekursionsstufe.

In der Variablen-Ansicht solltest du bei diesen Schein-Aufrufen mitverfolgen können, wie malZeichenAnzahl jedes mal höher wird, während er sich die ganzen Stufen hochhangelt.

Ein "return" in der innersten Rekursionsstufe bewirkt NICHT (und KANN auch nicht bewirken) dass er sofort wieder an die höchste Stufe hüpft....

 

[RedNose84]

1. verstehe ich noch nicht so ganz warum du term übergibst und term unverändert zurückgibst!

2. ich glaube du brauchst da keine Rekursion, du musst doch eigentlich das term nur in einer schleife durchgehen!

also entweder habe ich es nicht verstanden oder du müsstest noch mal deine Logik überdenken.

Hallo und danke erstmal....

Meine LKogik so müsste schon stimmen. Ich habe keinen einfachen Schleifendurchlauf, weil es ja gewisse mathematischen Regel zu beachten gilt. Punkt vor Strich zB. Also muss ich meinen Term erst nach * durchforsten (später auch nach /) Bis alle weg sind. Erst dann kann ich alles hintereinander weg verrechnen)

Beispiel: 1+2*3*4*5 kann nicht hintereinander weg verrechnet werden

zu deiner ersten Anmerkung: Der Term wird NICHT unverändert übergeben. Denn:

Berechne(newTerm, malZeichenAnzahl);

Hier wird solange wie ein * Zeichen vorhanden ist die Funktion ja wieder selber aufgerufen. Mit einem veränderten term. Ist kein * zecihen mehr vorhanden so gibt er den aktuell übergebenen Term einfach weider zurück!

Jetzt evtl. Verständlicher?

Gruß

 

[RedNose84]

Allerdings ruft er im debug Modus mit Einzelschrittanweisung nach und nach wieder die Funktion
Berechne(newTerm, malZeichenAnzahl);
auf.

Kann es sein, dass da ein mißverständnis vorliegt?! Er ruft diese Funktion nicht auf, er HAT sie aufgerufen.... Wenn der Ablauf sowas ist wie

berechne(x, 2);
{
    berechne(x, 1);
    {
        berechne(x,0); RETURN
        XXX   
    }
}

dann sieht es im Debugger-Stack bei der Zeile "XXX" evtl. kurz so aus, als würde er in die Berechne-Funktion hineinhüpfen - er hüpft aber nicht hinein, sondern ist nur "auf dem Weg zurück" von der Tiefsten in die nächst-weniger-tiefe Rekursionsstufe.

In der Variablen-Ansicht solltest du bei diesen Schein-Aufrufen mitverfolgen können, wie malZeichenAnzahl jedes mal höher wird, während er sich die ganzen Stufen hochhangelt.

Ein "return" in der innersten Rekursionsstufe bewirkt NICHT (und KANN auch nicht bewirken) dass er sofort wieder an die höchste Stufe hüpft....

Ja das scheint so... aber er "rechnet" dann auch alles wieder zurück?!?! Also übergeben wird dann einfach wieder der ursprungsterm :-( Was versteh ich denn da nicht?

 

[max40]

also wenn du klammern auflöst z.B. Klammer auf rufe Methode nochmal auf, Klammer zu gehe aus Methode raus, etc. da würde ich eine Rekursion verstehen. Aber bei Mal, Geteilt, plus und Minus ist doch (so denke ich) 4 mal hintereinander aufrufen mit jeweils unterschiedlichen Operator.

 

[RedNose84]

Wenn ich 1+2*3*4 rechnen will dann würde er laut deiner Logik (wenn ich dich richtig verstehe) fiolgendes rechnen 1+2 und dann das ergebnis * 3 etc.

Das ist ja nicht richtig

 

[max40]

Wenn ich 1+2*3*4 rechnen will dann würde er laut deiner Logik (wenn ich dich richtig verstehe) fiolgendes rechnen 1+2 und dann das ergebnis * 3 etc.

Das ist ja nicht richtig

Nein, ich würde auch erst alles mit '*' durchgehen und dann mit '/' usw.!

 

[maki]

Versuche es doch mal als baum:
1 + (2*3*4)

    (+)
    / \
 (1)  (2)
         \
         (*)
           \
            (*)
            / \
          (3) (4)

 

[0x7F800000]

@maki: * und 2 vertauscht? ???:L

@OP: pack da noch ein stack mit rein, der die klammern zählt. Damit kannst du dann die Operatoren raussuchen, die am weitesten oben im baum anzuorden sind, von den wählst du dann noch diejenigen mit der höchsten priorität aus, und schon kriegst du im prinzip einen parse baum... Das ist lahm & hässlich, aber dafür erfordert es 0 parserbau-kenntnisse Funktioniert ganz gut. Aber mit einer methode ist das definitiv nicht getan, da sollte eher für jede Produktionsregel eine hin... Als ich das gebastelt habe, waren das etwa 10-15... :noe:

 

[RedNose84]

Nein, ich würde auch erst alles mit '*' durchgehen und dann mit '/' usw.!

Das verstehe ich dann nicht. Wie soll das gehen? Wie willst du das neue Ergebnis dann zwischenspeichern? Das es mit dem nöchsten wieder verrechnet werden kann?

Mal davon abgesehen soll dann auch Klammern etc Berücksichtigt werden....

 

[RedNose84]

Versuche es doch mal als baum:
1 + (2*3*4)

    (+)
    / \
 (1)  (2)
         \
         (*)
           \
            (*)
            / \
          (3) (4)

Jetzt bin ich völlig raus.. ??? Was heißt das nun?

 

[RedNose84]

@maki: * und 2 vertauscht? ???:L

@OP: pack da noch ein stack mit rein, der die klammern zählt. Damit kannst du dann die Operatoren raussuchen, die am weitesten oben im baum anzuorden sind, von den wählst du dann noch diejenigen mit der höchsten priorität aus, und schon kriegst du im prinzip einen parse baum... Das ist lahm & hässlich, aber dafür erfordert es 0 parserbau-kenntnisse Funktioniert ganz gut. Aber mit einer methode ist das definitiv nicht getan, da sollte eher für jede Produktionsregel eine hin... Als ich das gebastelt habe, waren das etwa 10-15... :noe:

Sorry hab ich auch nicht verstanden... :-(

 

[maki]

>> * und 2 vertauscht?

Ja *peinlich*

 

[0x7F800000]

Sorry hab ich auch nicht verstanden... :-(

Ähm, welchen Teil genau?

Das mit dem stack meine ich konkret so:

term : 1+(2+3)/7+8*(3-9*(3*7))
stack: 00111100000011111222210
ops  :  +     / + *

wobei die zahlen in der zeile "stack" die anzahl der Klammer im Stack angibt [bei nur einer Klammerart ist ein Stack eigentlich unnötig, man kann auch nur die anzahl der geöffneten Klammer abspeichern]

In der Zeile "ops" sind dann alle Operatoren zu sehen, die auf der obersten ebene zu sehen sind, bei den also "0" dransteht. Im nächsten schritt brauchst du alle anderen operatoren nicht zu betrachten, weil sie tiefer in verschachtelten klammern liegen.

Von den Sichtbaren Operatoren hat + die höchste Priorität, du nimmst einfach den ersten verfügbaren, und trennst es am ersten Plus auf, und fährst so rekursiv fort...

Am ende erhälst du dann den Parse-Baum:

 

[RedNose84]

Ähm, welchen Teil genau?

Das mit dem stack meine ich konkret so:

term : 1+(2+3)/7+8*(3-9*(3*7))
stack: 00111100000011111222210
ops  :  +     / + *

wobei die zahlen in der zeile "stack" die anzahl der Klammer im Stack angibt [bei nur einer Klammerart ist ein Stack eigentlich unnötig, man kann auch nur die anzahl der geöffneten Klammer abspeichern]

In der Zeile "ops" sind dann alle Operatoren zu sehen, die auf der obersten ebene zu sehen sind, bei den also "0" dransteht. Im nächsten schritt brauchst du alle anderen operatoren nicht zu betrachten, weil sie tiefer in verschachtelten klammern liegen.

Von den Sichtbaren Operatoren hat + die höchste Priorität, du nimmst einfach den ersten verfügbaren, und trennst es am ersten Plus auf, und fährst so rekursiv fort...

Am ende erhälst du dann den Parse-Baum:

Ok danke erstmal.. muss mich wohl in die Thematik Stack Parser etc. einarbeiten erstmal. Gibt es interessante Literatur dazu? Hat jemand Tipps? Ansonsten bemühe ich google.


Danke :-(

 

[faetzminator]

ohne den Code genauer anzuschauen, gehe ich davon aus dass du nur aus

            ...
            malZeichenAnzahl--;
            Berechne(newTerm, malZeichenAnzahl);
            int t = 0;
            ...

einfach nur

            ...
            malZeichenAnzahl--;
            newTerm = Berechne(newTerm, malZeichenAnzahl);
            int t = 0;
            ...

machen musst.

 

[Landei]

Shunting Yard Algorithmus

 

[RedNose84]

ohne den Code genauer anzuschauen, gehe ich davon aus dass du nur aus

            ...
            malZeichenAnzahl--;
            Berechne(newTerm, malZeichenAnzahl);
            int t = 0;
            ...

einfach nur

            ...
            malZeichenAnzahl--;
            newTerm = Berechne(newTerm, malZeichenAnzahl);
            int t = 0;
            ...

machen musst.

ahhh verdammt nochmal da ist auf jeden fall nen fehler.. danke erstmal.....

 

[RedNose84]

Shunting Yard Algorithmus

Danke werde mir das mal weiter ansehen... klingt interessant.... Hab ich mir ja ne tolle Java Einsteigeraufgabe ausgesucht was ;-)