【算法题】最大括号深度

  • A+
所属分类:编程茶楼


共计 1209 个字符,预计需要花费 4 分钟才能阅读完成。

import java.util.Scanner;
import java.util.Stack;
/**
 * 标题:最大括号深度 | 时间限制:1秒 | 内存限制:262144K | 语言限制:不限
 * 现有一字符串仅由 '(',')','{','}','[',']'六种括号组成。
 * 若字符串满足以下条件之一,则为无效字符串:
 * ①任一类型的左右括号数量不相等;
 * ②存在未按正确顺序(先左后右)闭合的括号。
 * 输出括号的最大嵌套深度,若字符串无效则输出0。
 * 0≤字符串长度≤100000
 * 输入描述:
 * 一个只包括 '(',')','{','}','[',']'的字符串
 * 输出描述:
 * 一个整数,最大的括号深度
 * 示例1
 * 输入
 * []
 * 输出
 * 1
 * 说明
 * 有效字符串,最大嵌套深度为1
 * 示例2
 * 输入
 * ([]{()})
 * 输出
 * 3
 * 说明
 * 有效字符串,最大嵌套深度为3
 * 示例3
 * 输入
 * (]
 * 输出
 * 0
 * 说明
 * 无效字符串,有两种类型的左右括号数量不相等
 * 示例4
 * 输入
 * ([)]
 * 输出
 * 0
 * 说明
 * 无效字符串,存在未按正确顺序闭合的括号
 * 示例5
 * 输入
 * )(
 * 输出
 * 0
 * 说明
 * 无效字符串,存在未按正确顺序闭合的括号
 */
public class M_N_T_38 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        char[] chars = line.toCharArray();

        deal(chars);
    }

    private static void deal(char[] chars) {
        Stack<Character> stack = new Stack<>();
        int deep_max = 0;
        for (char aChar : chars) {
            if (aChar == '(' || aChar == '[' || aChar == '{') {
                stack.push(aChar);
                deep_max = Math.max(stack.size(), deep_max);
                continue;
            }

            if (stack.size() == 0) {
                System.out.println(0);
                return;
            }

            Character character = stack.pop();

            if (aChar == ')') {
                if (character == '(') {
                    continue;
                }
                System.out.println(0);
                return;
            }

            if (aChar == ']') {
                if (character == '[') {
                    continue;
                }
                System.out.println(0);
                return;
            }

            if (aChar == '}') {
                if (character == '{') {
                    continue;
                }
                System.out.println(0);
                return;
            }
        }

        System.out.println(stack.size() == 0 ? deep_max : 0);
    }
}
  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的微信公众号
  • 我的微信公众号扫一扫
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: