记一个简单的递归问题与解法

递归问题就像是俄罗斯套娃一样精妙，大的套小的，一层一层套在一起。

前些日子，一个朋友说看到一个算法题目，然后问我有思路吗？问题就是下面这样的：

这个问题很明显是个递归问题。我当时就夸下海口说，10分钟给你写个 Python 脚本。虽然实际上用了接近 30 分钟。。。

言归正传，这个问题的递归关系包含两种，嵌套关系和并列关系。比如 2[a]3[c] 最外层是并列关系，即 2[a] 和 3[c] 是两个互相并列的子问题，他们的解答串起来就是 2[a]3[c] 的解答。而 2[2[a]] 最外层则是一个嵌套关系，即要求 2[2[a]] 的解答需要先求子问题 2[a] 的解答 (这个解答显示就是 aa)，所以问题化解为 2[aa]。

所以思路就是，对于一个问题 X，先按并列关系划分为若干个子问题 X1, X2, …, Xn；如果 n 大于 1，那么各个子问题的答案串起来就是答案了；如果 n 等于 1，那么说明 X 最外层并不是并列关系而是嵌套关系或者根本就是单个字母，如果 X 是单个字母，那么答案就是它本身，反之，那么 X 一定是 s[Y] 的形式，答案就是 s 个 Y 的答案串起来。

def p_loc(input, left):
    count = 1
    i = left
    while count > 0:
        i += 1
        if input[i] == ']':
            count -= 1
        elif input[i] == '[':
            count += 1
    return i

def do(input):
    if '[' not in input:
        return input
    first = input.find('[')
    i = p_loc(input, first)
    if i < len(input) -1:
        parts = []
        while i < len(input) -1:
            parts.append(input[:i+1])
            input = input[i+1:]
            first = input.find('[')
            i = p_loc(input, first)
        parts.append(input[:i+1])
        res = ''
        for part in parts:
            res += do(part)
        return res
    else:
        right = p_loc(input, first)
        sub_res = do(input[first+1:right])
        return int(input[:first]) * sub_res
    

print(do('2[a]3[c]'))
print(do('2[2[a]]'))
print(do('2[2[a]]3[c]'))