python - 我如何检测python中的无限循环

Question

我正在学习 Python 3 并正在做一个练习，该练习要求编写一个模拟/读取 BASIC 程序作为输入的 Python 程序。我坚持编写应该检测无限循环的 Python 程序部分。这是我到目前为止的代码:

def execute(prog):
   while True:
      location = 0
      if prog[location] == len(prog) - 1:
         break
         return "success"
      getT = prog[location].split()
      T = len(getT) - 1
      location = findLine(prog, T)
   visited = [False] * len(prog)

此处，prog 是包含 BASIC 程序的字符串列表(字符串的形式为 5 GOTO 30、10 GOTO 20 等)。

T是prog[location]中指示的目标字符串。

如果 BASIC 程序有死循环，那么我的 Python 程序也会有死循环。我知道如果任何一行被访问两次，那么它将永远循环，我的程序应该返回“无限循环”。

教程助手给出的提示是“初始化一个列表 visited = [False] * len(prog) 并在访问 prog[i] 时将 visited[i] 更改为 True。每次循环，一个值更新在 visited[] 中。考虑如何更改列表中的单个值。然后考虑如何确定 visited[] 中的哪个值需要更改。”

所以这是我坚持的部分。如何跟踪 prog 中的哪些字符串已被访问/循环？

Answer 1

我不确定我是否同意访问一行两次证明是一个无限循环。请参阅问题下的评论。但我可以回答实际问题。

提示如下:

A hint given by the tutorial assistant says "initialize a list visited = [False] * len(prog) and change visited[i] to True when prog[i] is visited. Each time through the loop, one value updates in visited[]. Think about how you change a single value in a list. Then think about how you identify which value in visited[] needs to change."

这是说你应该有两个列表，一个包含程序，一个包含真/假标志。第二个将被命名为 visited 并且最初包含 False 值。

Python代码就像提示说的那样:

visited = [False] * len(prog)

这使用 * 列表运算符“列表重复”来重复长度为 1 的列表并创建一个更长的新列表。

要将 visited[i] 更改为 True 很简单:

visited[i] = True

然后你可以这样做:

if visited[i]:
    print("We have already visited line {}".format(i))
    print("Infinite loop?  Exiting.")
    sys.exit(1)

请注意，我们通过简单地说 if visited[i]:

来测试 True 值

我们也可以这样写 if visited[i] == True: 但更短的形式就足够了并且在 Python 社区中是习惯的。这个和其他习惯用语记录在这里:http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html

对于这么小的程序，保留两个这样的列表也不错。对于更大、更复杂的程序，我更喜欢将所有内容放在一个地方。这将使用您可能还没有学过的“类”。像这样:

class ProgramCode(object):
    def __init__(self, statement):
        self.code = statement
        self.visited = False

prog = []
with open(input_basic_program_file, "rt") as f:
    for line in f:
        prog.append(ProgramCode(line))

现在我们有一个列表，而不是两个列表，其中每个项目都是一些 BASIC 代码和一个 visited 标志。

附言上面显示了一个明确的 for 循环，它重复使用 .append() 添加到列表中。经验丰富的 Python 开发人员可能会改用“列表理解”，但我想让它尽可能易于理解。

这是列表理解。如果现在看起来很奇怪，请不要担心；你的类(class)最终会教给你这个。

with open(input_basic_program_file, "rt") as f:
    prog = [ProgramCode(line) for line in f]