I am working on an assignment in python. The goal is to make a function with two parameters, one for a string and the other for a pattern. If the pattern appears in the string, the program must return true, or false if otherwise. Also, the pattern can accept *'s to represent any number of characters can appear in between and the pattern is still good.
ex.
matchPat(a*t*r. anteaters)
True
matchPat(a*t*r. albatross)
Ture
matchPat(a*t*r. albatross)
False

I have the function set to look through the string one at a time for a match with the first character of the pattern. If true it dumps that character and letters in the string it looked for.

It goes through good enough, but once I get to the end I get an index error since I am usually passes pattern in as "" which isnt allowed. Problem is when I block that instance all I get for an output is None and not true which is what I need.

I put some print statements up and noticed when I get to the end of pattern and the end of the string, I get a random burp of previous values, so I am guessing something in my recursion is off. Any pointers pros? Oh, and no uses of loops

def matchPat(CH, string):
    print(CH)
    print(string)
    input("")
    if not CH:
        return True
    elif CH[0] == string[0]:
        return matchPat(CH[1:], string[1:])
    elif CH[1] == string[0] or matchPat(CH, string[1:]):
        matchPat(CH[1:], string)
        print(CH)
        print(string)

print(matchPat("a*t*r","anteater"))

Recommended Answers

All 5 Replies

You want to use the re nodule. There are examples of use as well as a full reference. Be aware of the difference between the search and the match methods.

You have to test for a length of 2 or greater, otherwise you get and index error on the [1:]s.

return matchPat(CH[1:], string[1:])
    elif CH[1] == string[0] or matchPat(CH, string[1:]):

Note also that line 10
matchPat(CH[1:], string)
does not catch the return from the matchPat function so the "return True" is never caught. Add some print statements so you can see what is happening with each recursion.

This my try seems to work, I do not know if I am overcomplicating things, but you could compare this to your try and maybe debug the problem:

from __future__ import print_function

def match_pat(CH, mystring):
    print ("%r vs %r" % (CH, mystring))
    if not CH:
        return not mystring
    elif CH == '*':
        return True
    elif not mystring:
        return False
    elif CH[0] == '*':
        return any(match_pat(CH[1:],mystring[index:]) for index in range(len(mystring)))
    else:
        return CH[0] == mystring[0] and match_pat(CH[1:], mystring[1:]) 

pat = 'a*at*r*' 
for word in ("anteater",'albatross','albania'):
    print(word, pat, match_pat(pat,word))
    print('-'*30)

This my try seems to work, I do not know if I am overcomplicating things, but you could compare this to your try and maybe debug the problem:

from __future__ import print_function

def match_pat(CH, mystring):
    print ("%r vs %r" % (CH, mystring))
    if not CH:
        return not mystring
    elif CH == '*':
        return True
    elif not mystring:
        return False
    elif CH[0] == '*':
        return any(match_pat(CH[1:],mystring[index:]) for index in range(len(mystring)))
    else:
        return CH[0] == mystring[0] and match_pat(CH[1:], mystring[1:]) 

pat = 'a*at*r*' 
for word in ("anteater",'albatross','albania'):
    print(word, pat, match_pat(pat,word))
    print('-'*30)

This code is great and works fine. The only problem is with line 12 I believe it is where you say:

return any(match_pat(CH[1:],mystring[index:]) for index in range(len(mystring)))

Is there any way to change this line so it doesn't use a for loop or the any operator? Both of these are not allowed in the final submission.

You could replace the loop part by appropriate recursion. That is appropriate home work for you to understand how.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.