【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！

栈在括号问题中的应用

【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！_括号匹配问题

导言

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

在前面的内容中，我们详细介绍了栈在括号问题中的应用，相信大家看完后对括号问题的解题思路有了更加清晰的认识了。俗话说的好，磨刀不误砍柴工。在今天的内容中，我们就来通过几道习题来加深栈在括号问题中应用吧。

一、有效的括号——栈、字符串——简单

首先我们来看第一题，这一题是leetcode网中的一道题，原题链接在此奉上：20. 有效的括号。

1.1 题目要求与分析

接下来我们来看一下题目的要求，题目要求如下所示：

【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！_栈_02

在这一题中，我们可以看到，它是一道最基本的括号匹配问题，由题目提示条件可知，本题中字符串的最大长度为10000，这个体量不算大，所以在这一题中我们既可以选用顺序栈来解题，也可以选用链栈来解题。

在这一题中，我会给大家介绍如何通过对数组进行相关操作来模拟实现栈，因此对于这一题的解题过程我采用的是顺序栈来进行解题。

既然我们现在时通过数组来模拟实现顺序栈，那么我们就需要能够创建一个存储数据的数组，以及指向栈顶的指针，即数组下标，如下所示：

代码语言：javascript复制

#define MAXSIZE 10000
bool isValid(char* s) {
	char S[MAXSIZE] = { 0 };//数据域
	int i = 0;//栈顶指针
}

接下来按照括号问题的解题思路，我们在这一题中需要完成的内容有：

1. 遍历原字符串；
2. 找到左括号进行入栈；
3. 对栈进行判空；
4. 获取栈顶元素；
5. 找到右括号进行匹配；

1.2 代码实现

接下来我们就按照上面的思路来一步一步的来实现对应的操作。首先是遍历原字符串，这里我们还是以for循环来进行遍历，如下所示：

代码语言：javascript复制

for (int j = 0; s[j]; j  ) //遍历原字符串
	{

	}

这里我们通过for循环实现了两个内容——判断当前的元素以及遍历字符串。

• 在for循环的判断条件中，当我们遍历的元素为括号时，此时对应的值为一个非零的值，我们可以顺利进入循环；当我们遍历的元素为''时，其对应的ASCII码值为0，我们就会结束循环；
• 在C语言的数组与指针篇章中我们有介绍过，数组名与指针变量是可以等价的，因此此时的指针变量s就等价与一个字符数组，我们可以通过数组下标来访问数组中对应的元素，所以这里我们通过下标j来完成对数组元素的遍历；

接下来我们就需要完成第二个内容——找到左括号进行入栈，这里的入栈也就是给数组进行赋值操作，如下所示：

代码语言：javascript复制

if (s[j] == '(' || s[j] == '[' || s[j] == '{') {
			S[i  ] = s[j];//遇到左括号时进行入栈
		}

这里需要注意的是我们的栈顶指针i指向的是栈顶元素的下一块区域，因此我们的操作步骤应该是先入栈再移动栈顶指针。C语言提供的后置 这个操作符刚好符合这个操作特性——先使用再 ，所以这里我们可以简写为上述的形式。

在实现这个内容时，我们需要判断的条件就是两个——遍历的对象为左括号或者遍历的对象为右括号。当我们遍历的对象为右括号时，我们需要先对栈进行判空，如果栈为空，则说明该右括号没有与其相匹配的左括号，根据题目要求，我们可以直接返回false，如下所示：

代码语言：javascript复制

else {
			if (i == 0)//当栈顶指针为0时，说明此时的栈为空栈
				return false;//栈为空栈，并且遍历的元素为右括号，那说明没有与之对应的左括号
		}

当栈不为空时，我们就需要获取栈顶元素并与当前遍历的元素进行匹配。这时又有两种情况——匹配成功以及匹配不成功。

• 当匹配成功时，我们需要执行出栈操作。由于栈顶指针指向的是栈顶元素的下一块区域，因此我们需要先移动栈顶指针，再进行出栈。C语言提供的前置--操作符刚好满足这一特性，所以我们同样可以进行简写；
• 当匹配不成功时，说明此时的右括号没有与之对应的左括号，根据题目要求，我们可以直接返回false；

