首页 > 试题广场 >

括号匹配深度

[编程题]括号匹配深度

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

知行90

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int dep = 0;
        //表示栈深度的变换
        int size = 0;
        if(scanner.hasNext()){
           String s = scanner.nextLine();
           for(int i  = 0; i < s.length();i++){
               char c = s.charAt(i);
               if(c == '('){
                   size++;
                   dep =  Math.max(dep,size);
               }else if(c == ')'){
                   size--;
               }
           }
        }
        System.out.println(dep);
    }
}

发表于 2023-02-03 07:46:49 回复(0)

哒哒嘀嘀

Java 巧用栈

39ms、10792kb

import java.util.Scanner;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(new InputStreamReader(System.in));
        int Dep = 0;
        if (scanner.hasNext()){
            char[] input = scanner.next().toCharArray();
            Stack stack = new Stack();
            int tmpDep = 0;
            for(char c : input){
                if (c == '('){
                    stack.push(c);
                    tmpDep ++;
                }
                if (c == ')'){
                    stack.pop();
                    Dep = Math.max(Dep, tmpDep);
                    tmpDep --;
                }
            }
        }
        System.out.println(Dep);
    }
}

发表于 2022-06-08 19:06:26 回复(0)