Evaluating a string using recursion

Question

I'm trying to create a function that returns True is the string passed in is '1'(valid) or '1*'(valid) or in the form of '(' + valid + '|' + valid + ')' (valid). What I mean by the last part is for example:

(1|1) <- since its in the form of '(' + valid + '|' + valid + ')' and '1' is valid. ((1|1)|1) <- since its in the form of '(' + valid + '|' + valid + ')' and (1|1) is valid and so is '1'

((1|(1|1))|1) <- since its in the form of '(' + valid + '|' + valid + ')' and (1|(1|1)) is valid and so is '1'

My plan:

• 1.) if the string passed in is '1', return True (Base Case)
• 2.) if the string passed in is '1'+'*', return True
• 3.) Else, if the string passed in begins with a '(' and ends with ')' look at the contents inside of the bracket and find the '|' symbol that's not inside of another bracket. Once it is found run the function again on the string on the left of the found symbol, and also run the function again on the string on the right of the found symbol. If both are True then the string is True (Recursive Step)
• 4.) Return False if anything else is passed in.

My code based on my plan:

def check(s):
    if s == '1':
        return True
    elif s == '1'+'*':
        return True
    else:
        if s.startswith('(') and s.endswith(')'):
            #TO-DO
            pass
    return False 

Some examples:

check('((1|1)|1)')
True
check('((1|1*)|1)')
True
check('(1|1)')
True
check('1')
True
check('1*')
True
check('((1|(1|1))|1)')
True
check('((1|(1|1))|((1|(1|1))|1))')
True
check('*1')
False
check('2')
False
check('((1|(1|1));1)')
False

I spent 3 days on this and still couldn't figure out how to do the recursive step so I'm hoping someone can help me with this. I can't figure out how to find the '*' symbol that is not within another set of brackets. I think if I'am able to find that '*' symbol than I can do the rest myself.

I'm sure that we can do this using the re module but let's just pretend we can't use that.

Answer 1

For parsing small grammars like this, I would suggest you to simplify them manually to a point where you can apply a non-backtracking recursive descent parser. The grammar you gave is:

valid ::= "1*" | "1" | "(" valid "|" valid ")"

so it is already non-left-recursive and ready to go, you just have to prefer 1* over 1. I suggest your parser functions to have type string -> (bool, string), where the bool indicates whether the parsing was successful and the second component is the unparsed rest of the string. Instead of the bool, you can also return an internal representation (AST) of the parsed string.

As an example, here is a parser for the valid production:

def valid(s):
    if s.startswith('1*'):
        return True, s[2:]
    if s.startswith('1'):
        return True, s[1:]
    if s.startswith('('):
        success, rest = valid(s[1:])
        if not success or not rest.startswith('|'): return False, s
        success, rest = valid(rest[1:])
        if not success or not rest.startswith(')'): return False, s
        return True, rest[1:]
    return False, s

def check(s):
    return valid(s) == (True, '')