【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现

2024-09-07 11:29:40 浏览数 (2)

栈在括号问题中的应用

【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_括号问题【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_括号问题

导读

大家好，很高兴又和大家见面啦！！！

在前面的内容中我们详细介绍了栈与队列的相关知识点，并通过C语言实现栈与队列的基本操作。可是在我们做题时我们会发现我们很难将这些知识点与实际问题联系起来。

为了帮助大家更好的学习和使用栈与队列的相关知识点，从这个篇章开始，我们将介绍它们在实际问题中的几种运用。 在今天的篇章中，我们将来探讨一下栈的第一种应用——括号问题。下面我们一起来了解一下……

一、括号问题

括号问题也就是括号匹配问题，那什么是括号匹配呢？我们可以简单的理解为就是对于圆括号"()"、中括号"[]"和花括号"{}"这三种括号，它们要进行两两匹配的话只能够是'('与')'匹配、'['与']'匹配、'{'与'}'匹配这一种对应的左右括号匹配方式。

现在大家应该了解了什么是括号问题了。那在实际应用中对于这一类问题我们就有可能遇到以下几种应用：

  1. 给定一个存放这三种括号的字符数组，我们需要判断这些括号是否匹配；
  2. 给定一个存放这三种括号的字符数组，我们需要找出距离最长的有效括号；
  3. 给定一个存放这三种括号的字符数组，我们需要找出长度最长的有效括号；

如果大家有刷leetcode题库中的题目的话这两道题应该不会陌生，它们对应的就是leetcode题库中的下面两道题：

【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_数据结构_02【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_数据结构_02

还没有做过的朋友或者说是没有思路的朋友下面我们一起在探讨的过程中顺便来解决一下这两道题。

对于这类问题我们应该如何来解决呢？下面我们就一起来探讨一下对应的算法思路；

二、算法思路

当我们在拿到一道括号问题时，我们可能会遇到各种各样的字符串，如："()[]{}"、"(([{}]))"、"((}))"、"(([{}])){"……这些不同的括号字符串，这时如果我们想要对其进行匹配的话最简单的思路就是从左往右依次进行扫描，在依次扫描的过程中我们需要进行以下操作：

  1. 判断是否为括号——是括号说明未被扫描完，是''说明已经被扫描完；
  2. 判断括号的方向——是左括号还是右括号？
  3. 记录括号并匹配——确保每一个左括号都能与右括号进行匹配，每一个右括号都能与左括号进行匹配

2.1 基本操作的实现

这三件事情单独拎出来都是很好实现的，比如判断是否为括号，如果我们用C语言来表示的话那就可以进行如下表示：

代码语言：javascript复制
//扫描并判断是否为括号
void test1() {
	char ch[11] = "()[]{}";
	int i = 0;//数组下标
	while (ch[i])//判断元素是否为括号
	{
		i  ;//如果元素为括号则往后继续进行扫描
	}
}

这个代码想必大家都不陌生了，这里我也就不过多赘述了。下面如果我们要判断括号的方向，那我们则可以用C语言进行如下表示：

代码语言：javascript复制
//判断括号的方向
void test2() {
	char ch[11] = "(([{}]))";
	int i = 0;//数组下标
	while (scanf("%d", &i) == 1) //通过多组输入来进行对应下标元素的判断
	{
		if (i > strlen(ch) || i < 0)//对输入下标的合理性进行判断
			return;
		//输入下标合理则进行括号开口方向的判断
		if (ch[i] == '(' || ch[i] == '[' || ch[i] == '{')
			printf("%c该括号为左括号n", ch[i]);
		else
			printf("%c该括号为右括号n", ch[i]);
	}
}

这里我例举的是单一的判断数组中的某一个元素，如果我们要想判断数组中的每一个元素，那我们可以通过输入或者说是遍历的方式来实现，这里我就不过多赘述了。

最后一个问题我们要记录对应的括号并匹配的话，我们可以通过不用的数组来依次实现。那首先我们就需要知道如果要在数组中要进行两两配对的话那么左括号的数组下标就是0、2、4、6……这些偶数下标，对应的右括号的下标那就是1、3、5、7……这些奇数下标，因此我们就可以通过下标的奇偶来进行括号的记录与匹配，如下所示：