因此我们在实现这两种情况时可以编写如下代码：

代码语言：javascript复制

else {
				char x = S[i - 1];//获取栈顶元素，这里可要可不要
				if ((s[j] == ')' && x == '(') || (s[j] == ']' && x == '[') || (s[j] == '}' && x == '{'))
					S[--i] = 0;//进行出栈操作，先移动栈顶指针，再进行元素出栈
				else {
					return false;//当栈顶元素与遍历对象不匹配时，说明没有与之对应的左括号
				}
			}

当所有元素都遍历完时，此时数组下标指向的元素为''，这种情况下程序是不能继续进入循环的。在结束循环后，我们就需要对栈进行判空，这时也会有两种情况：

• 栈为空的话则表示所有的元素都匹配成功，即该字符串中的元素为有效括号，根据题目要求，我们可以返回true；
• 栈不为空的话则表示存在未匹配的左括号，根据题目要求，我们需要返回false；

对应的代码如下所示：

代码语言：javascript复制

if (i == 0)
		return true;
	return false;

现在我们就完成了所有的内容，下面我们来看一下整体的代码：

代码语言：javascript复制

#define MAXSIZE 10000
bool isValid(char* s) {
	char S[MAXSIZE] = { 0 };//数据域
	int i = 0;//栈顶指针
	for (int j = 0; s[j]; j  ) //遍历原字符串
	{
		if (s[j] == '(' || s[j] == '[' || s[j] == '{') {
			S[i  ] = s[j];//遇到左括号时进行入栈
		}
		else {
			if (i == 0)//当栈顶指针为0时，说明此时的栈为空栈
				return false;//栈为空栈，并且遍历的元素为右括号，那说明没有与之对应的左括号
			else {
				char x = S[i - 1];//获取栈顶元素，这里可要可不要
				if ((s[j] == ')' && x == '(') || (s[j] == ']' && x == '[') || (s[j] == '}' && x == '{'))
					S[--i] = 0;//进行出栈操作，先移动栈顶指针，再进行元素出栈
				else {
					return false;//当栈顶元素与遍历对象不匹配时，说明没有与之对应的左括号
				}
			}
		}
	}
	if (i == 0)
		return true;
	return false;
}

我们在力扣上就可以直接提交了，结果如下所示：

【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！_栈_03

从提交结果中可以看到，我们通过数组模拟实现顺序栈成功解决了这一题。当然这一题我们也可以通过链栈来解题，大家感兴趣的话可以自行尝试一下；

二、最长有效括号——栈、字符串、动态规划——困难

我们接着看第二题，这一题同样是leetcode网中的题目，原题链接在此奉上：32. 最长有效括号。

2.1 题目要求与分析

在做解答这道题之前，我们还是需要先来看一下题目对应的要求，并对题目进行分析，题目要求如下所示：

【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！_字符串_04

不知道大家看到这个题目是何感受，我在初次看到这个题目，感觉有点脑壳疼，这题目要求说的啥呀！！！怎么又是有效括号又是子串的，二期还要最长这些都是啥呀！！！

其实冷静下来分析一下，这一题相比于上一题，它无非就是一道多个知识点的综合题。 对于有效括号以及对应的解题思路我们我们在上一个篇章中已经详细介绍过了，这里就不加赘述了。 现在唯一的疑问就是子串，这个知识点是字符串的相关内容，在后面的篇章中我们会再详细介绍。这里我举一个简单的例子来介绍一下什么是子串：

对于字符串"aabaacabc"来说，字符串"aab"字符串"aac"字符串"aba"等等这些在原字符串中包含的字符串就被称为该字符串的子串； 当然对于字符串"aaaa"来说，它就不是原字符串的子串。

因此子串我们可以理解为，是在原字符串中能够找到的字符串，子字符串中的元素在原字符串中一定是相邻的。

现在我们对题目的要求有了一个大致的了解，这一题实际上就是考察的有效括号和字符串两个知识点。如果将这二者一起解决感觉还是有些困难的，为了简化问题，现在我们就来对问题进行一下拆解，将其拆分为下面几个小问题：

1. 如何计算有效括号的个数；
2. 如何记录了连续括号的长度；
3. 如何寻找最长的子串；

