首页 > 试题广场 >

括号匹配深度

[编程题]括号匹配深度

热度指数：763 时间限制：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.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    int cnt = 0, max = 0, i;
    for (i=0; i<s.length(); ++i) {
      if (s.charAt(i) == '(')
        cnt++;
      else
        cnt--;
      max = Math.max(max, cnt);
    }
    System.out.println(max);
  }
}

发表于 2018-03-17 22:35:53 回复(0)

你家昊爷plus

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

public class Main {

    public static void main(String[] args) {
        Stack<Character> stack = new Stack<>();
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
        int deep = 0;
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == '(') {
                stack.push(str.charAt(i));
            }else if(str.charAt(i) == ')') {
                if(deep < stack.size()) {
                    deep = stack.size();
                }
                stack.pop();
            }
        }
        System.out.println(deep);
        scan.close();
    }

}

发表于 2018-09-12 21:43:08 回复(0)

Java

牛客359854864号

import java.util.LinkedList;
import java.util.Scanner;

//[()({}{})]
public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] chars = in.nextLine().toCharArray();
        LinkedList<Character> stack = new LinkedList<>();
        int max = 0;
        for (char c : chars) {
            if (c == ']' || c == '}' || c == ')') {
                if ((c == ']' && stack.peek() == '[') || (c == '}' && stack.peek() == '{') || (c == ')' && stack.peek() == '(')) {
                    max = (max > stack.size()) ? max : stack.size();
                    stack.pop();
                }
            } else {
                stack.push(c);
            }
        }
        if (!stack.isEmpty()) {
            System.out.println(0);
        } else {
            System.out.println(max);
        }
        in.close();
    }
}

我的思路是在遇到右括号时统计栈内有多少左括号，有几个就是几层深度，最后判断栈是否空了，没空就是错误字符串，代码粗糙，有错望指教（轻喷）

发表于 2022-10-01 17:23:35 回复(0)

牛客128414416号

#include<stdio.h>
#include<string.h>
int main(){
char s[50];
int i,j,k,len,len2,count=0;
while(scanf("%s",&s)!=EOF){
len=strlen(s);
if(len==0){
break;
printf("0\n");
}
if(len!=0){
for(i=0,j=len-1;i<=(len/2)&&j>=(len/2);i++,j--){
if(s[i]=='('||s[j]==')'){
count=count+1;

}else if(s[i]==')'||s[j]=='('){
count=count-1;
}else
break;
}
if(count==0){
count=1;
printf("%d\n",count);
}else
printf("%d\n",count);
}
}
return 0;
}

发表于 2022-06-12 13:00:16 回复(0)

拼命也要幸福

遇到（加1 遇到)减一因为（）（）（）是同一级

发表于 2019-07-20 13:19:07 回复(0)

hsp619

import java.util.Scanner;

public class test1 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        int result=0,index=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                index++;
                result=Math.max(index, result);
            }else{
                index--;
            }
        }
        System.out.println(result);
    }
}

发表于 2019-03-16 15:16:45 回复(0)

xsongj


	import java.util.Scanner;



	import java.util.Stack;



	



	



	public class Main {



	



	    public static void main(String[] args) {



	



	        Scanner in = new Scanner(System.in);



	        String s = in.nextLine();



	        char[] chs = s.toCharArray();



	        Stack<Character> stack = newStack<>();



	        int maxDp = 0;



	        for(char ch : chs) {



	            if(ch == '(') {



	                stack.push(ch);



	            } else if(ch == ')') {



	                stack.pop();



	            }



	            if(maxDp < stack.size()) {



	                maxDp = stack.size();



	            }



	        }



	        System.out.println(maxDp);



	    }



	}

编辑于 2018-09-05 22:22:45 回复(0)

xllg

  import java.util.*; 
  public class Main { 
      public static void main(String args[]){ 
          Scanner ss=new Scanner(System.in); 
          String s=ss.nextLine(); 
            
          int lnum=0,rnum=0; 
          int max=0; 
          for(int i=0;i<s.length();i++){ 
              if(s.charAt(i)=='('){ 
                  lnum++; 
              }else{ 
                  rnum++; 
              } 
              if(lnum-rnum>max){ 
                  max=lnum-rnum; 
              } 
          } 
          System.out.print(max); 
      } 
  } 

发表于 2018-01-20 11:30:38 回复(0)

愫憭訫

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        char[] chs = s.toCharArray();
        int deepest = getDeepest(chs);
        System.out.println(deepest);
    }

    /**
     * 解题思路：用一个字符数组存放输入的序列，遍历数组，用一个变量来记录，当遇到左括号就+1，遇到右括号就-1，变量的最大值就是这个序列的深度
     */
    public static int getDeepest(char[] chs) {

        int count = 0;
        int deepest = 0;
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] == '(') {
                count++;
                if (count > deepest) {
                    deepest = count;
                }
            }
            if (chs[i] == ')') {
                count--;
            }
        }

        return deepest;
    }

}

发表于 2017-12-26 12:39:19 回复(0)