Pattern Matching ohne Match-Methoden

[barodscheff]

Hallo liebes Forum,

ich bin neu hier, da ich nun langsam bei meinem Wissen an die Grenzen komme.
Ich studiere Wirtschaftsinformatik und habe mir mein Java-Wissen hauptsächlich durch Bücher selbst angeeignet.

Aktuell arbeite ich an einer Hausaufgabe, bei der es darum geht PatternMatching anzuwenden ohne Match-Methoden wie "matches" zu verwenden. Als Lösungshinweis ist angegeben, dass das rekursiv gelöst werden kann.

Der Vergleich soll zwischen 2 Strings(p und s) stattfinden, die nur Zahlen von 0 bis 9 enthalten dürfen. String p darf zudem einen Joker (*) verwenden.

Hier mal die komplette Aufgabe:

Mir fehlt jetzt irgendwie ein Ansatz. Das einzige was mir einfällt wäre es durch etliche if-Abfragen bestimmte Fälle auszuschließen. Z.B. wenn String p ohne den Joker länger ist als String s, dann return false... Aber das scheint mir doch etwas zu kompliziert.

Habt ihr einen sinnvolleren Ansatz? Die Ausnahmebehandlung kann erstmal außen vor gelassen werden.

Viele Grüße

 

[njans]

na du gehst deinen String s durch und schaust, ob s gleich p ist. Wenn du auf deinen Joker triffst, musst du evtl 2 wege gehen (sofern möglich):
Betrachte den Joker als korrektes symbol, dann musst du sowohl in s als auch in p auf das nächste Zeichen springen. Ansonsten kann der Joker auch ein leeres Symbol sein, also musst du so weiter machen, als ob dieser Joker nicht in P vorkäme.

 

[barodscheff]

Danke für die schnelle Antwort.

Die Idee hatte ich ja auch schon nur eben dieser Joker ist mein Problem. Wie soll ich denn z.B. prüfen ob 2*3**3, mit 233 übereinstimmt. Ich weiß nicht wie ich das formulieren soll.

Mein Anfang sieht jetzt so aus:

if(p.equals(s)) { 
    return true;
} else if() {
	    
}

LG

 

[njans]

Ich würde es rekursive lösen, das erscheint mir einfacher.

boolean match(String s, String p, int indexS, int indexP)

Wäre der Kopf der Methode, die du bräuchtest. Der Gedanke ist der: Wenn du beide Strings vergleichen willst, musst du immer wissen, an welcher Stelle du bei beiden Sequenzen bist. Dies können indexS und indexP darstellen. Dann musst du immer prüfen ob die beiden Buchstaben an der jetzigen Stelle:
- Ungleich sind
- Gleich sind
- der Buchstabe in P dein Joker ist


Je nachdem kannst du dann entweder abbrechen (false zurückgeben), einfach beide indices um eins erhöhen oder eine Fallunterscheidung machen:
- * das korrespondierende Zeichen in s, dann musst du wieder beide Indices erhöhen
- * ist das leere Symbol, dann musst du nur den Index von p erhöhen.

Natürlich fehlen dann noch Abbruchbedingungen, so dass du nicht außerhalb der Strings zugreifst.
Ich habe das mal eben, ohne Gewähr, geschrieben. Wenn du nicht weiter kommst, kannst du dort mal reinschauen

Spoiler

	public boolean isValid(String s, String p)
	{
		return match(s, p, 0, 0);
	}
	
	private boolean match(String s, String p, int indexS, int indexP)
	{
		// Abbruchbedingungen
		if (indexP >= p.length())
			return true;
		
		if (indexS >= s.length())
			return false;
		
		// Lokale Variablen der Übersicht halber
		char wChar = s.charAt(indexS);
		char pChar = p.charAt(indexP);
		
		// Rekursionsschritt
		if (pChar == '*')
			return 	match(s, p, indexS, indexP+1) || 
					match(s, p, indexS+1, indexP+1);
		
		if (wChar == pChar)
			return match(s, p, indexS+1, indexP+1);
		
		return false;
	}

 

[barodscheff]

Vielen Dank für die Mühe, es hat mir weitergeholfen.
Das hier ist jetzt entstanden und funktioniert soweit:

