首页 > 试题广场 >

括号匹配深度

[编程题]括号匹配深度

热度指数：2429 时间限制：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

输入

(())

输出

算法知识视频讲解

Java

默默努力的大鲨鱼

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String str = in.nextLine();

char[] arr = str.toCharArray();

int max = 0;

int temp = 0;

for ( int i = 0; i < arr.length ; i ++) {

if ( '(' == arr[i]) {

temp ++;

} else if ( ')' == arr[i]) {

if ( temp > max) {

max = temp ;

}

temp --;

}

System.out.print(max);

}

发表于 2022-09-27 14:46:31 回复(0)

Java

周星星lm

利用栈进行求解

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String cur = in.next();
        Deque<Character> stack = new ArrayDeque<>();
        int res = 0;
        for(int i = 0;i < cur.length();i++){
            if(cur.charAt(i) == '('){
                stack.add(')');
            }else{
                stack.pop();
            }
            res = Math.max(res,stack.size());
        }
        System.out.println(res);
    }   
}

发表于 2022-07-31 17:56:44 回复(0)

Java

卖女孩的小火柴201905070927943

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
int max = 0;
int count = 0 ;
LinkedList<String> list = new LinkedList();
for(int i = 0;i< str.length(); i++){
String current = str.substring(i,i+1);
String last = list.size()!=0?list.getLast():null;
if(last!=null && current.equals(")")){
count = list.size();
list.pop();
if(list.size()>max){
max = count;
}
}else{
list.push(current);
}

}
System.out.println(max);

}
}

发表于 2021-12-28 19:43:32 回复(0)

Java

又笨又懒不想上课

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine().trim();
        char[] chs = s.toCharArray();
        int res = 1;
        int cur = 0;
        for(int i = 0; i < chs.length - 1; i++) {
            if(chs[i] == '(') ++cur;
            else --cur;
            res = Math.max(res,cur);
        }
        System.out.println(res);
    }
}

发表于 2021-05-26 18:44:34 回复(0)