现在我们的一个解题思路的大致框架就已经构建的差不多了，接下来就需要开始对框架中的细节进行完善了，下面我们就来接下一下这几个问题；

2.2 问题解析

2.2.1 如何计算有效括号的个数

这个问题看似只有一个问题，实际上它考察的是两个点：

• 判断有效括号
• 计算有效括号的个数

现在我们不难发现，这个问题实际上就是上一道题的升级版。在上一题中，我们只需要找出不是有效括号的元素就行了，但是在这一题中，我们则是要找出所有的有效括号并对其进行数量统计，如果仅仅只是实现这个功能的话，那实现的过程也很简单，对应代码如下所示：

代码语言：javascript复制

char S[MAXSIZE] = { 0 };//数据域
	int i = 0;//指针域——栈顶指针
	int count = 0;//计数器
	for (int j = 0; s[j]; j  ) //遍历原字符串
	{
		if (s[j] == '(')//遇到左括号
			S[i  ] = s[j];//进行入栈操作
		else {
			if (i)//当i不为0时，说明栈非空，此时有与之相匹配的左括号
			{
				count  ;//匹配成功，正常计数
				S[--i] = 0;//进行出栈操作
			}
		}
	}

通过这段代码，我们就能很好的实现判断有效括号并记录有效括号的数量这两个功能，但是这并不足以解决这一道题，前面也说过了，这是一道综合题，它的考察内容目前我们才只完成了一个，接下来我们继续分析；

2.2.2 如何记录了连续括号的长度

单看这个问题，确实不那么容易理解，这里又是连续括号又是长度的，此时就有两个新的问题产生：

• 什么样的括号属于连续括号？
• 连续括号的长度如何计算？

对于第一个问题，我们可以理解为两个括号之间不存在无效括号的单括号，这样的两个括号就称为连续括号，因此，对于连续括号的形式大致就有以下两种：

1. 包含型连续括号——"(())"
2. 独立型连续括号——"()()"

那如何计算它们的长度呢？对于这个问题，我们有很多种解决方式，但是这里我简单的介绍一下连续括号的个数与连续括号长度之间的关系。

首先我们要明确的是一个有效括号是由两个单括号组成，那么也就是说其对应的字符串长度就是两个字符。根据这个特性我们就能很容易得到结论：

因此现在我们就有了一种解题思路——记录连续括号的个数。在这种解题思路下随之就会产生一个新问题——如何判断括号是否连续？

通过观察我们不难发现，这两种类型的判断都是有明显特征的：

• 对于包含型的连续括号，入栈与出栈都是连续不间断的，因此我们在判断包含型的连续括号时，我们实际上只需要看右括号即可，当右括号是连续的并且都能匹配成功，那么右括号的数量就是连续有效括号的数量；
• 对于独立型的连续括号，左括号的下一个括号必定是右括号，右括号的下一个一定是左括号，也就是入栈与出栈是交替进行的，因此在栈中最直观的反应就是每次出栈时，栈都为空栈。所以我们在判断独立型的括号时，我们只需要判断匹配成功后栈是否为空栈即可，空栈的次数就是连续有效括号的个数；

那是不是我们按照这两种类型的连续括号来分别进行实现就可以了呢？答案是否定的，这里我们例举的是连续括号比较典型的两个例子，并不是代表所有的情况都是这二者其一，实际上更多的是二者相结合，如——"(()())"。在这种情况下我们如果采用的是上述判断中的其中一种，那么得出的结果肯定是错的，在这种情况下我们又该如何处理呢？

其实不管是包含型的也好还是独立型的也好，它们作为连续括号的最终结果就是入栈的次数与出栈的次数相同，也就是我们在遍历完字符串后最终得到的应该是空栈。

这时有朋友可能会说，如果是"((()())"这种情况呢？我们在遍历完数组后得到的结果并不是空栈这时我们又应该如何处理呢？

在这种情况下我们实际上只需要将原先的判空替换成是否为第一个元素即可，这里我就将其称为遍历起点，当我们在遍历完有效括号的长度后，栈的状态回到了遍历的起始点，那么就说明这个过程中出现的有效括号都为连续的，因此有效括号的个数就为连续括号的个数。