public class Match {   
    // Vorgegebene Methode
    public static boolean match(String p, String s) {
	
	if(p.equals(s)) {
	    // "Einfache" Gleichheit gegeben
	    return true;
	} else if(p.isEmpty()) {
	    // Wenn p leer ist, muss auch s leer sein
	    if(s.isEmpty()) {
		return true;
	    } else {
		return false;
	    }
	} else {
	    
	    // "Einfache" Gleichheit nicht gegeben
	    // Initialisierung von i und j und boolsche Hilfsvariable matching
	    int i = 0;
	    int j = 0;
	    boolean matching = false;
	    boolean jokerCheck = false;

	    // While-Schleife zum Vergleich der chars
	    while(i < p.length()) {
		
		// Vergleich der einzelnen chars an den jew. Positionen
		if(p.charAt(i) == s.charAt(j)) {
		    
		    // i wird nicht erhöht wenn Ende von i erreicht ist, von j aber nicht
		    if(i == p.length() - 1 && j < s.length() - 1) {
			matching = false;
			i++;
		    } else {
			matching = true;
			i++;
		    }
			
		    // j wird nicht erhöht wenn die maximale Länge erreicht ist
		    if(j < s.length() - 1) {
			j++; 
		    }
		    
		} else {
		    
		    // Überprüfung ob alle chars in p Joker sind
		    for(int k = 0; k < p.length(); k++) {
			if(p.charAt(k) == '*') {
			    jokerCheck = true;
            		} else {
            		    jokerCheck = false;
            		    break;
            		}
		    }
			
		    // Wenn alle chars in p Joker sind true zurückgeben
		    if(jokerCheck == true) {
			matching = true;
			break;
		    } // Überprüfung ob es sich bei p an der Stelle i um einen Joker handelt
		    else if(p.charAt(i) == '*') {
			i++;
			// j wird nicht erhöht wenn die maximale Länge erreicht ist und wenn die Zahlenkombination nach dem Joker = s ist (*1234 & 1234)
			if(j < s.length() - 1 && !p.substring(i, p.length()).equals(s)) {
			    j++; 
			}
			// Überprüfung ob es sich bei p - 1 um einen Joker handelt UND ob akt. index von i nicht 0 ist UND j nicht letztes char in s ist
		    } else if(i != 0 && p.charAt(i - 1) == '*' && j != s.length() - 1) {
			j++;    
		    } else {
			matching = false;
			break;
		    }
		}
		
	    } // Ende while
	    
	    // Ausgabe
	    return matching;
	    
	}
    } // Ende Methode match
   
    // main-Methode
    public static void main(String[] args) {
	// System.out.println(match(args[0], args[1]));
	System.out.println(match("*", " "));
    }

}

Jetzt fehlt mir nur noch die Überprüfung ob unzulässige Zeichen verwendet wurden.
Ich ging davon aus, dass sei einfach, habe mich aber getäuscht.

Ist try-catch hier der richtige Ansatz? Wie könnte ich das am besten implementieren.

LG

 

[DrZoidberg]

Rekursiv lässt sich das aber deutlich kürzer lösen.

public static boolean match(String p, String s) {
    if(p.length() == 0) return s.length() == 0;
    if(p.charAt(0) == '*') {
        if(s.length() == 0) return match(p.substring(1), s);
        return match(p, s.substring(1)) || match(p.substring(1), s);
    }
    if(s.length() == 0) return false;
    return s.charAt(0) == p.charAt(0) &&
           match(p.substring(1), s.substring(1));
}

 

[njans]

@DrZoidberg, siehe meinen spoiler-Post, da hatte ich bereits eine Lösung geschrieben.

@barodscheff [WR]Deine Lösung funktioniert aber nicht richtig.[/WR]

match("A*B*C*D***E**", "ABCDE");

Gibt false aus.

 

[DrZoidberg]

@barodscheff [WR]Deine Lösung funktioniert aber nicht richtig.[/WR]

match("A*B*C*D***E**", "ABCDE");

Gibt false aus.

Dann ist deine Lösung aber auch nicht richtig
isValid("ABCDE", "A*B*C*D***E**", 0, 0) gibt false.

 

[njans]

hmm das ist wahr, ich sehe auch wo das Problem ist. Allerdings war meine Idee auch nur aus dem Kopf geschrieben, daher hatte ich eh damit gerechnet, dass da noch Fehler sind.

