# Rekursion Ablauflogik



## RedNose84 (2. Apr 2009)

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 (2. Apr 2009)

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 (2. Apr 2009)

_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 (2. Apr 2009)

max40 hat gesagt.:


> 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 (2. Apr 2009)

Marco13 hat gesagt.:


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





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 (2. Apr 2009)

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 (2. Apr 2009)

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 (2. Apr 2009)

RedNose84 hat gesagt.:


> 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 (2. Apr 2009)

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

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


----------



## 0x7F800000 (2. Apr 2009)

@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 (2. Apr 2009)

max40 hat gesagt.:


> 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 (2. Apr 2009)

maki hat gesagt.:


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



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


----------



## RedNose84 (2. Apr 2009)

0x7F800000 hat gesagt.:


> @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 (2. Apr 2009)

>> * und 2 vertauscht? 

Ja *peinlich*


----------



## 0x7F800000 (2. Apr 2009)

RedNose84 hat gesagt.:


> 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 (2. Apr 2009)

0x7F800000 hat gesagt.:


> Ähm, welchen Teil genau?
> 
> Das mit dem stack meine ich konkret so:
> 
> ...




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 (2. Apr 2009)

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 (2. Apr 2009)

Shunting Yard Algorithmus


----------



## RedNose84 (2. Apr 2009)

faetzminator hat gesagt.:


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




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


----------



## RedNose84 (2. Apr 2009)

Landei hat gesagt.:


> Shunting Yard Algorithmus



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


----------

