首页 > 试题广场 >

括号匹配深度

[编程题]括号匹配深度

热度指数：7650 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个合法的括号匹配序列有以下定义:
1、空串""是一个合法的括号匹配序列
2、如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列
3、如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列
4、每个合法的括号序列都可以由以上规则生成。
例如: "","()","()()","((()))"都是合法的括号序列
对于一个合法的括号序列我们又有以下定义它的深度:
1、空串""的深度是0
2、如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y) 3、如果"X"的深度是x,那么字符串"(X)"的深度是x+1
例如: "()()()"的深度是1,"((()))"的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

输入描述:

输入包括一个合法的括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含'('和')'。

输出描述:

输出一个正整数,即这个序列的深度。

示例1

输入

(())

输出

算法知识视频讲解

Python3

TS9527

栈+贪心

class MainActivity:

    def main(self):
        # Read the data
        s = input()
        # Initialization
        stack = []
        result = 0
        # Traverse
        for char in s:
            if stack:
                if char == '(':
                    stack.append('(')
                else:
                    if stack and stack[-1] == '(':
                        stack.pop()
            else:
                stack.append(char)
            result = max(result, len(stack))
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-26 17:50:13 回复(0)

Python3

牛客991380985号

s = input()

# write code here
stack = []
max_num = 0
for i in s:
    if i == "(":
        stack.append(i)
        if len(stack) > max_num:
            max_num = len(stack)
    elif i == ")":
        if stack:
            stack.pop()

print(max_num)

发表于 2023-02-22 14:15:01 回复(0)