algorithm - 计算开口支架的最大深度

Question

有以下四种形状的括号。

类型 1：'(' 或 ')'

类型 2：'{' 或 '}'

类型 3：'[' 或 ']'

类型 4：'<' 或 '>'

如果存在仅由上述四种形状的括号组成的字符串，则编写一个函数以返回最内括号的深度。深度由重叠的程度定义。最外层括号的深度为 1，最外层括号内的括号深度为 2，再多一个括号内的深度为 3。

示例：- “{([])[()(<>)]}” 这里最大深度为 4。让字符串包含有效括号。

Answer 1

简单的实现：

open_brackets = '[', '{', '(', '<'
close_brackets = ']', '}', ')', '>'

depth = 0
max_depth = 0

for character in string
    if open_brackets contains character
        depth++
        if depth > max_depth
            max_depth = depth
    else if close_brackets contains character
        depth--

return max_depth

请注意，这并不关心不匹配的括号（例如，它发现 '[(])' 可以接受）。

如果您确实想检查不匹配的括号，则需要一个堆栈。当你遇到一个开放的括号时，把它推到堆栈上。当您遇到右括号时，将顶部括号从堆栈中弹出，并确保它与该右括号的类型相同。就像是....

open_brackets = '[', '{', '(', '<'
close_brackets = ']', '}', ')', '>'

max_depth = 0
stack = new stack

for character in string
    if open_brackets contains character
        stack.push character
        if stack.count > max_depth
            max_depth = stack.count
    else if close_brackets contains character
        desired_closing_bracket = stack.pop
        if desired_closing_bracket is not the same type as character
           throw exception "Mis-matched bracket. Got {character}, expected {desired_closing_bracket"

return max_depth

该算法的弱点是，stack.pop如果您获得的右括号多于左括号，则该行可能会失败并出现异常。预测或捕获此异常并提供更有用的错误消息可能是明智的。

另外，如果要检查左括号的数量是否多于右括号，请检查循环后堆栈是否为空。

Answer 2

由于您没有指定语言，我将在 Python 中执行此操作。它也非常接近伪代码，您可以轻松地将其翻译成其他语言：

像这样的东西：

def maxdepth(s):
    depth = 0
    maxdepth = 0
    for c in s:
        print c
        if c in '[({<':
            depth = depth + 1
            maxdepth = max(maxdepth, depth)
            print depth, maxdepth
        elif c in '])}>':
            depth = depth - 1
            print depth, maxdepth
    return maxdepth