这时有朋友又会有疑问了，既然我这里提到了遍历的起始点，那这个起始点我应该如何来确定呢？

这个问题我们先保留，我们先接着往后看。

2.2.3 如何寻找最长的子串

在解决了上面两个问题后，随之而来的就是咱们今天要解决的最后一个问题了——如何寻找最长的子串？

既然是最长，那肯定就是有比较才行，比较的对象是什么呢？

没错就是无效括号两边的有效括号的长度。如在字符串"(()())(()"中，我们可以看到它是由左边的三个连续的有效括号和右边的一个有效括号组成，二者中间由一个无效的左括号隔开，在这种情况下我们如何来通过计算机实现查找呢？

按照前面分析的思路，如果我能够分别将无效括号两侧的有效括号记录下来，那是不是问题就迎刃而解了呢？因此，我们就有了第一种解题思路——通过找到无效括号，并将无效括号作为断点将字符串分为左右两个部分，之后再进行左右两部分长度的比较。那这个思路有没有问题呢？我们继续分析；

如果使用这个解题思路的话，那我们就需要解决以下几个问题：

假设一个长度为n的字符串，当我们需要判断第一个元素是否为有效括号时，就会出现以下几种情况：

在这一道题中，对于这个问题规模来说，此时的时间复杂度很显然是不太合适的，如果我们直接实现这个算法的话，只会出现一个结果——测试用例超时，因此我不建议大家来实现这个算法，感兴趣的朋友自己可以尝试着实现一下；

那既然这个思路并不能解决这一题，那我们又应该如何来解题呢？大家还记不记得我们前面遗留的一个问题——如何确定遍历的起始点，所谓的起始点，最实际的就是各个字符在字符串中出现的位置，那我们是不是只需要记录下来每个字符出现的位置就可以了呢？

这里我要先简单介绍一下字符串的一点知识——对于字符串而言，我们可以将其看做一个字符数组，因此我们可以通过对应的下标来访问对应的元素。在字符串中，每个字符对应的下标与其所在位置的差值为1，就比如字符串中的第一个元素它出现在字符串的第一个位置，但是它对应的下标为0，依次类推，出现在字符串第n个位置的字符它对应的下标则为n-1；

有了这个知识点的支撑，下面我们则有了一种新的解题思路——我们在栈中不再记录字符，而是记录每个字符所对应的下标。那这里就会产生一个问题——我们要记录的是左括号的下标还是右括号的下标呢？为了理清我们的思路，下面我们就来探讨一下这两种情况：

• 记录左括号的下标

从上图中我们不难发现，当我们记录左括号的下标时，每一个下标对应的都是一个遍历的起始点，那现在问题来了，我们又应该如何来记录有效括号的个数呢？

这里我们需要复习一下数组的相关知识了，在数组中，两个下标的差值为两下标中间元素的个数比如给定的字符串中，我们用下标3来减下标1得到的就是从下标1开始到下标3 这个过程中的元素个数，它包含的是下标1和下标2这两个元素。

回到题目中，此时我们记录的1为遍历的起始点，当我们遍历到下标3时，进行了第一次出栈，此时我们用3来与1作差得到的就是中间的元素个数，即有效括号的长度，同理，当我们遇到5时进行的是第二次出栈，用5减1，我们得到的是新的有效括号的长度，可以这里的问题就来了，当我们遇到6时，1也进行了出栈，这时我们就没有对应的起点了，显然这样是不太合理的。下面我们来看一下如果记录的是右括号的下标，又会如何；

• 记录右括号的下标

这一次我们会发现，如果只是记录右括号下标，我们无法实现任何事情。既然只记录左括号的话会出现当栈为空栈时我们无法记录有效括号的个数，只记录右括号的话我们又根本啥都做不了，那我们应该怎么办呢？

从上面两次演示我们可以看到，如果记录左括号的下标的话那实际上是可行的，只不过我们需要将左括号全部出栈的情况进行完善，而记录右括号的话，看似我们无法实现任何事情，实际上只要我们观察一下就会发现，每一个右括号的下标都是下一次记录的起始点，比如下标3为右括号，那就相当于我下一次遍历就是从4开始，当遇到下标5的时候，也就意味着起始点被跟换了，那我下一次遍历就是从6开始，从这个角度来看的话我们会得到一个结论：

