首页 > 试题广场 >

括号匹配深度

[编程题]括号匹配深度

热度指数：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

输入

(())

输出

算法知识视频讲解

Java

比企苦

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.time.YearMonth;
import java.time.format.DateTimeFormatter;
import java.util.*;
import java.io.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer st = new StreamTokenizer(br);

	
	public static void main(String[] args) throws IOException {
		char[] c=br.readLine().toCharArray();
		char[] stack=new char[c.length];
		int flot=0;
		int[] arr=new int[50]; 
		for(int i=0;i<c.length;i++) {
			if(flot==0) {
				stack[flot]=c[i];
				flot++;
			}else {
				if(c[i]==')') {
					arr[flot-1]=Math.max(arr[flot]+1,arr[flot-1]);
					arr[flot]=0;
					flot--;
				}else {
					stack[flot]=c[i];
					flot++;
				}
			}
		}
		System.out.println(arr[flot]);
	}
}

发表于 2026-04-15 16:32:46 回复(0)

Java

kakatalon

搞点走捷径的方法：循环把（）替换为空，记录循环次数即为深度了

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int count = 0;
        while ( s.length()>1 ){
            s = s.replace("()" , "");
            count++;
        }
        System.out.println(count);
    }        
}

发表于 2022-06-08 09:00:18 回复(0)

Java

Leo兵

import java.util.*;

public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int solution = solution(s);
System.out.println(solution);
}

public static int solution(String s) {
int n = s.length();
if (n == 0) {
return 0;
}
Deque<Character> deque = new ArrayDeque<>();
deque.addLast(s.charAt(0));
int i = 1;
int maxSize = 0;
while (i < n) {
char c = s.charAt(i);
if (c == '(') {
deque.addLast(c);
maxSize = Math.max(maxSize, deque.size());
} else if (c == ')') {
deque.pop();
}
i++;
}
return maxSize;
}
}

发表于 2022-05-03 10:38:18 回复(0)

Java

叫我小du

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(getDeep(s));
    }

    public static int getDeep(String s) {
        char[] chs = s.toCharArray();
        int res = Integer.MIN_VALUE;
        int cnt = 0;
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] == '(') {
                cnt++;
            } else {
                cnt--;
            }
            if (cnt < 0) {
                cnt = 0;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }
}

发表于 2021-04-14 16:23:43 回复(0)

Java

牛客196305255号

 public static void solve(String str) {
	int count=0;
	while(!str.isEmpty()) {
	    str=str.replace("()", "");
	    count++;
	}
	System.out.println(count);
}

发表于 2021-01-12 20:02:30 回复(0)

Java

何止hz

import java.util.Scanner;
import java.util.Stack;

/**
 * @Author: coderjjp
 * @Date: 2020-05-15 7:32
 * @Description: 括号匹配深度
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int ans = 0;
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < s.length()){
            if (s.charAt(i) == '('){
                stack.push('(');
                i++;
            }
            else {
                ans = Math.max(ans, stack.size());
                while (i < s.length() && s.charAt(i) == ')'){
                    stack.pop();
                    i++;
                }
            }
        }
        System.out.println(ans);
    }
}

发表于 2020-05-15 08:45:46 回复(0)

Java

_徒然喜欢你_

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.next();
int len = str.length();
int count = 0;
int index = 0;
for(int i = 0; i < len; i++){
if(str.charAt(i) == '('){
count++;
if(count > index){
index = count;
}
}else{
count--;
}
}
System.out.print(index);
}
}

发表于 2019-09-18 20:37:55 回复(0)

Java

Mono_Chrome

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int need = 0;
        int max = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                need++;
                max = max > need ? max : need;
            } else {
                need--;
            }
        }
        System.out.println(max);
    }
}

发表于 2019-06-17 20:05:21 回复(0)

Java

成程晨

栈的思想
import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            System.out.println(helper(in.nextLine()));
        }
    }
    public static int helper(String s){
        if(s.equals("")) return 0;
        char[] cs = s.toCharArray();
        int count = 0,max = 0;
        for(char c:cs){
            if(c == '('){
                count++;
                max = Math.max(max,count);
            }else{
                count--;
            }
        }
        return max;
    }
}

发表于 2019-02-11 19:43:53 回复(1)