代码语言：javascript复制
//记录每一个括号
void test3() {
	char ch[11] = "(([]({)}))";
	int i = 0;//给定的字符数组下标
	char bracket1[11] = { 0 };//记录圆括号/小括号()
	char bracket2[11] = { 0 };//记录方括号/中括号[]
	char bracket3[11] = { 0 };//记录花括号/大括号{}
	int sl = 0, ml = 0, ll = 0;//左括号下标
	int sr = 1, mr = 1, lr = 1;//右括号下标
	while (scanf("%d", &i) == 1) {
		if (i > strlen(ch) || i < 0)//判断下标的合理性
			return;
		switch (ch[i]) {
		case '(':
			bracket1[sl] = ch[i];//记录左圆括号
			sl  = 2;
			break;
		case ')':
			bracket1[sr] = ch[i];//记录右圆括号
			sr  = 2;
			break;
		case '[':
			bracket2[ml] = ch[i];//记录左方括号
			ml  = 2;
			break;
		case ']':
			bracket2[mr] = ch[i];//记录右方括号
			mr  = 2;
			break;
		case '{':
			bracket3[ll] = ch[i];//记录左花括号
			ll  = 2;
			break;
		case '}':
			bracket3[lr] = ch[i];//记录右花括号
			lr  = 2;
			break;
		default:
			break;
		}
	}
}

对于这个问题的实现，我是借助了三个与题目给定的字符数组大小一致的字符数组以及数组对应的左右下标来进行记录，这样我们在经过一次扫描之后就能保证每一个左括号的右边都是一个有括号，每一个每一个右括号的左边都是一个左括号。如果出现左括号的右边没有元素或者右括号的左边没有元素，那么就说明没有与之相对应的括号。

对于上述三个功能的实现如果还有问题的朋友可以回顾一下C语言分支与循环、数组的相关知识点。

那如果我们要将这三个功能合并的话也是很简单的，这里我们就需要知道，我们在进行记录并匹配时实际上就已经完成了判断的功能，那么我们只需要将手动输入替换成遍历就可以，如下所示：

代码语言：javascript复制
//依次遍历、判断并记录括号
void test4() {
	char ch[11] = "(([]({)}))";
	int i = 0;//给定的字符数组下标
	char bracket1[11] = { 0 };//记录圆括号/小括号()
	char bracket2[11] = { 0 };//记录方括号/中括号[]
	char bracket3[11] = { 0 };//记录花括号/大括号{}
	int sl = 0, ml = 0, ll = 0;//左括号下标
	int sr = 1, mr = 1, lr = 1;//右括号下标
	while (ch[i]) //判断元素是否为括号
	{
		switch (ch[i]) {
		case '(':
			bracket1[sl] = ch[i];//记录左圆括号
			sl  = 2;
			break;
		case ')':
			bracket1[sr] = ch[i];//记录右圆括号
			sr  = 2;
			break;
		case '[':
			bracket2[ml] = ch[i];//记录左方括号
			ml  = 2;
			break;
		case ']':
			bracket2[mr] = ch[i];//记录右方括号
			mr  = 2;
			break;
		case '{':
			bracket3[ll] = ch[i];//记录左花括号
			ll  = 2;
			break;
		case '}':
			bracket3[lr] = ch[i];//记录右花括号
			lr  = 2;
			break;
		default:
			break;
		}
		i  ;//往后遍历
	}
}

这种实现方式已经满足了我们判断括号的最低需求，但是肯定不是最合理的方式，那我们需要在此基础上做哪些改进呢？下面我们来依次分析；

2.2 问题分析

对于一个算法的好坏在绪论中我们已经介绍过了，不知道大家还有没有影响，下面我们一起来复习一下：对于一个好的算法来说我们需要具备以下几种特性：

  1. 正确性
  2. 可读性
  3. 健壮性
  4. 高效率和低存储需求

对于最后这段代码，我们从这几个方面来依次进行分析。下面我们来测试一下最后的这段代码：

【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_栈_03【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_栈_03

可以看到程序能够正常运行，这就说明这个代码是正确的，代码中的每一句代码都并不复杂，因此代码的可读性也是很高的，对于不符合要求的下标，我们通过while语句的判断条件以及Switch语句的default语句可以将其很好的进行筛选，因此这段代码的健壮性也是没问题的。

下面我们就来分析一下这段代码的时间复杂度与空间复杂度：

  • 在这段代码中，涉及到一次循环，如果字符串的长度为n那么循环的内的语句的执行次数就为n因此这段代码的时间复杂度为O(N);
  • 这段代码中，我们可以抛开原数组所占空间大小，只看我们后续申请的空间大小。对于一个长度为n的字符串而言，在这段代码中我们申请了3n的空间，这里涉及到7个整型变量，因此我们为了解决这个问题实际上花费了3n 28的内存空间，对应的空间复杂度则为O(3N 28)；

PS：为了更好的说明，这里我们对于空间复杂度就不进行简化了。

当我们在实际的使用中其实只花费了N 28的空间大小，如果考虑极端情况，原数组中只含一种括号的话，那我们实际上花费的也只有N 8的空间大小，多出来的2N 20都是被我们给浪费的空间，因此在这个算法中，它并不满足低存储需求这个要求。所以我们接下来就需要在这个方面来进行改进。

