问题描述

给定字符串，仅包含左括号和右括号，设计算法，找出最长匹配的括号子串，返回该子串的长度。

如：

• ( ( ) 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;
 }

@最长括号匹配