#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2008
    Location
    El Paso
    Posts
    20
    Rep Power
    0

    Recursive String Function


    OK I got a new problem. I think I have a way to solve this one, except for one part. I have to create a string function that is recursive to see if a user inputted string matches a certain form. Ok I have to read a user string that needs to be using the characters {a,b,c}. The string is only recognized if it is in the form of acab. The first part ‘ a’ can be repeated or not be there at all. Also the ‘b’ at the end can be there or not, or repeated.

    Some examples of valid strings:
    ‘aaaaaaaaaaacab’, ‘cab’, ‘ca’, ‘acabbbb’, etc.

    Invalid strings:
    ‘gfsds’, ‘baca’, ‘bac’, etc.

    I think the way I am going to take on this one is just with two functions. A stringmatch function that calls a helper function. Basically I just need the stringmatch function to call the helper function(which will be recursive). The stringmatch just needs to return a true/false value. Like… if true “the string is recognized” or “false, the string is not recognized”.
    My one problem I have with this is the leading a, and ending b. Since they can be repeated, I was just wondering how that would be set up, and was wondering if anyone could provide any HINTs on how to set that up. If anything is unclear let me know. I will be working on this a little bit later.
  2. #2
  3. Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Dec 2004
    Location
    Meriden, Connecticut
    Posts
    1,797
    Rep Power
    154
    You don't need a helper function. Without giving you the exact answer, what you can do to keep it recursive is remove a character from the string each time around. For example if the function takes 1 argument (which is how it should be) and the value is "aaaaaaacab", it can do a simple check each time around and remove the first character of the string if it is still 'a' until there is only 1 'a' left at the start of the string. This is one method, though I"m sure there's several others. I'm on my way to work but I'm sure someone else may toss some code your way sometime today.

    Edit: I forgot you mentioned the 'a' can be repeated when it's first character. However, you can still apply the same concept I gave and just keep iterating through the string (via recursion) until you reach the next character in the string that is not equal to 'a'.
    Last edited by Yegg`; September 26th, 2008 at 02:34 PM.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2008
    Location
    El Paso
    Posts
    20
    Rep Power
    0
    Just a quick update. I seem to be stuck, I am just trying to see if the first character is going to match 'a' or 'c'. Here is just some rough code of what I have so far. I have yet to set up the strmatch function as recursive. I just want to check if the user inputed string is starting with either 'a' or 'c'. If it does not equal those characters then the program is just suppose to say fail. If it does start with those characters, then it continues on to check if the string is in the right form (acab, where leading a can be repeated and ending b can be repeated.) In the else condition this where i plan to make the recurisve call and remove the character.

    Right now I just need help getting started on the if/else condition to check if the string is coming in with the correct starting variables, which again can only be 'a' or 'c'.

    Here is the code so far. (remember real rough b/c ive been moving things around testing)

    Code:
    a = "a"
    b = "b"
    c = "c"
    def strmatch(string):
        length = len(string)
        start = string[0]
        print start #for testing
        if start != a or c:        
            print "fail"
        else:
            print "true"
        
        return string    
    
    
    
    
    userstring = raw_input("Please enter a string using the characters 'a', 'b', 'c': ")
    
    print "The string you entered: ", userstring
    
    newstring = strmatch(userstring)
    print "test: " , newstring
    Every time I run this the function just prints fail. Even if I input an a or c. I know I am just setting up the condition wrong. Any advice?
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    London, England
    Posts
    1,585
    Rep Power
    1373
    Every time I run this the function just prints fail. Even if I input an a or c. I know I am just setting up the condition wrong. Any advice?
    The problem is this line:
    Code:
        if start != a or c:
    - it is not doing what you think.

    Lets play around with it interactively:
    Code:
    >>> 'x' != 'a' or 'c'
    True
    >>> 'a' != 'a' or 'c'
    'c'
    >>> 'c' != 'a' or 'c'
    True
    Python interprets start != a or c as (start != a) or c. The 'and' and 'or' operators always return the last value to be evaluated. If start is not equal to a then the expression (start != a) will evaluate to true, and that will be the result of the whole expression - the 'c' is not evaluated or compared with anything. If start IS equal to a then (start != a) will be False, so c is returned as the value of the whole expression.

    You were probably thinking of something like (start != a) or (start != c), but that would not work either, since it will always be True.
    Here are some variations that would work:
    Code:
        (start != a) and (start != c)
    
        not ((start == a) or (start == c))
    
        start not in [a, c]
    The most python way is the last one.

    However it generally makes for more readable code if you reverse the if and else branches so you do not have a negative in the test, e.g.

    Code:
        if (start == a) or (start == c):
            print "true"
        else:
            print "fail"
    # or
        if start in [a, c]:
            print "true"
        else:
            print "fail"
    Dave
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    London, England
    Posts
    1,585
    Rep Power
    1373
    I am curious about where this exercise came from, and why the function has to be recursive.

    Although it is important to know HOW to do recursion, it is equally important to know WHEN to do recursion. You need to write recursive functions when the problem itself is recursive or you are dealing with recursive data structures - that is not the case in this situation, so IMHO the exercise teaches bad habits.

    Recursion in Python has sever limitations compared to iteration: Unlike Lisp, Python does not do tail-call optimisation. Function calls have a high overhead, and there is a limit to the depth of the stack so deeply recursive functions can cause a stack overflow exception.

    I would also not use recursion when there is a much simpler solution in the standard library:
    Code:
    import re
    re.match("a*cab*$", string)
    Dave
    Last edited by DevCoach; September 29th, 2008 at 03:40 PM.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2008
    Location
    El Paso
    Posts
    20
    Rep Power
    0
    Originally Posted by DevCoach
    I am curious about where this exercise came from, and why the function has to be recursive.

    Although it is important to know HOW to do recursion, it is equally important to know WHEN to do recursion. You need to write recursive functions when the problem itself is recursive or you are dealing with recursive data structures - that is not the case in this situation, so IMHO the exercise teaches bad habits.

    Recursion in Python has sever limitations compared to iteration: Unlike Lisp, Python does not do tail-call optimisation. Function calls have a high overhead, and there is a limit to the depth of the stack so deeply recursive functions can cause a stack overflow exception.

    I would also not use recursion when there is a much simpler solution in the standard library:
    Code:
    import re
    re.match("a*cab*$", string)
    Dave
    I am actually taking a Python leveling course for work. I have some programming knowledge. I understand recrusive calls from C++. This excerise is suppose to not use any of the standard library code. Which stinks. I am not good at recursion, as I fully do not understand it. I do understand that Python does not do any kind of tail-call recursion. Here is what I have so far.

    Any more help would be greatly appreciated. Also do you know where I can find more of the standard library calls? I am about to search for a complete listing and I am pretty sure that I can find it on python.org. Python has actually become one of my favortie languages even though I know little about it. It seems much easier than C and java.

    Here is what I have so far:


    Code:
    a = "a"
    b = "b"
    c = "c"
    def strmatch(string):
        length = len(string)
        start = string[0]
        print start #for testing
        if start in [a,c]:
            string = string[1:]
            print "good" 
            strmatch(string)
        elif start in b:
            string = string[1:]
            strmatch(string)
        elif start == NULL:
            print "over"
        else:
            print "String is not recognized"
    
        
        return string
    The problem I am getting, is if I input a string "acab" it errors because start[0] is out of index, which I can fix. Just wanted to share what I had so far.


    I know that the b should not b in start, but I have no clue on how to do it for the middle character? If that makes sense.(NOTE: string can only start with a or c according to the excerise, and yes I do realize here that b if the user inputed a string with this code it can be taken as it could start with b, even though it really cant. Just trying to get something.) I also was wondering if there was a different way to strip the first character of the string, that way it can be called recursivly with the next character removed.

    I just want to thank you guys again, everything I have gotten from here has been nothing less than excellent. Really good advice!
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2008
    Posts
    96
    Rep Power
    45
    hi sigeptxchi,

    Maybe I could help, but can you provide sample input, and output? and some conditions and requirements? I can't follow your post... especially if I read recursive string functions... which I don't know what kind of function is this for string?
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2008
    Location
    El Paso
    Posts
    20
    Rep Power
    0
    The function that I provided on my previous post is suppose to be a recursive function that takes in a string, and returns a string. It is suppose to be in the form of acab...where the leading a can be repeated or not be there at all. The last character(b) is suppose can be there or it might not be there. Some sample input/output could be

    >>> Enter a string: aaaaaaaaaacabbbbbbb (input)
    >>> String is recognized. (output)

    >>>Enter a string: cab (input)
    >>> String is recognized. (output)

    >>>Enter a string: dbfjssd (input)
    >>>String is not recognized (output)

    >>>Enter a string: ccab (input)
    >>>String is not recognized (output)

    >>>Enter a string: bbbbbacd (input)
    >>> String is not recognized (output)

    >>>Enter a string: ca (input)
    >>> String is recognized (output)


    So the function I provided in my above post, just ignore all the print statements because I was using those when I was debugging earlier. Like I said before the form of the string has to be in acab. with the leading a and trailing b, they can be there, or not be there, and if they are there they can be repeated multiple times.

    Hope that makes it a little bit clearer.
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2008
    Posts
    96
    Rep Power
    45
    According to what I understand....

    Try this code:


    python Code:
    def strmatch(ustr):
     
        # Determine first the lenght of string
        ulen = len(ustr)
        """ if only 1 string is given LOL where's the 'ca' on that case?"""
        if ulen == 1: return False
     
        """ if only 2 then it should be 'ca' """
        if ulen == 2:
            if ustr == 'ca':
                return True
            else:
                return False
     
        """ just in case only 3 then it should be something like:
           'aca' or 'cab' we should find first the 'ca'
           before scanning the rest of the characters. """
     
        if ulen == 3:
            #need to have try and except, .index raise may raise an exceptions.
            try:
                ix = ustr.index('ca')
            except:
                if ValueError:
                    return False
     
            # checking the last character
            if ix == 0 and ustr[ulen-1:] == 'b':
                return True
     
            #checking the first character
            if ix == 1 and ustr[:ix] == 'a':
                return True
     
            return False
     
        """ The real battle begins here with more than 4 characters
            although you can combined this in 3 chars, but better  to
            do this way for the meantime.
        """
        # Whatever happens we should have 'ca' otherwise, all are invalid.
        if ulen > 3:
            try:
                ix = ustr.index('ca')
            except:
                if ValueError:
                    return False
     
            # The rest will just scan trim the string found in between 'ca'
            stat = 1
            txt1 = ustr[:ix] #This can be empty string eg. 'cabbb' 
            txt2 = ustr[ix+2:] #This can be empty string eg. ''aaaaaaaaaca'
     
            if txt1 != '': #who want's to scan an empty string?
                for i in txt1:
                    if i != 'a':
                        #print "Changing Status @ " + ustr
                        stat = 0
     
            if txt2 != '':#who want's to scan an empty string?
                for i in txt2:
                    if i != 'b':
                        #print "Changing Status @ " + ustr
                        stat = 0
            if stat: return True
            else: return False 
        return None
     
     
    if __name__ == '__main__':
     
        TestValid = ['ca', 'aca', 'cab', 'acab', 'aaaaacab', 'cabbbb', 'aaacabbbbbb']
        TestInvalid = ['c', 'acca', 'caab', 'accab', 'bca', 'caaab', 'caaabb', '']
        # the value '' is just a test to return None value.    
     
        print "\nTesting valid strings\n"
        for i in TestValid:
            print "Reading string:\t '"+i+"'......."+str(strmatch(i))
     
        print "\nTesting Invalid strings\n"
        for i in TestInvalid:
            print "Reading string:\t '"+i+"'......."+str(strmatch(i))

    output is:
    Testing valid strings
    Reading string: 'ca'.......True
    Reading string: 'aca'.......True
    Reading string: 'cab'.......True
    Reading string: 'acab'.......True
    Reading string: 'aaaaacab'.......True
    Reading string: 'cabbbb'.......True
    Reading string: 'aaacabbbbbb'.......True

    Testing Invalid strings

    Reading string: 'c'.......False
    Reading string: 'acca'.......False
    Reading string: 'caab'.......False
    Reading string: 'accab'.......False
    Reading string: 'bca'.......False
    Reading string: 'caaab'.......False
    Reading string: 'caaabb'.......False
    Reading string: ''.......None
    I was thinking to use some regular expression... I try it some other time...

    Mark
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2008
    Location
    El Paso
    Posts
    20
    Rep Power
    0
    Mark - I checked the code, and it works great, and it was every easy to understand. The only thing is, and if i missed it, the function strmatch is non-recursive. I really want to thank you for your help. I think I can modify it to make it recursive (maybe). LOL I am not really good at recursion. BUt once again thank you to everyone that provided me with some input.
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    London, England
    Posts
    1,585
    Rep Power
    1373
    I stand by what I said - recursion is the wrong tool for this problem. By insisting on a recursive solution, your tutor is teaching the class bad habits.

    Dave
  22. #12
  23. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2008
    Location
    Germany
    Posts
    25
    Rep Power
    0
    I guess it's only a matter of thinking a little bit in the
    Lisp/Prolog style.

    So here is my recursive solution (if i understand it right):
    python Code:
     
    def match(s):
     
      if not 'ca' in s:
        return False
     
      if s == 'ca':
        return True
     
      if s[0] == 'a':
        return match(s[1:])
      if s[-1] == 'b':
        return match(s[:-1])
     
      return False
     
     
     
    test_valid = ['ca', 'aca', 'cab', 'acab', 'aaaaacab',
                  'cabbbb', 'aaacabbbbbb']
    test_invalid = ['c', 'acca', 'caab', 'accab',
                    'bca', 'caaab', 'caaabb', '']
     
    print map(match, test_valid)
    print map(match, test_invalid)



    yipyip

    Comments on this post

    • MarkCuering agrees : excellent!
  24. #13
  25. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2008
    Posts
    96
    Rep Power
    45
    +1 on that
  26. #14
  27. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2008
    Posts
    96
    Rep Power
    45
    Originally Posted by sigeptxchi
    Mark - I checked the code, and it works great, and it was every easy to understand. The only thing is, and if i missed it, the function strmatch is non-recursive. I really want to thank you for your help. I think I can modify it to make it recursive (maybe). LOL I am not really good at recursion. BUt once again thank you to everyone that provided me with some input.
    I haven't seen the recursion requirements from the instruction you given me but you can refer to yipyip code...

    looking @ yipyip code, to help you analyze quickly:

    python Code:
    def match(s):
     
      if not 'ca' in s:
        return False
     
      if s == 'ca':
        print "\nFinally... 'ca' is left returning TRUE\n"
        return True
     
      if s[0] == 'a':
        print 'Trimming LEFT:\t'+ s[1:]
        return match(s[1:])
     
      if s[-1] == 'b':
        print 'Trimming RIGHT:\t' + s[:-1]
        return match(s[:-1])
     
      print "\nOopps... Got '" +s[0]+ "' On this point\n"
      return False
     
    test = ['aaaaaaaaaaaaaaacabbbbbb', 'aaaaaxcabbbb']
    print map(match, test)
  28. #15
  29. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2008
    Location
    El Paso
    Posts
    20
    Rep Power
    0

    Thanks to everyone


    Thanks to everyone who put input in. I've been out of the loop. I've been really busy at work. Once again thanks guys. I've modified a bit of everyones code. I was wondering if there were any good books on python programming out there? I am trying to find some stuff on python classes. All the stuff I've found online has been off the python.org website. I am just looking for class information. I may post something in a more general post, but if anyone can leave some titles or links that would be awesome. Once again, I havent searched for it; but i will.

IMN logo majestic logo threadwatch logo seochat tools logo