2.3 问题改进

在前面的实现过程中，我们在判断时实际上是将数组中的元素分成了6类进行判断——左/右括号以及圆/方/花括号。这样就导致了我们花费了更多的空间来完成，为了花费更少的空间，我们可不可以用一个数组就来完成这些操作呢？为了解决这个问题，我们需要换一种思路来思考。我们将判断与匹配分开进行，判断时我们只判断左右括号，匹配时我们才进行不同类型括号的匹配，也就是说，我们可以按照下面的思路来进行：

  1. 当元素为左括号/右括号时进行记录；
  2. 当元素为右括号/左括号时进行匹配；

单看文字可能无法直观的理解，下面我们来看图：

【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_数据结构_04【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_数据结构_04

在这个过程中我们会发现，我们在判断的过程中实际上就只是判断数组下标最大的那个元素。此时可能有朋友会说，如果题目给的括号是相反的比如题目给我们的字符串为")("那我们又应该如何处理呢？回答这个问题之前，我们先来回顾一下ASCII码表：

【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_C语言_05【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_C语言_05

从表中我们可以看到，对于这三种括号来说左括号的ASCII码值是小于右括号的ASCII码值的，因此我们在解决括号问题时是可以选择进行排序的方式来处理这种问题，将给定的字符数组中的元素按照由小到大的顺序进行排序，这样就能保证我们先扫描的是左括号了。

当然也有其它的解决方式，比如遇到右括号就记录，遇到左括号就匹配，或者从右往左进行扫描等等对于这种左右颠倒的字符串我们解决的方式有很多，这里就不展开介绍了。

PS: 目前我自己在学习的过程中还没有遇到这种问题，正常都是以左括号开头然后进行匹配，所以大家也不用过度去深究，真正等到遇到的时候，我还是建议大家以排序的方式来解决。排序的方式可以适用于给定的所有例子，至于最终大家选择怎么处理那就是智者见智仁者见仁了。

不知道大家有没有注意到，我们通过上面介绍的这种解题方式，我们会发现，后记录的括号会优先被匹配，或者我们可以将这种操作特性称为后人先出（LIFO）。

看到这个操作特性大家应该就比较熟悉了，这个就是栈的操作特性，因此在括号匹配问题中我们常见的解题方式就是用栈来解决。

在确定了解题的数据结构，下面我们就要思考算法的具体流程，并设计对应的算法了。

2.4 算法设计

想要设计这个算法，那我们就需要先考虑在具体的实现过程中可能会出现的一些问题：

  1. 当遇到右括号时栈中没有元素应该如何处理？
  2. 当遇到右括号时栈顶元素不匹配应该如何处理？
  3. 当遇到右括号全部匹配玩栈中还有多余的左括号应该如何处理？
  4. 当元素过多时出现满栈了应该怎么处理？

对于前面两个问题，正如我之前所说，我们现在遇到的题目正常都是从左括号开始，因此当遇到右括号出现空栈或者栈顶元素不匹配的情况，那就只有一种可能——该右括号没有与之匹配的左括号。

对于第三个问题，那就说明题目给定的字符串中存在没有与左括号与之匹配的右括号。

因此如果我们遇到的题目是判断给定的字符串是否都为有效括号时，我们可以直接通过返回false来表示该字符串中的元素并不是都为有效括号。如果我们遇到的题目是寻找有效括号的个数时，那对于这种不能被匹配的单括号我们可以直接采取删除的方式将这些单括号给排除掉。

对于第四个问题，我们就要回顾一下顺序栈和链栈的区别，对于顺序栈来说，它是会存在满栈的情况，而对于链栈来说，并不存在满栈的情况，理论上只要内存空间足够大，那么我就能一直入栈新的元素。因此，在数据比较庞大的情况下，我们优先选用的是链栈的方式来解决。

搞清楚了以上问题，那么我们就可以设计出该算法的具体流程了，如下所示：

【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_C语言_06【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_C语言_06

从流程图中我们可以看到，在我们要实现的算法中，有三种情况会导致匹配失败：

  1. 所有元素遍历完，还存在未匹配的左括号；
  2. 所有入栈的左括号匹配完，还存在需要匹配的右括号；
  3. 栈顶的左括号与需要匹配的右括号不匹配；

整个算法中，只有一种情况是匹配成功的：

  • 所有的元素遍历完，栈中的所有左括号全部匹配完。

有了具体的操作流程，接下来我们就可以来通过C语言实现这个算法了。

三、算法实现

本次实现的算法中，我们需要涉及到的栈的基本操作有：

  1. 栈的创建与销毁；
  2. 元素的入栈与出栈；
  3. 栈的判空；
  4. 栈顶元素的获取；