• 右括号的下标记录的是遍历的起始点，左括号的下标记录的是括号匹配的情况；

那我们接下来何不尝试一下同时记录左右括号的下标呢？当遇到左括号时，我们记录左括号对应的下标，当遇到右括号时，我们将左下标进行出栈，并记录右括号的下标。但是这里同样会存在一个问题，如果开头的第一个元素为左括号，并且还能被匹配成功，这种情况又应该如何处理呢？

这时有朋友很快就反应过来了，我直接在遍历开始前在栈帧中添加一个起点不就行了吗？既然数组下标之间的差值是两个下标之间的元素个数，那我何不在0下标前先入栈一个-1作为起始点呢？如下所示：

【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！_字符串_19

此时我们会发现一个新问题，如果我们是在遇到右括号将左括号出栈，并记录右括号的下标，那我们会发现对于我们无法计算连续括号的个数与长度，就如同上面例子中的下标为1的左括号，它本身是与下标为6的右括号进行匹配的，但此时因为栈顶元素为前一个右括号的下标5，因此我们在这个算法中，并未实现下标为1的左括号与下标为6的右括号进行匹配。那我们应该如何修改呢？

我们现在可以思考一下，当下标为2的左括号与下标为3的右括号匹配成功时，此时我们的遍历起始点有没有发生变化？我们在计算连续有效的有效括号时是接着从1开始还是重新从3开始？

答案是当匹配成功时，计算连续有效括号的起始点并未发生变化，因此，对于下标为3的右括号，我们并不需要进行入栈操作，同理下标为4与下标为5的左右括号进行匹配完，也同样不需要将右括号的下标进行入栈操作。也就是说，我们的栈中存放的是未匹配成功的左右括号的下标，也就是我们所说的遍历起始点，所以这个算法完整的思路应该是：

1. 在开始遍历前在栈中入栈一个下标值为-1的起始点；
2. 当遍历到左括号时进行入栈操作，当遍历到右括号时如果没有与之匹配的左括号则进行入栈操作，反之，则将与之匹配的左括号下标进行出栈；
3. 当匹配成功时，通过右括号下标与遍历起始点的下标进行作差，得到从起始点开始到匹配成功时的有效括号的长度；
4. 将此时的有效括号长度与所记录的最大长度进行比较，并取最大值；

现在还有一个问题，如下图所示：

【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！_leetcode_20

在这种情况下，栈中会存在两个起始点，并且此时下标为0的右括号，并不能随着后续的扫描而被正常匹配，那么在这种情况下，这个记录的-1这个起始点还有存在的必要吗？答案是并没有存在的必要，而且不仅仅是这个情况下的-1，还有下面这种情况：

【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！_栈_21

此时下标为6和下标为7的两个括号都不可能在后续的扫描中被匹配成功，因此我们实际上只需要记录一个7就行；

也就是说当遇到右括号时，它如果被匹配成功就不需要记录对应下标，当它匹配失败时则需要记录对应的下标，并且该下标为后续记录连续有效括号的起始点，因此我们可以将原先已有的起始点进行替换，也就是将原先的起始点出栈，并入栈新的右括号的下标作为遍历起始点。所以我们算法最终的完整形态如下所示：

【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！_leetcode_22

现在对于整个算法的思路我们已经理顺了，接下来就可以编辑代码来实现算法了；

2.3 代码实现

根据上述思路，我们在代码中需要完成以下几个功能：

1. 创建一个存放下标的栈，并将-1进行入栈；
2. 从左往右遍历字符串中的所有元素；
3. 当遇到左括号时进行对应下标的入栈；
4. 当遇到右括号时，将栈顶元素出栈，并将下标对应的元素与其进行匹配：

• 匹配成功，则继续往后扫描；
• 匹配失败，则将右括号对应下标入栈；

1. 当右括号匹配成功时，将右括号的下标与此时的栈顶元素进行作差，得到有效括号的长度；
2. 将有效括号长度与最大值进行比较，取二者中的最大值；

下面我们就来依次实现对应的功能：

2.3.1 创建栈

