首页 > 试题广场 >

括号匹配深度

[编程题]括号匹配深度

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

牛客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)

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)