python - newB 在 Udacity Computer 与 Backus Naur 斗争。科学。 101

Question

我即将完成 Udacity 的计算机科学入门 101 类(class)，并正在寻求一些帮助来解决最终测验问题之一。以下代码在提交时返回“通过”，但我觉得我没有捕获本次测验中挑战的核心。任何有关如何处理和思考问题的帮助或建议将不胜感激。

问题:

"""
Define a Python procedure, in_language(<string>), 
that takes as input a string and returns True 
if the input string is in the language described by the BNF grammar below 
(starting from S) and returns False otherwise. 

BNF grammar description:
S => 0 S 1 
S => 1 S 0
S => 0
"""
# Tests. These all should print True if your procedure is defined correctly
print in_language("00011") == True
print in_language("0") == True
print in_language("01") == False
print in_language("011") == False
print in_language("01002") == False

这是我到目前为止的代码:

def in_language(bnf):
    if len(bnf) % 2 == 0:
        return False
    if any(i in '23456789' for i in bnf) == True:
        return False
    if bnf[len(bnf)/2] != '0':
        return False
    else:
        return True

对于不给定巴科斯-诺尔表单的提交，此代码将返回 True:

S => 0 S 1 
S => 1 S 0
S => 0

例如“11111011111”

print in_language('11111011111') == False

我仍然对递归很感兴趣，但似乎有一种方法可以递归地解决这个问题？或者我的下一步是检查字符串的第一个和最后一个字符，看看它们是否完全是零和一(不是两者)，然后删除它们并继续修剪字符串，直到到达基本情况，或“中间”零。我很惊讶代码此时通过了测验。

值得注意的是，我对代码的思考:

if len(bnf) % 2 == 0:

我想到了第一个 if 条件，因为给定 B-N 形式，任何迭代都会产生奇数个数字，因此字符串长度能被 2 整除表示不属于这种形式。

if any(i in '23456789' for i in bnf) == True:

第二个“if”也是一个简单的考虑因素，因为问题只是寻找由 1 和 0 构成的字符串(我想我也可以包含字母表，或者简单地写成 if any(i not in '01' 代表 bnf 中的 i) .

if bnf[len(bnf)/2] != '0':

第三个“if”类​​似地寻找给定 B-N 形式的限定特征 - 无论根据给定语法的表达式是什么，中间都会有一个零 - 并利用 Python 的底除法因为索引从零开始。

任何替代解决方案的想法或建议将不胜感激，谢谢!

由于我是 StackOverflow 的新手，我在发布之前研究了这个问题。任何发布风格的考虑(太冗长？)或担忧也会有帮助:)

<小时/>

好的，

我采纳了 duskwoof 的建议并提出了这个:

def in_language(bnf):
# corresponding to: S => 0 S 1
    if bnf[0] == '0' and bnf[-1] == '1':
        return in_language(bnf[1:-1])
# corresponding to: S => 0 S 1
    if bnf[0] == '1' and bnf[-1] == '0':
        return in_language(bnf[1:-1])
# corresponding to: S => 0
    if bnf == '0':
        return True
    return False

它适用于遵循该表单的案例，但是当我提交不遵循该表单的案例时，Python会感到厌烦……而且我仍然觉得我在递归和解析巴科斯-诺尔表单的字符串方面缺少一些东西。对于不符合表格的情况我应该如何考虑处理？感谢您的帮助。我会继续努力解决这个问题。

<小时/>

这似乎效果更好 - 通过了所有测试用例:

def in_language(bnf):
    if len(bnf) > 2:
# corresponding to: S => 0 S 1
        if bnf[0] == '0' and bnf[-1] == '1':
            return in_language(bnf[1:-1])
# corresponding to: S => 0 S 1
        if bnf[0] == '1' and bnf[-1] == '0':
            return in_language(bnf[1:-1])
# corresponding to: S => 0
    if bnf == '0':
        return True
    return False

但是，我完全是一个新手@programming，所以任何建议或输入都会非常有帮助......我仍然不觉得我有一个非常通用的解决方案；只是这个特定 BNF 语法的特定内容。

Answer 1

I am still wrapping my head around recursion, but it seems like there is a way to address this problem recursively?

这正是您解决此问题的方式。不要试图通过分析该语言中的字符串将具有哪些属性(例如，长度模 2、它将包含哪些字符，等等)来过度思考问题!虽然这可能适用于这种特定语言，但它不适用于一般情况；有些语言太复杂，无法编写像您所描述的那样的迭代解决方案。

您的解决方案应该是语言描述的直接翻译 - 您不必过多考虑规则的含义! -- 并且应该对右侧有 S 的规则使用递归。应该写成这样的形式:

def in_language(bnf):
    if ...: # corresponding to: S => 0 S 1
        return True
    if ...: # corresponding to: S => 1 S 0
        return True
    if ...: # corresponding to: S => 0
        return True
    return False

(您当前拥有的解决方案是“错误解决方案”——它将通过问题中给出的测试，但在某些其他输入上会失败。例如，字符串 000 不是用这种语言，但你的函数会说它是。)