12. 最大括号深度

题目描述

现有一字符串仅由"("，")", "{","}", "[", "]"六种括号组成。若字符串满足以下条件之一，

则为无效字符串:任一类型的左右括号数量不相等

存在未按正确顺序(先左后右)闭合的括号输出括号的最大嵌套深度，若字符串无效则输出0。

0<=字符串长度<=100000

输入描述

一个只包括(，’)’，’{‘，”}”，[，”]”的字符串

输出描述

整数，最大的括号深度

用例

一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.一个合法的括号匹配序列有以下定义：

（1）空串“”是一个合法的括号匹配序列

（2）如果“X”和“Y”都是合法的括号匹配序列，“XY”也是一个合法的括号匹配序列

（3）如果“X”是一个合法的括号匹配序列，那么“（X）”也是一个合法的括号匹配序列

（4）每个合法的括号序列都可以由以上规则生成。

2.对于一个合法的括号序列我们又有以下定义它的深度：

（1）空串“”的深度为0

（2）如果字符串“X”的深度是x，字符串“Y”的深度是y，那么字符串“XY”的深度为max（X，Y）

（3）如果“X”的深度是x，那么字符串“（X）”的深度是x+1

3.输入描述：输入包括一个合法的括号序列s，s长度length大于等于2小于等于50，序列中只包含括号（有两道题，一道题是只包括小括号，还有一道题是包括小括号中括号和大括号）

4.输出描述：输出一个正整数，即这个序列的深度

二、解题思路

1.先说只有小括号的情况（一定是合法的）

2.如果只有小括号（且输入合法），我们需要判断深度的话

3.定义一个整数int depth = 0;用来代表深度，定义一个整数int maxdepth = 0;

4.如果遇到左括号，depth增加1，然后如果depth大于maxdepth，maxdepth更新值

5.如果遇到右括号，depth减少1，

6.最后输出maxdepth就是最大深度了

#include <stdio.h>
#include <string.h>
int main() {char str[1000];scanf("%s", str);int depth = 0;int maxdepth = 0;int len = strlen(str);for(int i = 0; i < len; i++) {if(str[i] == '(') {depth++;} else if(str[i] == ')') {depth--;}if(depth > maxdepth) maxdepth++;}printf("%d\n", maxdepth);return 0;
}

1.然后再说有方括号大括号和括号三种括号的情况（并且有可能输入不合法）

2.如果输入不合法（比如左右括号不对称、未按正确顺序闭合）那么输出0

3.我们可以定义一个字符串数组char left[1000];用来记录遇到的括号

4.它的索引值为int idx = 0;我们遍历字符串char str[1000];，每遇到一个左括号，我们将这种类型的左括号放到栈顶，然后idx++

5.我们还需要在前面定义一个int maxdepth = 0;如果遇到的是左括号idx++之后，

6.比较idx和maxdepth的值，如果idx比较大，maxdepth更新值

7.如果我们遇到的是右括号，我们与左括号作比较，如果是同一类型的，那么我们idx--

8.如果是不同类型的，我们认为输入不合法，我们需要在前面定义一个bool valid = true；

9.如果遇到输入不合法的情况，那么我们valid = false；并且break；出循环

10.遍历完字符串以后,如果idx ！= 0；那么我们认为不合法valid = false;

11.最后，如果不合法，我们输出0，否则的话我们输出maxdepth的值

12.然后返回return 0；

三、具体步骤

使用的语言是C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
int main() {char str[1000];scanf("%s", str);char left[1000];int idx = 0;int maxdepth = 0;int len = strlen(str);bool valid = true;for (int i = 0; i < len; i++) {// printf("test i = %d\n", i);if (str[i] == '(' || str[i] == '[' || str[i] == '{') {// printf("遇到左括号\n");left[idx++] = str[i];if (idx > maxdepth) maxdepth = idx;// printf("idx = %d\n", idx);// printf("maxdepth = %d\n", maxdepth);} else if (str[i] == ')') {// printf("遇到)括号\n");if (left[idx - 1] == '(') idx--;else valid = false;} else if (str[i] == ']') {// printf("遇到]括号\n");if (left[idx - 1] == '[') idx--;else valid = false;} else if (str[i] == '}') {// printf("遇到}括号\n");if (left[idx - 1] == '{') idx--;else valid = false;} else {valid = false;}if (valid == false) break;}if (idx != 0) valid = false;if (valid) printf("%d\n", maxdepth);else printf("0\n");return 0;
}