newB 在 Udacity Comp 与 Backus Naur 作斗争。科学。 101

Question

我正在完成 Udacity 的计算机科学入门 101 课程，正在寻求一些帮助来解决最后的测验问题之一。以下代码在提交时 return 编辑了 "pass"，但我觉得我没有掌握本测验中挑战的核心。任何有关如何处理和思考问题的帮助或建议将不胜感激。

问题：

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

此代码将 return 对于给定 Backus-Naur 形式的提交不是为真：

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

比如'11111011111'

print in_language('11111011111') == False

我仍然在思考递归问题，但似乎有一种方法可以递归地解决这个问题？那个或我的下一步将是检查字符串的第一个和最后一个字符以查看它们是否完全是零和一个（不是两者），然后删除它们并继续修剪字符串直到我到达基本情况，或者，"middle" 零。我很惊讶代码此时通过了测验。

值得注意的是，我对代码的看法：

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' for i in bnf) .

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

第三个"if"类似地寻找给定B-N形式的限定特征——无论根据给定语法的表达式是什么，中间都会有一个零——并利用Pythons楼层划分以及索引从零开始。

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

由于我是 Whosebug 的新手，我在发帖前研究了这个问题。任何发帖风格注意事项（太冗长？）或疑虑也会有所帮助:)

好的，

我采纳了 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

但是，我完全是一个 newB @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

（您当前的解决方案是 "false solution" -- 它会通过问题中给出的测试，但会在某些其他输入上失败。例如，字符串 000 不是用这种语言，但你的函数会说它是。）

newB 在 Udacity Comp 与 Backus Naur 作斗争。科学。 101

newB struggling with Backus Naur at Udacity Comp. Sci. 101

python

recursion

python-2.x

bnf