网站模板切换,WordPress页面加分类文章,网站建设的潜在客户,家用宽带怎么做网站 访问题目描述 现有一字符串仅由(#xff0c;), {,}, [, ]六种括号组成。若字符串满足以下条件之一#xff0c; 则为无效字符串:任一类型的左右括号数量不相等 存在未按正确顺序(先左后右)闭合的括号输出… 题目描述 现有一字符串仅由(), {,}, [, ]六种括号组成。若字符串满足以下条件之一 则为无效字符串:任一类型的左右括号数量不相等 存在未按正确顺序(先左后右)闭合的括号输出括号的最大嵌套深度若字符串无效则输出0。 0字符串长度100000 输入描述 一个只包括(’)’’{‘”}”[”]”的字符串 输出描述 整数最大的括号深度 用例 一、问题分析
首先读题仔细看描述中的内容发现需求是
1.一个合法的括号匹配序列有以下定义
1空串“”是一个合法的括号匹配序列
2如果“X”和“Y”都是合法的括号匹配序列“XY”也是一个合法的括号匹配序列
3如果“X”是一个合法的括号匹配序列那么“X”也是一个合法的括号匹配序列
4每个合法的括号序列都可以由以上规则生成。
2.对于一个合法的括号序列我们又有以下定义它的深度
1空串“”的深度为0
2如果字符串“X”的深度是x字符串“Y”的深度是y那么字符串“XY”的深度为maxXY
3如果“X”的深度是x那么字符串“X”的深度是x1
3.输入描述输入包括一个合法的括号序列ss长度length大于等于2小于等于50序列中只包含括号有两道题一道题是只包括小括号还有一道题是包括小括号中括号和大括号
4.输出描述输出一个正整数即这个序列的深度
二、解题思路
1.先说只有小括号的情况一定是合法的
2.如果只有小括号且输入合法我们需要判断深度的话
3.定义一个整数int depth 0;用来代表深度定义一个整数int maxdepth 0;
4.如果遇到左括号depth增加1然后如果depth大于maxdepthmaxdepth更新值
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;
}
