编写 Smallf*ck 解释器

Question

我要解决的问题是这个 Codewars 套路：https://www.codewars.com/kata/58678d29dbca9a68d80000d7/train/python

我通过了 124 项测试中的 123 项，但我失败的一项与我处理嵌套循环的方式有关。我似乎无法找到一种方法来复制问题，因为它们没有向您显示测试输入。任何帮助表示赞赏；到目前为止，这是我对这个问题的看法：

import re

def interpreter(code, tape):
    #Filter out non-command characters
    code_pure = re.findall(r"(\>|\<|\*|\[|\])", code)
    sf = "".join(code_pure)
    #Convert tape to list so that elements are mutable
    tape_list = []
    for bit in tape:
        tape_list.append(bit)
    #Keep track of pointer and instruction position
    pointer = 0
    instr = 0
    brack_pos = [] #Contains positions of "[" brackets
    while instr < len(sf):
        #If pointer goes out of bounds then end the program
        if pointer >= len(tape_list) or pointer < 0:
            return "".join(tape_list)
        #"*" flips the current bit
        if sf[instr] == "*":
            if tape_list[pointer] == "1":
                tape_list[pointer] = "0"
            elif tape_list[pointer] == "0":
                tape_list[pointer] = "1"
            instr += 1
        #Move right one bit
        elif sf[instr] == ">":
            pointer += 1
            instr += 1
        #Move left one bit
        elif sf[instr] == "<":
            pointer -= 1
            instr += 1
        elif sf[instr] == "[":
            #If pointer is on 0, skip the loop
            if tape_list[pointer] == "0":
                brack_cnt = 1
                while brack_cnt != 0:
                    instr += 1
                    if sf[instr] == "[":
                        brack_cnt += 1
                    elif sf[instr] == "]":
                        brack_cnt -= 1
                instr += 1
             #If pointer is 1, step into the loop
            elif tape_list[pointer] != "0":
                brack_pos.append(instr)
                instr += 1
        elif sf[instr] == "]":
            if tape_list[pointer] == "0":
                instr += 1
            elif tape_list[pointer] != "0":
                instr = brack_pos[-1] 
                brack_pos.pop()
    
    return "".join(tape_list)

Answer 1

问题出在检查 sf[instr] == "]" 的最后一个 if 块中，其中 brack_pos.pop() 仅在循环回到左括号时执行，而不是在移动经过右括号时执行。 IE。 brack_pos.pop()需要无条件。

顺便说一句，这似乎是一个有趣的练习。这是我想出的：

def interpreter(code, tape):
    # Implement your interpreter here
    tape = list(tape)
    # Find matching brackets
    jump = [0]*len(code)
    open_bracket_stack = []
    for i,c in enumerate(code):
        if c == '[':
            open_bracket_stack.append(i)
        elif c == ']':
            matching = open_bracket_stack.pop()
            jump[i] = matching
            jump[matching] = i
    code_ptr = 0
    tape_ptr = 0
    while(code_ptr < len(code) and tape_ptr < len(tape) and tape_ptr >= 0):
        c = code[code_ptr]
        if c == '>':
            tape_ptr += 1
        elif c == '<':
            tape_ptr -= 1
        elif c == '*':
            tape[tape_ptr] = '1' if tape[tape_ptr] == '0' else '0'
        elif c == '[' and tape[tape_ptr] == '0':
            code_ptr = jump[code_ptr]
        elif c == ']' and tape[tape_ptr] == '1':
            code_ptr = jump[code_ptr]
        code_ptr += 1
    return "".join(tape)

编写 Smallf*ck 解释器

Writing a Smallf*ck interpreter

python

algorithm

interpreter