algorithm - 递归:打印隐含的括号

Question

我正在尝试打印所有括号，但我坚持只打印一个输出而不是所有隐含的括号。

如何显示所有可能的隐含括号？ From here我明白了。

我无法获得打印所有隐含括号的方法。

def add_up(exp):
        operators = ["+", "/", "*", "-"]
        if len(exp) == 1:
            return exp
        result = ""
        for i in range(0, len(exp)):
            if exp[i] in operators:
                left = add_up(exp[0:i])
                right = add_up(exp[i+1:len(exp)])
                result = "(" + left + exp[i] + right + ")"
        return result

print(add_up("3*4+5"))

Answer 1

您的代码返回单个结果，而解决方案包含多个可能的结果。当然，当您递归时，左右分支也可能产生不止一个结果。

您可以通过将您的函数转换为生成器然后遍历结果来解决此问题:

operators = ["+", "/", "*", "-"]

def add_up(exp):
    if len(exp) == 1:
        yield exp

    for i in range(0, len(exp)):
        if exp[i] in operators:
            for left in add_up(exp[:i]):
                for right in add_up(exp[i + 1:]):
                    yield "(" + left + exp[i] + right + ")"

for e in add_up("1+2*3+4"):
    print e, ':', eval(e)

或者(更详细)，您可以制作结果列表:

def add_up(exp):
    if len(exp) == 1:
        return [exp]

    result = []

    for i in range(0, len(exp)):
        if exp[i] in operators:
            for left in add_up(exp[:i]):
                for right in add_up(exp[i + 1:]):
                    result += ["(" + left + exp[i] + right + ")"]

    return result