Das Problem bei mir ist, dass die letzten zwei Joker da nicht berücksichtigt werden.

Hier mal ein Fix:

Spoiler

public boolean isValid(String s, String p)
    {
        return match(s, p, 0, 0);
    }
   
    private boolean match(String s, String p, int indexS, int indexP)
    {
        // Abbruchbedingungen
        if (indexP == p.length())
            return (indexS == s.length());
       
        if (indexS == s.length())
            return isJoker(p, indexP);
       
        // Lokale Variablen der Übersicht halber
        char wChar = s.charAt(indexS);
        char pChar = p.charAt(indexP);
        
        // Rekursionsschritt
        if (pChar == '*')
            return  match(s, p, indexS, indexP+1) ||
                    match(s, p, indexS+1, indexP+1);
       
        if (wChar == pChar)
            return match(s, p, indexS+1, indexP+1);
        
        return false;
    }
    
    private boolean isJoker(String p, int startIndex)
    {
    	for (int i = startIndex; i < p.length(); i++)
			if (p.charAt(i) != '*')
				return false;
			
    	return true;
    }

 

[barodscheff]

Ja den Fehler habe ich auch schon bemerkt.

Die rekursive Lösung will einfach nicht in meinen Kopf, verstehe das nicht so ganz.
Kannst du mir vielleicht erklären was genau beim Rekursionsschritt passiert?

LG

 

[njans]

 // Abbruchbedingungen
        if (indexP == p.length())
            return (indexS == s.length());
       
        if (indexS == s.length())
            return isJoker(p, indexP);

Wenn du mit einem der Indices am Ende des jweiligen Strings bist (index == length) dann ist dein Prozess beendet. wenn du dann verststellst, dass das Pattern zuende ist, dann musst du nur gucken ob s auch am zuende ist.
Wenn dein Srting zuende ist, dann musst du nur gucken, ob der Rest des Patterns Joker sind (die können auch das leere Symbol sein).

   // Lokale Variablen der Übersicht halber
        char wChar = s.charAt(indexS);
        char pChar = p.charAt(indexP);

Einfach zur leserlichen Darstellung, geht auch ohne, dann muss man aber immer .charAt() verwenden.

        // Rekursionsschritt
        if (pChar == '*')
            return  match(s, p, indexS, indexP+1) ||
                    match(s, p, indexS+1, indexP+1);
       
        if (wChar == pChar)
            return match(s, p, indexS+1, indexP+1);
       
        return false;

Wenn du gerade im pattern auf ein * triffst, dann kann es zwei verschiedene Lösungen geben:
- Das * ersetzt den Buchstaben an der entsprechenden Stelle in s: indexS+1, indexP+1
- * ist das leere Symbol, kann also ignoriert werden: indexS, indexP+1

Da ich die Strings s und p nicht verändere (ich lese nur) kann ich bei der Rekursion einfach einen neuen Schritt gehen [*].
Ich ver-ODER (wenn eines der beiden Ergebnisse true zurückliefert, dann ist das Ergebnis auch true). Wenn eines der Ergebnisse true ist, dann ist das eine valide Lösung (also es gibt eine Möglichkeit, dass das Pattern matcht).
Wenn wChar == pChar, dann ist das jetzige Zeichen übereinstimmend mit dem Pattern.
Der einzige Fall, der jetzt noch eintreten kann, ist, dass wChar != pChar, dann stimmen Pattern und String nicht überein! Es kann also abgebrochen werden.


[*] Bei Rekursion erzeugt jeder Schritt einen neuen "Pfad", äquivalent zu deinem Baum (Informatik), welcher Ast für Ast abgelaufen wird. Das Programm ruft dann immer wieder die methode match() auf, bis du auf eine Abbruchbedingung triffst und gibt dann das Ergebnis daraus zurück.


Verfolge (Zeichne) mal, was passiert wenn man ein Pattern der Länge 2 und einen String der Länge 2 hat. Wenn das nicht hilft, einfach hier nochmal fragen.

 

[barodscheff]

Erneut danke.
Ich kann es mehr oder weniger nachvollziehen, nur alleine würde ich da nicht drauf kommen.

LG