使用s的Python字符数学

Question

我在一次算法会议上收到了一个有趣的挑战。给定一个输入字符串，返回一个字符串，其中括号内的所有子字符串已被复制n次，其中n是括号外的整数。括号外的字符应该简单地连接到括号内的子字符串。例如：

• 2[ab]应该返回abab
• a[3[bc]]应该返回abcbc
• 2[ab[cd]]应该返回

我已经开始使用堆栈来实现这个解决方案，但是我感觉我检查每个取消堆叠的字符是否有括号的方法是错误的，有人有什么建议吗？代码如下

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def length(self):
        return len(self.items)

def is_number(s):
    try:
        int(s)
        return True
    except ValueError:
        return False

def character_math(charstr):
    final_output = ""
    substring = ""
    for i in charstr:
        myStack.push(i)

    for m in range(myStack.length() - 2):
        destacked = myStack.pop()
        # We want to go to the inner-most right bracket
        if destacked != "]":
            substring += destacked
        if destacked == "[":
            possible_multiplier = myStack.pop()
            if is_number(possible_multiplier):
                final_output += int(possible_multiplier) * substring
            else:
                final_output += possible_multiplier[::-1]
                break
        final_output += substring[::-1]
    return "Final output is ", final_output

myStack = Stack()
# 3[ab[cd]] should return 'abcdabcd'
sample_str = '2[ab[cd]]'
print(character_math(sample_str))

Answer 1

最好的方法是使用递归算法。其思想是重复一个函数，直到条件匹配为止。这是我使用的代码，它适用于你的例子，我不认为我忘记了一个可能性。你知道吗

# -*-coding:Utf-8 -*

Input = "2[ab[cd]]"

def Treatment(STR):

    # Exit the treatment. That's the end condition.
    if "[" not in STR:
        return STR

    # Find the inner [], in this case, the "cd" part
    Bound1_ID = len(STR) - STR[::-1].index("[") - 1
    Bound2_ID = STR.index("]")

    # Separate STR into : First_part + middle between [] + Last_part
    Last_part = STR[Bound2_ID + 1:]

    # First_part depends if there is a number or not
    try:
        Multiplier = int(STR[Bound1_ID - 1])
        First_part = STR[:Bound1_ID - 1] 
    except:
        Multiplier = 1
        First_part = STR[:Bound1_ID]

    Middle_part = STR[Bound1_ID + 1: Bound2_ID] * Multiplier

    # Assemble the new STR :
    New_STR = First_part + Middle_part + Last_part

    # Recursive command, repeat the function on the new STR
    return Treatment(New_STR)

print (Treatment(Input))

编辑：它就是这么做的：

• 第一次迭代：“2[ab[cd]]”
• 第二次迭代：“2[abcd]”
• 第三次迭代：shu xiao=>；不再有“[”，所以到此为止。你知道吗