python - 使用递归评估字符串

Question

我正在尝试创建一个返回 True 的函数，如果传入的字符串是 '1'(有效)或 '1*'(有效)或在'(' + valid + '|' + valid + ')' 的形式(有效)。最后一部分的意思是例如:

(1|1) <- 因为它的形式是 '(' + valid + '|' + valid + ')' 和 ' 1' 有效。 ((1|1)|1) <- 因为它的形式是 '(' + valid + '|' + valid + ')' 和 (1|1) 是有效的，'1'也是如此

((1|(1|1))|1) <- 因为它的形式是 '(' + valid + '|' + valid + ')' 和 (1|(1|1)) 是有效的，'1'

也是有效的

我的计划:

• 1.) 如果传入的字符串是'1'，返回True(Base Case)
• 2.) 如果传入的字符串是'1'+'*'，则返回True
• 3.) 否则，如果传入的字符串以“(”开头并以“)”结尾 查看括号内的内容并找到'|'象征 那不在另一个括号内。一旦找到再次运行该功能 在找到的符号左侧的字符串上，并再次运行该函数 在找到的符号右侧的字符串上。如果两者都为真则字符串 为真(递归步骤)
• 4.) 如果传入任何其他内容，则返回 False。

我的代码基于我的计划:

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 

一些例子:

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

我在这上面花了 3 天，但仍然无法弄清楚如何执行递归步骤，所以我希望有人能帮助我解决这个问题。我不知道如何找到不在另一组括号内的 '*' 符号。我想如果我能找到那个 '*' 符号，我就可以自己完成剩下的事情。

我确信我们可以使用 re 模块来做到这一点，但让我们假装我们不能使用它。

Answer 1

为了解析像这样的小语法，我建议您手动将它们简化到可以应用非回溯的程度 recursive descent parser .你给出的语法是:

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

所以它已经是非左递归的并且可以使用了，你只需要更喜欢 1* 而不是 1。我建议您的解析器函数具有 string -> (bool, string) 类型，其中 bool 指示解析是否成功，第二个组件是未解析的其余部分字符串。除了 bool，您还可以返回已解析字符串的内部表示 (AST)。

例如，这里是valid 产生式的解析器:

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