【POJHDOJleetcode】括号匹配合法性及最长括号匹配

• Z时代
• 2024-01-10
• 分类：综合

/*

1. string parenthesis
给出一个由()组成的字符串判断合法性,如()合法, (,  (((不合法.

2. 给出一串()字符串,求出最长连续括号匹配的长度及其位置
*/

#include <iostream>
#include <stdio.h>
#include <stack>
usingnamespace std;
class Solution {
public:
bool isValid(conststring& s) {
if (s == "") {
returntrue;
        }
        stack<char> stk;
        size_t size = s.size();
for (size_t i = 0; i < size; i++) {
if (s[i] == '(') {
                stk.push(s[i]);
            } else {
if (stk.empty()) returnfalse;
                stk.pop();
            }
        }
return stk.size() == 0;
    }
};
pair<int,int> NumOfMatch(constchar* str)
{
if (str == NULL) return {0, 0};
constchar* p = str;
int nLeft = 0;      // 待匹配的左括号的个数
int nMatchedPre = 0;// 上一个匹配子串的已匹配括号的对数
int nMatchedCur = 0;// 当前子串的已匹配括号的对数
int maxi = -1, maxmatch = 0;
constchar* front = p;
while (*p != '\0') {
if (*p == '(') {
++nLeft;
        } elseif (*p == ')') {
if (nLeft == 0) {
                maxmatch = max(nMatchedCur, maxmatch);
                nMatchedPre = nMatchedCur;
                nMatchedCur = 0;
            } else {
                nMatchedCur++;
                nLeft--;
if (nMatchedCur > maxmatch) {
                    maxi = (p - front);
                    maxmatch = nMatchedCur;
                }
            }
        }
        p++;
    }
    maxi -= maxmatch * 2 - 1;
    maxmatch *= 2;
return make_pair(maxi, maxmatch);
}
int cnt = 0;
int total = 0;
void expect_test(bool a, bool b) {
    total++;
if (a == b) {
        cnt++;
return;
    }
    printf("expect %d actual %d\n", a, b);
}
void expect_test_int(int a, int b) {
    total++;
if (a == b) {
        cnt++;
return;
    }
    printf("expect %d actual %d\n", a, b);
}
typedef pair<int,int> pii;
void expect_test_pair(pii a, pii b) {
    total++;
if (a.first == b.first && a.second == b.second) {
        cnt++;
return;
    }
    printf("expect {%d,%d} actual {%d,%d}\n",
    a.first, a.second, b.first, b.second);
}
int main() {
    Solution sol;
    expect_test(true, sol.isValid("()"));
    expect_test(true, sol.isValid("(())"));
    expect_test(true, sol.isValid("()()"));
    expect_test(false, sol.isValid(")"));
    expect_test_pair({0, 2}, NumOfMatch("()))"));
    expect_test_pair({0, 4}, NumOfMatch("(()))"));
    expect_test_pair({0, 4}, NumOfMatch("(())"));
    expect_test_pair({0, 0}, NumOfMatch(""));
    expect_test_pair({4, 4}, NumOfMatch("())((())"));
    printf("%d/%d\n", cnt, total);
return0;
}

以上是 【POJHDOJleetcode】括号匹配合法性及最长括号匹配 的全部内容， 来源链接： utcz.com/z/508577.html