www.jammni.de

Gepostet:
27.11.2005 19:33

Pattern Matching

Hi,

ich hab eine Aufgabe um einfaches Pattern Matching im Haskell zu implementieren. * und ? sind Sonderzeichen, die einen Buchstaben bzw. eine Reihe der Zeichen ersetzen koennen (auch keine Zeichen).
Das mit dem Fragezeichen hab ich so geloest, sodass ich in dem entsprechendem Text, der ich mit dem Muster vergleiche, entsprechenden Buchstaben mit den ? ersetze. Das funktioniert schon, aber * ist ein wenig schwieriger zu implementieren.

Ein solcher Fall z.B. Muster= "ab*d*xy" , Text= "abcmusadkkyxy";

Kann mir jmd ein Tipp geben?

Zum Seitenanfang

Jacke

Gepostet:
27.11.2005 20:14

Du musst erstmal sagen, was du genau machen sollst. Sollst du nur zurückgeben, ob das Suchmuster (ab*d*xy) im Suchtext (abcmusadkkyxy) vorhanden ist? Also einen true/false-Wert zurückgeben?
Oder sollst du das Suchmuster finden und das komplette Suchmuster durch einen anderen String ersetzen?
Und als zweites, soll das Suchmuster nur enthalten sein -sprich Muster "ab", Text = "cabc" wird gefunden, oder muss das Suchmuster auf den ganzen Text anspringen - also Muster = "*ab*", Text = "cabc"?

Und dann noch was zum Verständnis:
? heißt genau ein Zeichen
* heißt beliebig viele Zeichen, auch keine Zeichen

Wenn ich da was falsch verstanden habe, dann musst du das mal noch korrigieren...

Zum Seitenanfang

dejan

Gepostet:
27.11.2005 20:32

Hi,

man sollte den Text ausgeben, wenn der Muster mit im Text vorkommt. D.h. im Falle Muster= "ab*d*xy" , Text= "abcmusadkkyxy" sollte der Text ausgegeben werden.

Jacke wrote:
"Und als zweites, soll das Suchmuster nur enthalten sein -sprich Muster "ab", Text = "cabc" wird gefunden, oder muss das Suchmuster auf den ganzen Text anspringen - also Muster = "*ab*", Text = "cabc"?"

Das ist eine gute Frage. Ich hab schon einen Algorithmus, der ohne ? und * super funktioniert. Im Falle Muster="ab" und "cabc" liefert er den Text aus. Das ist leider nicht so eindeutig in der Angabe.

Ich meine, das ist mir zur Zeit nicht so wichtig; das kann ich spaeter anedern; da problemm ist, dass ich irgendwie nicht eine Loesung mit den * (obiges Bsp) finden kann. Hab schon eine Idee, aber ist ziemlich kompliziert.
Hast irgendwelche Vorschlaege?

Danke fuer Meldung :)
lG

Zum Seitenanfang

Jacke

Gepostet:
27.11.2005 22:32


suche ([m],[],acc) = []
suche ([],t,acc) = acc
suche ((m:m1:m2),(t:t1:t2),acc)
				|(m/=t) = suche ((m:m1:m2),(t1:t2),acc)
				|(m=='?') = suche ((m1:m2),(t1:t2),acc)
				|((m=='*') && (m1/=t1))= suche((m:m1:m2),(t1:t2),acc) 
				|((m=='*') && (m1==t1))= suche (m2,t2,(acc++[m1]))
				|otherwise = suche ((m1:m2),(t1:t2),(acc++[m]))



--m==t = suche m1:m2 t1:t2 acc++m

muster= "ab*d*xy" 

text= "abcmusadkkyxy"

so hier erstmal eine vorvorläufige version...schmeißt aber nen fehler beim ausführen...ich denke ich werd es dann morgen fertig proggen
krieg ich aber sicher noch hin...vllt hilft dir aber die idee schon weiter

gruß jacke

Zum Seitenanfang

Jacke

Gepostet:
27.11.2005 22:45

Hier mal eine etwas eine richtigere Lösung, aber immernoch nicht ganz fertig ;-)

suche ([m],[],acc) = []
suche (m,[t],acc) = acc++m
suche ([],t,acc) = acc
suche ((m:m1:m2),(t:t1:t2),acc)
				|(m/=t) = suche ((m:m1:m2),(t1:t2),acc)
				|(m=='?') = suche ((m1:m2),(t1:t2),acc)
				|((m=='*') && (m1/=t1))= suche((m:m1:m2),(t1:t2),acc) 
				|((m=='*') && (m1==t1))= suche (m2,t2,(acc++[m1]))
				|otherwise = suche ((m1:m2),(t1:t2),(acc++[m]))



muster= "ab*d*xy" 

text= "abcmusadkkyxy"

Zum Seitenanfang

Jacke

Gepostet:
27.11.2005 23:25

soooo jetzt aber : da ist sie die lösung :


suche ([],[],acc)= acc
suche ([m],[],acc) = []
suche (m:[],t:t1,acc)
		  	|(m==t) = acc++[m]
		  	|otherwise = suche((m:[]),t1,acc)

suche ([],t,acc) = acc
suche ((m:m1:m2),(t:t1:t2),acc)
				|((m/=t) && (m/='*')) = suche ((m:m1:m2),(t1:t2),acc)
				|(m=='?') = suche ((m1:m2),(t1:t2),acc)
				|((m=='*') && (m1/=t1))= suche((m:m1:m2),(t1:t2),acc++[t]) 
				|((m=='*') && (m1==t1))= suche (m2,t2,(acc++[m1]))
				|otherwise = suche ((m1:m2),(t1:t2),(acc++[m]))



muster= "ab*d*xy" 
muster2="*xy"
text= "abcmusadkkyxy"

und so ruft mans auf :-)


Main> suche(muster,text,[])
"abcmusdkkxy"

naja hat noch ein paar macken ^^ bei ** streikt er auch aber ich denke damit kommst du schon weiter...ich für meinen fall bin jetzt tot müde
und bei nen sternchen am ende gehts auch nicht ...wenn es nicht geht schmeißt er auch ab und an ne fehlermeldung ^^

Zum Seitenanfang

Haskell-Forum