Pattern Matching ohne Match-Methoden

B

barodscheff

Gast
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:
blatt.jpg


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

Top Contributor
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.
 
B

barodscheff

Gast
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:

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

LG
 

njans

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

Java:
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

Java:
	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;
	}
 
B

barodscheff

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

Java:
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
 
Zuletzt bearbeitet von einem Moderator:

DrZoidberg

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

Java:
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

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

@barodscheff [WR]Deine Lösung funktioniert aber nicht richtig.[/WR]
Java:
match("A*B*C*D***E**", "ABCDE");
Gibt false aus.
 
Zuletzt bearbeitet:

njans

Top Contributor
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:
Java:
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;
    }
 
Zuletzt bearbeitet:
B

barodscheff

Gast
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

Top Contributor
Java:
 // 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).


Java:
   // 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.

Java:
        // 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.
 
Zuletzt bearbeitet:
B

barodscheff

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

LG
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
M Methoden Pattern Matching Vokal Java Basics - Anfänger-Themen 2
L Pattern Matching Java Basics - Anfänger-Themen 3
B static und Pattern matching Java Basics - Anfänger-Themen 22
M Pattern Matching Java Basics - Anfänger-Themen 2
M Pattern-Matching Java Basics - Anfänger-Themen 4
S pattern matching Java Basics - Anfänger-Themen 3
D was ist der vorteil vom Builder-design pattern? Java Basics - Anfänger-Themen 11
W GoF-Pattern im Programmierer-Alltag Java Basics - Anfänger-Themen 113
D Java Pattern mit X Ausgabe Stern Java Basics - Anfänger-Themen 4
J Methoden Observer-Pattern mit Consumer und accept( ) Java Basics - Anfänger-Themen 6
Dimax Erste Schritte Pattern.matcher,die Besonderheiten. Java Basics - Anfänger-Themen 12
N Best Practice Frage zum MVC-Pattern Java Basics - Anfänger-Themen 2
J Implementierung von Observer und Singleton-Pattern Java Basics - Anfänger-Themen 9
F Design pattern Java Basics - Anfänger-Themen 29
W RegEx Matcher + Pattern und Emails Java Basics - Anfänger-Themen 8
M Schlüsselworte Unterschied: String.matches und Pattern.compile Java Basics - Anfänger-Themen 2
C Best Practice JTable in MVC Pattern Java Basics - Anfänger-Themen 7
D Design Pattern Command Java Basics - Anfänger-Themen 3
Bregedur Methoden Matcher und Pattern bei sich wiederholenden Werten Java Basics - Anfänger-Themen 1
fLooojava MVC Pattern und Observer Pattern Java Basics - Anfänger-Themen 6
S Regex Pattern Java Basics - Anfänger-Themen 3
Z Pattern und Matcher substring zu String möglich? Java Basics - Anfänger-Themen 4
B Pattern für Email Liste Java Basics - Anfänger-Themen 3
J Builder Pattern implementieren Java Basics - Anfänger-Themen 3
Tarrew Proxy Design-Pattern Java Basics - Anfänger-Themen 1
agent47 Pattern split Java Basics - Anfänger-Themen 2
J MVC Pattern, mehrere Controller/Views/Models Java Basics - Anfänger-Themen 0
B Strategy Pattern - Rechner Java Basics - Anfänger-Themen 6
I Vertändnisfrage zu Prototype Pattern Java Basics - Anfänger-Themen 0
L Kompositum-Pattern Hilfe :O Java Basics - Anfänger-Themen 4
F eigenes Listener Pattern mit Interface Java Basics - Anfänger-Themen 1
S Je nach erhaltene Daten unterschiedlich reagieren (Design Pattern?) Java Basics - Anfänger-Themen 3
Furtano OOP Memento Pattern | übergabe einer Kopie des Arrays Java Basics - Anfänger-Themen 0
F Erste Schritte Pattern zum Zerlegen von selbstdefinierten Dateinamen Java Basics - Anfänger-Themen 7
M MVC + Strategy Pattern Ansatz (mit Code) Java Basics - Anfänger-Themen 5
A Design Pattern - Welche? Java Basics - Anfänger-Themen 33
Rudolf OOP Übungen zu Design Pattern in Java Java Basics - Anfänger-Themen 6
A Observer Pattern Problem Java Basics - Anfänger-Themen 15
J Interface Frage zu Interfces am Beispiel Observer Pattern Java Basics - Anfänger-Themen 8
S OOP Regex Pattern Java Basics - Anfänger-Themen 2
P Grundsatzfrage zu Decorator-Pattern Java Basics - Anfänger-Themen 6
L RegExp bzw Pattern in Java Java Basics - Anfänger-Themen 6
Helgon Observer Pattern - hasChanged() immer false Java Basics - Anfänger-Themen 10
R aktualisierung des View im MVC-Pattern Java Basics - Anfänger-Themen 5
M RegEx Pattern Matcher Java Basics - Anfänger-Themen 16
R Pattern bzw. Regex HTML-Code Java Basics - Anfänger-Themen 10
N Regexp Pattern & Matcher Problem Java Basics - Anfänger-Themen 4
I OOP Verständnisfrage zu Singelton Pattern Java Basics - Anfänger-Themen 21
R Welches Design pattern Java Basics - Anfänger-Themen 10
T pattern klappt nicht so Java Basics - Anfänger-Themen 6
T Decorator Pattern Java Basics - Anfänger-Themen 7
A Pattern und Matcher Java Basics - Anfänger-Themen 9
T Frage zu Pattern/Matcher Java Basics - Anfänger-Themen 6
D Pattern in Midi-Sequencer Java Basics - Anfänger-Themen 2
V Frage zu Decorator-Pattern Java Basics - Anfänger-Themen 4
S OOP Factory Pattern Java Basics - Anfänger-Themen 2
C OOP Observer Pattern Java Basics - Anfänger-Themen 2
M Regex-Pattern Java Basics - Anfänger-Themen 2
Haubitze_Broese Pattern für Links in RSS-Reader Java Basics - Anfänger-Themen 6
Raidri Pattern liefert false Java Basics - Anfänger-Themen 9
megachucky regex-Problem ( mit den Klassen Matcher / Pattern) --> XML prüfen Java Basics - Anfänger-Themen 11
O useDelimiter / Muster im Parameter (Pattern) Java Basics - Anfänger-Themen 6
S Problem mit Pattern Java Basics - Anfänger-Themen 2
S Pattern.matches mit Ignore Case Java Basics - Anfänger-Themen 2
N in int array einen pattern(eine zahl) finden Java Basics - Anfänger-Themen 21
A Hilfe zu Pattern Java Basics - Anfänger-Themen 2
Y Pattern Java Basics - Anfänger-Themen 2
A Proxy Pattern implementieren Java Basics - Anfänger-Themen 2
N OOP MVC Pattern Java Basics - Anfänger-Themen 3
G Probleme mit Pattern und Aussagenlogik Java Basics - Anfänger-Themen 6
H Verständnis Strategy Pattern Java Basics - Anfänger-Themen 4
D regexp-pattern .. letzter schliff Java Basics - Anfänger-Themen 6
A ist das ein Singleton-Pattern? Java Basics - Anfänger-Themen 6
Z regexp/pattern für dateipfad Java Basics - Anfänger-Themen 5
A Factory Pattern Java Basics - Anfänger-Themen 2
D Objekte anlegen und Singleton Pattern Java Basics - Anfänger-Themen 21
O Erklärung für Pattern Java Basics - Anfänger-Themen 5
U Java Pattern Regex Java Basics - Anfänger-Themen 9
0 Probleme mit Pattern und Matcher Java Basics - Anfänger-Themen 5
K Observer Pattern notifyObservers Java Basics - Anfänger-Themen 9
S geeignetes Such Pattern Java Basics - Anfänger-Themen 6
J Zugriff mit Visitor Pattern auf eigen erstellte verk. Liste Java Basics - Anfänger-Themen 3
J Visitor Pattern Java Basics - Anfänger-Themen 4
W Observer-Pattern Java Basics - Anfänger-Themen 3
M Singleton Pattern Java Basics - Anfänger-Themen 35
J Singleton Pattern Java Basics - Anfänger-Themen 5
J Ant pattern Erklaerung Java Basics - Anfänger-Themen 4
G Aufbau MVC-Pattern Java Basics - Anfänger-Themen 6
S Singleton Pattern passend hierfür? Java Basics - Anfänger-Themen 60
M Factory Pattern Ansatz falsch? Java Basics - Anfänger-Themen 6
Y Hilfe bei Pattern-Regexp Java Basics - Anfänger-Themen 5
U pattern Java Basics - Anfänger-Themen 2
A Pattern.matches(); Java Basics - Anfänger-Themen 14
A Problem mit Obser-Pattern Java Basics - Anfänger-Themen 2
P pattern/match Java Basics - Anfänger-Themen 2
K Probleme mit RegEx (Pattern und Matcher) Java Basics - Anfänger-Themen 2
K Regex Pattern Java Basics - Anfänger-Themen 4
G Vorteile Reflection bezüglich MVC-Pattern Java Basics - Anfänger-Themen 9
F regex pattern problem Java Basics - Anfänger-Themen 4
S Regex Pattern Problem Java Basics - Anfänger-Themen 2

Ähnliche Java Themen


Oben