计算开口支架的最大深度

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如果你得到的结束括号多于左括号,那么该行可能会失败并出现异常.预测或捕获此异常可能是明智的,并提供更有用的错误消息.

此外,如果要检查没有比关闭括号更多的左括号,请检查循环后堆栈是否为空.