问题描述
给定字符串，仅包含左括号和右括号，设计算法，找出最长匹配的括号子串，返回该子串的长度。
如：
- ( ( ) 2
- ( ) ( ) 4
- ( ) ( ( ) 2
- ( ) ( ( ) ) 6
- ( ( ) ( ) ) 6
分析
“最长匹配的括号子串”的长度，等于“最长匹配的括号子串”的括号匹配数 * 2。所以只需求“最长匹配的括号子串”的括号匹配数。
-
假设在给定字符串中，存在一个“匹配的括号子串”A：
如果A的下一个字符为
0，即字符串结束，则此子串结束匹配；如果A的下一个字符为
)，)没有与之匹配的左括号，因此此子串结束匹配；-
如果A的下一个字符为
(，则此子串可能结束匹配，也可能未结束匹配。- 如果此子串未结束匹配，则说明后续的字符串中有一个右括号与之对应；反之说明后续的字符串中没有一个右括号与之对应，如“ ( ) ( ( ( ) ”。所以，可以在遇到
)时，判断此)是否与所述(对应，如果对应，则两个子串合并为一个匹配子串，否则两个匹配子串由(隔开。
- 如果此子串未结束匹配，则说明后续的字符串中有一个右括号与之对应；反之说明后续的字符串中没有一个右括号与之对应，如“ ( ) ( ( ( ) ”。所以，可以在遇到
用一个变量left记录子串未匹配的
(的个数，每出现一个(，left加1，每出现一个)，left减1，则left为0时，子串匹配。
代码
#include <stdio.h>
#include <stdlib.h>
int NumOfMatch(char* str)
{
const char* p = str;
int nLeft = 0; // 待匹配的左括号的个数
int nMatchedPre = 0;// 上一个匹配子串的已匹配括号的对数
int nMatchedCur = 0;// 当前子串的已匹配括号的对数
int MAX = 0;
for (; *p; ++p)
{
if ('(' == *p)
{
++nLeft;
}
else if (')' == *p)
{
if (0 == nLeft) // 上一个子串结束匹配
{
MAX = __max(nMatchedPre, MAX);
nMatchedPre = 0;
}
else
{
--nLeft;
++nMatchedCur;
if (0 == nLeft) // 两个子串合并
{
nMatchedPre += nMatchedCur;
nMatchedCur = 0;
}
}
}
}
MAX = __max(__max(nMatchedPre, nMatchedCur), MAX);
return MAX * 2;
}
int main()
{
char str[100];
while (gets_s(str))
{
int result = NumOfMatch(str);
printf("%d\n", result);
}
return 0;
}
