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

Question

有如下四种形状的括号。

Type 1 : '(' or ')'

Type 2 : '{' or '}'

Type 3 : '[' or ']'

Type 4 : '<' or '>'

如果有一个字符串只由上述四种形状的括号组成，写一个函数返回最里面括号的深度。深度由重叠的程度定义。最外层括号的深度为 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 行可能会失败并出现异常。预测或捕获此异常并提供更有用的错误消息可能是明智的。

此外，如果您想检查左括号是否多于右括号，请检查循环后堆栈是否为空。