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|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.

So is (1||1|) valid? Because accroding to your description it is, but it seems strange. Is (1|) really valid? — Niklas B.
– Niklas B., Commented Mar 16, 2014 at 16:52
That seems strange as well, I'll go ahead an introduce a new symbol so that there's not something like || which is pretty confusing. — user3412839
– user3412839, Commented Mar 16, 2014 at 17:16
Yes, please. That is the only thing that makes parsing awkward here — Niklas B.
– Niklas B., Commented Mar 16, 2014 at 17:16

Niklas B. · Accepted Answer · 2014-03-16 17:20:10Z

2

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, '')

edited Mar 16, 2014 at 17:20

answered Mar 16, 2014 at 17:00

Niklas B.

95.8k18 gold badges201 silver badges228 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Graeme Stuart Over a year ago

This fails on "1|" and "(1|1) is given as an example of a string that should pass.

Niklas B. Over a year ago

@GraemeStuart: Yes, but then again OP probably underspecified the grammar. Since I don't know all the special cases (is '(1||1||1)` allowed?) I can only give an example to maybe point OP into the right direction

Niklas B. Over a year ago

@GraemeStuart: I meant (1) instead of (1|1)

Collectives™ on Stack Overflow

Evaluating a string using recursion

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related