【算法题】最大括号深度
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);
}
}正文到此结束
