时间戳

首页 > 解决方案 > 字符串的递归解压

python - 字符串的递归解压

问题描述

我正在尝试使用递归解压缩字符串。例如，输入：

3[b3[a]]

应该输出：

咩咩咩

但我得到：

咩咩咩咩咩咩咩咩咩咩咩咩咩

我有以下代码，但它显然是关闭的。第一个 find_end 函数按预期工作。我对使用递归和任何帮助理解/跟踪额外字母的来源或任何帮助我理解这种非常酷的方法的一般提示绝对是新手，将不胜感激。

def find_end(original, start, level):
    if original[start] != "[":
        message = "ERROR in find_error, must start with [:", original[start:]
        raise ValueError(message)
    indent = level * "  "
    index = start + 1
    count = 1
    while count != 0 and index < len(original):
        if original[index] == "[":
            count += 1
        elif original[index] == "]":
            count -= 1
        index += 1
    if count != 0:
        message = "ERROR in find_error, mismatched brackets:", original[start:]
        raise ValueError(message)
    return index - 1


def decompress(original, level):
# set the result to an empty string
    result = ""
# for any character in the string we have not looked at yet
    for i in range(len(original)):
# if the character at the current index is a digit
        if original[i].isnumeric():
# the character of the current index is the number of repetitions needed
            repititions = int(original[i])
# start = the next index containing the '[' character
            x = 0
            while x < (len(original)):
                if original[x].isnumeric():
                    start = x + 1
                    x = len(original)
                else:
                    x += 1
# last = the index of the matching ']'
            last = find_end(original, start, level)
# calculate a substring using `original[start + 1:last]
            sub_original = original[start + 1 : last]
# RECURSIVELY call decompress with the substring
            # sub = decompress(original, level + 1)
# concatenate the result of the recursive call times the number of repetitions needed to the result
            result += decompress(sub_original, level + 1) * repititions
# set the current index to the index of the matching ']'
            i = last
# else
        else:
# concatenate the letter at the current index to the result
            if original[i] != "[" and original[i] != "]":
                result += original[i]
# return the result
    return result


def main():
    passed = True
    ORIGINAL = 0
    EXPECTED = 1
    # The test cases
    provided = [
        ("3[b]", "bbb"),
        ("3[b3[a]]", "baaabaaabaaa"),
        ("3[b2[ca]]", "bcacabcacabcaca"),
        ("5[a3[b]1[ab]]", "abbbababbbababbbababbbababbbab"),
    ]
    # Run the provided tests cases
    for t in provided:
        actual = decompress(t[ORIGINAL], 0)
        if actual != t[EXPECTED]:
            print("Error decompressing:", t[ORIGINAL])
            print("   Expected:", t[EXPECTED])
            print("   Actual:  ", actual)
            print()
            passed = False
    # print that all the tests passed
    if passed:
        print("All tests passed")


if __name__ == '__main__':
    main()

标签： python

解决方案

从我从您的代码中收集的内容来看，它可能会给出错误的结果，因为您在给定级别查找最后一个匹配的右大括号时采用的方法（我不是 100% 确定，代码很多）。但是，我可以建议使用堆栈的更简洁的方法（几乎类似于 DFS，没有复杂性）：

def decomp(s):
    stack = []
    for i in s:
        if i.isalnum():
            stack.append(i)
        elif i == "]":
            temp = stack.pop()
            count = stack.pop()
            if count.isnumeric():
                stack.append(int(count)*temp)
            else:
                stack.append(count+temp)
    for i in range(len(stack)-2, -1, -1):
        if stack[i].isnumeric():
            stack[i] = int(stack[i])*stack[i+1]
        else:
            stack[i] += stack[i+1]
    return stack[0]

print(decomp("3[b]"))          # bbb
print(decomp("3[b3[a]]"))      # baaabaaabaaa
print(decomp("3[b2[ca]]"))     # bcacabcacabcaca
print(decomp("5[a3[b]1[ab]]")) # abbbababbbababbbababbbababbbab

这适用于一个简单的观察：不是在读取 a 之后[评估子字符串，而是在遇到 a 之后评估子字符串]。这将允许您在单独评估各个部分之后构建结果。（这类似于使用编程的前缀/后缀评估）。
（如果您愿意，您也可以为此添加错误检查。在一次传递中检查字符串在语义上是否正确并在另一次传递中对其进行评估会更容易，而不是一次性完成）

推荐阅读