这些基本操作的C语言实现在前面的篇章中有详细的介绍，这里我就不多加赘述了，下面我们要重点介绍的是整个算法的实现。为了避免栈溢出的问题，这里我采取链栈的方式来实现，如下所示：

代码语言：javascript复制
//括号匹配问题——栈的应用
bool isVaid(char* s) {
	assert(s);
	Stack* S;//创建链栈——头指针
	InitStack(&S);//链栈的初始化——无头结点的初始化，即S = NULL；
	for (int i = 0; s[i]; i  ) {
		if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
			if (Push(&S, s[i]))//遇到左括号，进行入栈操作
				printf("%c已入栈n", s[i]);
		}
		else {
			Elemtype x = 0;
			GetTop(S, &x);
			if ((s[i] == ')' && x == '(') || (s[i] == ']' && x == '[') || (s[i] == '}' && x == '{')) {
				if (Pop(&S, &x))
					printf("%c匹配成功，已出栈n", x);
			}
			else {
				printf("栈中没有与%c匹配的括号n", s[i]);//栈顶
				return false;
			}
		}
	}
	if (Empty(S))
		return true;
	printf("栈中没有与%c匹配的括号n", S->data);
	return false;
}

下面我们来以前面提到的例子"()[]{}"、"(([{}]))"、"(([]({)}))"、"(([{}])){"来测试一下这个算法，结果如下所示：

【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_数据结构_07【数据结构】如何解决括号问题？详谈括号问题的算法思想与代码实现_数据结构_07

可以看到此时我们算法的运行是没有问题的，也就是说它满足正确性、可读性与健壮性，接下来我们只需要分析该算法所需的时间与消耗的空间即可。

在这个算法中由于我们采取的是链栈，因此算法所需的空间与给定的字符串的长度有关；在这个算法中，我们采取的是当遇到不匹配的情况时直接结束算法，因此，算法所需的时间也与给定的字符串的内容有关；

在这个算法中，会出现三种情况：

  1. 当给定的字符串第一个字符就不匹配时，此时算法会消耗一个临时的空间用来对算法的情况进行反馈，空间大小为字符类型的大小，基本上可以忽略不计；当字符串第一个元素就不匹配时，此时算法是直接进行终止的，因此对应的时间复杂度为O(1)；
  2. 当给定的字符串在中间出现不匹配时，此时算法消耗的额外空间与还未匹配的括号个数有关，这里我们考虑极端情况，前面的M个元素都为进行匹配，此时的

，对应的空间复杂度估算为O(M)；在这种情况下，所需的时间复杂度同样为O(M)；

  1. 当给定的字符串在最后才出现不匹配时，此时我们完成了整个字符串的遍历，消耗的时间复杂度为O(N)，对于空间复杂度，我们还是考虑极端情况，没有右括号与左括号匹配，因此消耗的空间复杂度为O(N)；

综上所述，该算法在最坏的情况下所需的时间复杂度和空间复杂度都为O(N)，正常情况下的时间复杂度与空间复杂度都是不超过O(N)的，相比于刚开始通过三个数组来解决匹配问题的算法，在空间上有极大的提升，在时间上也有略微的改善。

结语

在今天的内容中，我们详细介绍了栈在括号匹配问题中的应用以及C语言的算法实现。对于括号匹配问题使用栈来解题的整体思路如下所示：

  1. 第一步：栈类型的选择——对于体量合适的问题，我们可以选用顺序栈来解题，对于体量庞大的问题我们则选用链栈来解题；
  2. 第二步：从左到右遍历给定的括号字符串；
  3. 第三步：判断遍历的对象是否为括号——为括号则继续后续内容，非括号则停止遍历；
  4. 第四步：判断遍历的对象的括号类型——左括号则进行入栈操作，右括号则进行出栈操作；
  5. 第五步：当遇到右括号时需要进行栈的判空操作——检测该右括号是否有与之匹配的括号；
  6. 第六步：当栈非空时，需要获取栈顶元素与右括号进行匹配——匹配成功继续向后遍历，匹配失败则说明该右括号没有与之匹配的左括号；
  7. 第七步：当完成遍历后需要对栈进行判空——栈非空则说明字符串中存在没有匹配对象的左括号，反之，则说明该字符串中的元素都为有效括号；

以上解题思路为最基础的括号问题的解题思路，希望对各位在使用栈来解题时有帮助，在后续的篇章中我会再通过习题来进一步介绍栈在括号问题中的应用，大家记得关注哦！

最后感谢各位对博主内容的支持，希望博主的内容能够在学习上帮助到大家，各位如果有遇到相关内容的问题可以评论或是私信博主，我看到后会耐心给各位解答哦！

咱们今天的内容到这里就结束了，期待在下一篇内容中与你相见！！！

算法 字符串 数据结构 遍历 数组

0 人点赞