题解 | 括号配对问题|非栈方法|c++

#include<bits/stdc++.h>
using namespace std;
vector<char> S;
int main() {
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        S.push_back(str[i]);
    }
    bool minB = true;
    while (minB) {
        minB = false;
        for (int i = 0; i < str.size(); i++) {
            if (S[i] == '(') {
                for (int j = i + 1 ; j < str.size(); j++) {
                    if (S[j] == '(' || S[j] == '[' || S[j] == ']') {
                        break;
                    }
                    if (S[j] == ')') {
                        S[i] = ' ';
                        S[j] = ' ';
                        minB = true;
                        break;
                    }
                }
            } else if (S[i] == '[') {
                for (int j = i + 1 ; j < str.size(); j++) {
                    if (S[j] == '(' || S[j] == '[' || S[j] == ')') {
                        break;
                    }
                    if (S[j] == ']') {
                        S[i] = ' ';
                        S[j] = ' ';
                        minB = true;
                        break;
                    }
                }
            }
        }
    }
    for (int i = 0; i < str.size(); i++) {
        if (S[i] == '(' || S[i] == ')' || S[i] == '[' || S[i] == ']') {
            cout << "false";
            return 0;
        }
    }
    cout << "true";
    return 0;
}

总之就是找最小的括号，遇到不匹配的括号就break，遇到匹配的就把括号变成空格，然后一直循环直到没有找到最小括号。

最后要是还剩括号就不合法