首先我们要选择栈的类型，在前面的思路分析以及演示中我们不难发现，这个算法的时间复杂度为

，因此对于此题30000的问题规模来说，我们是可以选用顺序栈进行解题的，但是在实际运用中我更倾向于链栈。这里我们还是以顺序栈为例来进行解题，同样的我们是以一个整型数组来模拟实现顺序栈，对应代码如下所示：

代码语言：javascript复制

int len = strlen(s);//计算当前字符串的长度——可要可不要
	if (!len)//当长度为0时
		return 0;//此时我们就不需要其它操作了，可以直接返回0
	int* S = (int*)calloc(len   1, sizeof(int));//创建顺序栈
	assert(S);//如果创建失败则打断程序的运行
	int i = 0;//指向栈顶元素的指针
	S[0] = -1;//将-1进行入栈

这里需要注意的是，我们在计算好长度后，在申请空间时需要申请len 1的空间，这样是为了避免出现第一个字符为左括号的情况，当第一个字符为左括号时，我们需要栈的空间至少是2个，一个存放起始点-1，一个存放第一个左括号的下标0，当然我们也可以选择直接向内存空间申请30001的连续空间来进行栈的创建，对应代码如下所示：

代码语言：javascript复制

#define MAXSIZE 30001
int longestValidParentheses(char* s) {
	int S[MAXSIZE] = { 0 };//创建顺序栈
	int i = 0;//指向栈顶元素的指针
	S[0] = -1;//将-1进行入栈
}

这里我们可以根据个人的喜好进行选择；

2.3.2 遍历字符串

字符串的遍历在上一题中也有详细的介绍，这里我就不多加赘述了，此时我们还是通过for循环来实现，对应代码如下所示：

代码语言：javascript复制

//遍历字符串
	for (int j = 0; s[j]; j  ) {

	}

这里我还是要强调一下，之所以我们可以通过S[j]来进行判断，这是因为''作为字符串的结束标志，它所对应的ASCII码值为0，而在循环的条件判断中，0为假，不能进入循环，因此我们可以通过遍历的元素来控制循环。当然，如果我们在前面有计算字符串的长度，这里也可以采用j < len来作为判断条件，具体的实现根据自己的需求进行选择；

2.3.2 遇到左右括号时的处理

在遍历的过程中，根据遇到的不同内容来选择不同的操作，这个实现方式我们很熟悉了——通过分支语句来实现，对于左括号我们的处理比较单一，但是对于右括号，则又需要分情况讨论，因此，这里我们选用if语句来实现不同情况下的操作，代码如下所示：

代码语言：javascript复制

if (s[j] == '(') //遇到左括号时
			S[  i] = j;//将左括号的下标进行入栈
		else if (s[j] == ')' && S[i] == -1)//当扫描的第一个元素为右括号时
			S[i] = j;//将-1出栈，并将此时的右括号下标进行入栈
		else if (s[j] == ')' && s[S[i]] != '(') //当扫描到右括号时栈顶元素存储的下标对应的元素与右括号不匹配时
			S[i] = j;//将当前栈顶存放的下标进行出栈，并将此时右括号的下标进行入栈
		else if (s[j] == ')' && s[S[i]] == '(')//当扫描到右括号时，栈顶元素存储的下标对应的元素与右括号相匹配
		{
			S[i--] = 0;//将栈顶元素出栈后移动栈顶指针
		}

此时对于遇到不同类型的括号的下标处理我们就完成了，接下来就要到咱们的重点了——记录有效括号的长度；

2.3.3 记录有效括号的长度

对于有效括号长度的计算，前面我们已经介绍的很详细了，这里我就再简单的提一下：

• 当匹配成功时，我们通过当前右括号的下标与此时的栈顶元素继续作差，得到的就是当前匹配成功时有效括号的长度；

当然因为要记录有效括号的长度，我们则需要在遍历开始前先创建一个整型变量Length，这里我就不展示创建变量的代码了，我们这里直接展示记录长度的代码：

代码语言：javascript复制

