Leerzeichen zählen mit Rekursion

[ThommyTom]

Hallo!
Ich versuche grade die Rekursion zu verstehen und habe wollte mir deshalb mal ein Programm schreiben, dass Leerzeichen in einem String zählt. Natürlich mittels Rekursion.

Das bekomme ich aber einfach nicht hin, kann mir da jemand weiterhelfen?
Ich habe:

public int anzahlLeerzeichen(String s)
    {
        if(s.isEmpty())
        {
            return 0;
        }
        else 
        {
            int ergebnis = anzahlLeerzeichen(s.substring(1));
            if(s.substring(s.length() - 1).isEmpty())
            {
                return 1 + ergebnis;
            }
            else
            {
                return ergebnis;
            }
        }
    }

Ablaufen sollte es so:
anzahlLeerzeichen("a bc d")
-> 0 + anzahlLeerzeichen(" bc d")
-> 0 + (1 + anzahlLeerzeichen("bc d"))
-> 0 + (1 + (0 + anzahlLeerzeichen("c d")))
-> 0 + (1 + (0 + (0 + anzahlLeerzeichen(" d"))))
-> 0 + (1 + (0 + (0 + (1 + anzahlLeerzeichen("d")))))
-> 0 + (1 + (0 + (0 + (1 + (0 + anzahlLeerzeichen(""))))))
-> 0 + (1 + (0 + (0 + (1 + (0 + 0)))))
-> 0 + (1 + (0 + (0 + (1 + 0))))
-> 0 + (1 + (0 + (0 + 1)))
-> 0 + (1 + (0 + 1))
-> 0 + (1 + 1)
-> 0 + 2
-> 2

Ich danke euch!
LG
Thomas

 

[ThommyTom]

public int anzahlLeerzeichen(String s)
    {
         if(s.isEmpty())
         {
             return 0;
         }
         else 
         {
            if(s.substring(0,1).equals(" "))
            {
                return 1 + anzahlLeerzeichen(s.substring(1));
            }
            else
            {
                return anzahlLeerzeichen(s.substring(1));
            }
         }
    }

Das stimmt, oder?

 

[rme]

Ja, das wäre eine mögliche Lösung Schön wäre es, wenn du die Rekursion endrekursiv hinbekommst, d.h. dafür sorgst, dass die Funktion im letzten Schritt immer in die Rekursion geht und dahinter nichts mehr kommt. Bei dir gibt es einen Fall, in dem du nach der Rekursion noch eine Addition durchführst - das ist in der Theorie der Rekursion nicht sehr elegant.

 

[ThommyTom]

Von welchem Fall sprichst du?

 

[rme]

                return 1 + anzahlLeerzeichen(s.substring(1));

In diesem Fall muss die Rekursion abgewartet werden, bis die 1 addiert werden kann, d.h. es ist Speicher für die ganzen Zwischenwerte erforderlich. Das sieht man auch oben in deinem Rekursionsbaum ganz gut - wenn die letzte Stufe fertig ist, muss alles nochmal zurückgerechnet werden, bis das Ergebnis feststeht.

In Java ist sowas egal, weil es in Java keine Funktionen gibt und Java deshalb immer diesen Speicher benötigen wird. Aber in Sprachen, in denen es Funktionen gibt (Scala, Haskell, Erlang, OCaml, ML, ...), könntest du Zeit und Speicher sparen, wenn du das obige Problem beseitigst

 

[ThommyTom]

Achso okay
Ich sollte es aber schon so implementieren, wie in dem Baum angegeben.
Ich denke trotzdem noch einmal drüber nach.

Eine Kleinigkeit noch zu regulären Ausdrücken:
[a-z] heißt ja genau ein Buchstabe aus der Menge.
Wenn ich jetzt z.B.
Klasse und K
scchreiben möchte, wie mache ich das?
[A-Z][a-z] geht ja nicht, weil ich so das K nicht hinbekomme. [] heißt genau einmal.

 

[rme]

[abc] bedeutet ja, dass sowohl a, b und c erlaubt sind - Ein Trennzeichen ist nicht erforderlich. Deshalb sieht das merkwürdig aus, aber man macht es so: [A-Za-z]

 

[ThommyTom]

Und wenn ich ausschließen möchte, dass so ein Wort mit einem Kleinbuchstaben beginnt? Ich möchte die Menge aller großgeschriebenen Wörter haben.
[A-K][a-k]+ muss also irgendwie so ergänzt werden, dass [a-k] auch garnicht vorkommen kann. Oder heißt + genau das? Ich dachte aber, dass heißt mindestens einmal.

Und wie stellt man z.B. die Zahlen von 0 bis 255 dar? [0-255] wäre ja 0,1,2,5.

 

[rme]

+ heißt "mindestens einmal". Du brauchst den *, der steht für "beliebig oft, einschließlich 0 mal"

Das Zahlenbeispiel lass ich dich selbst rätseln, wir wollen hier ja keine Hausaufgaben machen Tipp: Vielleicht brauchst du da mehrere, durch ein Oder | kombinierte Fälle.

 

[ThommyTom]

Aber man kommt da mit [], +, * und | aus? Was genau macht das |? Erlaubt es auch, dass beides erfüllt ist oder ist es exklusiv?

Achja, und es sind keine Hausaufgaben

 

[rme]

Hier mal systematische Überlegungen dazu:

Erste Ziffer:
* wenn die Zahl dreistellig ist, darf die erste Ziffer nur 0, 1 oder 2 sein (falls führende Nullen erlaubt sein sollen)
* wenn die Zahl weniger als drei Ziffern hat, kann die erste Ziffer beliebig sein

Zweite Ziffer:
* wenn die Zahl dreistellig ist, darf die zweite Ziffer nur 0 - 5 sein

Dritte Ziffer:
* darf nur 0 - 5 sein

Der Gesamtaufbau ist also eine Fallunterscheidung, d.h. sieht so aus:

(ausdruck für einstellige Zahlen) | (ausdruck für zweistellige zahlen) | (ausdruck für dreistellige zahlen)

Das Oder erlaubt auch, dass beides erfüllt ist.

 

[ThommyTom]

Ich habe nun dies hier:
[0-9]|([0-9][0-9])|([0-2][0-5][0-5]|[0-2][0-4][0-9]|[01][0-9][0-9])

Das müsste eigentlich stimmen. Geht es auch einfacher? Ist ja doch recht lang.

Nun möchte ich aber noch (du ahnst es wohl schon) einen Ausdruck für IP-Adressen haben.
Das wäre dann
([0-9]|([0-9][0-9])|([0-2][0-5][0-5]|[0-2][0-4][0-9]|[01][0-9][0-9]))\.([0-9]|([0-9][0-9])|([0-2][0-5][0-5]|[0-2][0-4][0-9]|[01][0-9][0-9]))\.([0-9]|([0-9][0-9])|([0-2][0-5][0-5]|[0-2][0-4][0-9]|[01][0-9][0-9]))\.([0-9]|([0-9][0-9])|([0-2][0-5][0-5]|[0-2][0-4][0-9]|[01][0-9][0-9]))

Hab ich das unnötig kompliziert gemacht, oder geht es einfach nicht anders?

 

[rme]

Es ist normal, dass reguläre Ausdrücke lang und unleserlich werden. Für die Zahl 0 bis 255 fällt mir intuitiv kein kürzerer ein. Für die IP-Adresse könnte man das abkürzen: Es gibt den Operator {a, b}, den man hinter einen Ausdruck schreiben kann - er sorgt dafür, dass der Ausdruck mindestens a mal und höchstens b mal vorkommen darf, z.B.:

[a-z]{2, 4} - 2 bis 4 Kleinbuchstaben

[0-9]{10} - genau 10 Ziffern

Dabei kann der zu wiederholende Ausdruck auch ein komplexer Ausdruck sein, dann einfach runde Klammern darum setzen, damit klar ist, was wiederholt werden darf.

Hier steht, was es noch alles gibt: Pattern (Java Platform SE 6)

 

[VfL_Freak]

Moin,

habe gerade mal schnell in meiner SW hier geschaut ... ich prüfe so auf gültige IPs:

  /**
   * Überprüft einen übergebenen Text auf eine IP-Adresse (ohne führenden oder nachfolgenden Text) 
   * @param strIP4 Der Text
   * @return true -> IP-Adresse gefunden
   */
  public static boolean validateIP4OhneText(String strIP4){
    boolean bResult = false;
    if (strIP4 == null)
    {
      return bResult;
    }
   	Pattern p = Pattern.compile("^[0-9]{1,3}[.]{1}[0-9]{1,3}[.]{1}[0-9]{1,3}[.]{1}[0-9]{1,3}$");
   	Matcher m = p.matcher(strIP4);
   	if( !m.find( ))
   	{
   		bResult = false;
   	} 
   	else 
   	{
   		bResult = true;
   	}
    return bResult;
  }

Müsste doch das sein, was Du suchst, oder ?

Gruß
Klaus

 

[rme]

Das würde aber 999.999.999.999 als gültige IP-Adresse zulassen

 

[VfL_Freak]

ok, guter Einwand .... :autsch:

Habe es mir gerade mal angeschaut.
Das liegt hier bei mir daran, dass mit dieser Methode quasi nur geschaut werden soll, ob es eine IP ist oder nicht! Die Prüfung, ob die einzelnen Blöcke im Bereich 0-255 liegen, macht scheinbar nur das vorgelagerte Programm, dass mir ggf. auf Anfrage eine konkrete IP liefert ...

Sorry, war dann auf die Schnelle wohl doch nicht so hilfreich, wie ich dachte. Ich habe dieses Projekt erst vor einiger Zeit übernommen und mich noc nicht mit allen Teilbereichen so intensiv beschäftigt, wie es sein sollte ... wußte nur, dass es so eine Methode gab!

Gruß
Klaus

 

[nvidia]

Um noch mal etwas zum eigentlichen Thema zu posten, bei dem es nicht um reguläre Ausdrücke ging.

public final class ZaehleZeichenBeispielRekursiv {
	public static int zaehleLeerzeichen(String quelle){
		return zaehleZeichen(quelle,' ');
	}
	
	private static int zaehleZeichen(String quelle, char zeichen) {
		return loop(quelle, zeichen, quelle.length()-1, 0);
	}

	private static int loop(String quelle, char zeichen, int aktuellePosition, int anzahl) {
		if(aktuellePosition < 0){
			return anzahl;
		}
		
		if(quelle.charAt(aktuellePosition) == zeichen){
			anzahl++;
		}
		
		return loop(quelle, zeichen, aktuellePosition-1, anzahl);
	}

	public static void main(String[] args) {
		System.out.println(zaehleLeerzeichen(" a b "));
	}
}

 

[ThommyTom]

Ich danke euch allen! Hat mir alles sehr geholfen!