城市建设和房屋管理部门网站网站模板切换
题目描述
现有一字符串仅由"("，")", "{","}", "[", "]"六种括号组成。若字符串满足以下条件之一，
则为无效字符串:任一类型的左右括号数量不相等
存在未按正确顺序(先左后右)闭合的括号输出括号的最大嵌套深度，若字符串无效则输出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;
}