else if (s[j] == ')' && s[S[i]] == '(')//当扫描到右括号时，栈顶元素存储的下标对应的元素与右括号相匹配
		{
			S[i--] = 0;//将栈顶元素出栈后移动栈顶指针
			Length = j - S[i];//将当前右括号的下标与当前的栈顶元素进行作差，得到有效括号的长度
		}

这里我们要注意的是，这个出栈移动指针的过程与计算长度的过程不能颠倒，如果颠倒了，计算的就不是匹配成功时右括号与起始点之间的差值，而是右括号与当前与之匹配的左括号之间的差值，这样计算出来的结果肯定是错的；

接下来我们来看最后一个功能——记录最大值；

2.3.4 记录有效括号长度的最大值

这个最大值的记录应该是在每次匹配完成后再进行记录，因此我们同样是在匹配完成的情况下来实现记录最大值，这里对于最大值变量的创建我就不再展示了，我们还是展示记录有效长度最大指的代码，对应代码如下所示：

代码语言：javascript复制

else if (s[j] == ')' && s[S[i]] == '(')//当扫描到右括号时，栈顶元素存储的下标对应的元素与右括号相匹配
		{
			S[i--] = 0;//将栈顶元素出栈后移动栈顶指针
			Length = j - S[i];//将当前右括号的下标与当前的栈顶元素进行作差，得到有效括号的长度
			max = max > Length ? max : Length;//记录有效括号长度的最大值
		}

这里大家可以像我一样通过三目操作符来实现比较大小并取最大值的方式来简化代码。

2.3.5 完整代码展示

现在我们的整体逻辑就全部实现了，下面我们来看一下完整的代码；

代码语言：javascript复制

//最长有效括号——栈、字符串、动态规划——困难
int longestValidParentheses1(char* s) {
	int len = strlen(s);//计算当前字符串的长度——可要可不要
	if (!len)//当长度为0时
		return 0;//此时我们就不需要其它操作了，可以直接返回0
	int* S = (int*)calloc(len   1, sizeof(int));//创建顺序栈
	assert(S);//如果创建失败则打断程序的运行
	int i = 0;//指向栈顶元素的指针
	S[0] = -1;//将-1进行入栈
	int Length = 0;//记录当前有效括号的长度
	int max = 0;//记录有效括号长度的最大值
	//遍历字符串
	for (int j = 0; s[j]; j  ) {
		if (s[j] == '(') //遇到左括号时
			S[  i] = j;//将左括号的下标进行入栈
		else if (s[j] == ')' && S[i] == -1)//当扫描的第一个元素为右括号时
			S[i] = j;//将-1出栈，并将此时的右括号下标进行入栈
		else if (s[j] == ')' && s[S[i]] != '(') //当扫描到右括号时栈顶元素存储的下标对应的元素与右括号不匹配时
			S[i] = j;//将当前栈顶存放的下标进行出栈，并将此时右括号的下标进行入栈
		else if (s[j] == ')' && s[S[i]] == '(')//当扫描到右括号时，栈顶元素存储的下标对应的元素与右括号相匹配
		{
			S[i--] = 0;//将栈顶元素出栈后移动栈顶指针
			Length = j - S[i];//将当前右括号的下标与当前的栈顶元素进行作差，得到有效括号的长度
			max = max > Length ? max : Length;//记录有效括号长度的最大值
		}
	}
	return max;
}

现在我们可以在力扣上进行提交，看一下最终结果：

【数据结构】括号匹配问题你学会了吗？来刷刷题检验一下吧！！！_括号匹配问题_24

可以看到，此时我们提交的代码通过了所有的测试用例，这一道困难题我们也就完美的解决了。

结语

今天的内容中，我们通过力扣的两道习题加深了栈在括号匹配问题中的应用的相关知识点，我相信如果有从头到尾认真阅读完并跟着我的解题思路过一遍的朋友，对这一块的内容应该没啥问题了。后面如果再遇到括号匹配问题，我相信大家处理起来应该是得心应手了。

今天的内容到这里就全部结束了，希望今天的内容能帮助大家更好的学习和理解栈在括号匹配问题中的应用。在接下来的内容中我们会继续介绍栈在表达式求值中的相关应用，大家记得关注哦！！！

最后感谢各位的翻阅，咱们下一篇再见！！！

数据结构 遍历 数组 指针 字符串

0 人点赞