括号匹配检查算法：C++实现

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，但需要成对出现。即'()'或 '[([ ][ ])]'等为正确的格式，'[ ( ] )'或 '( [ ( ) )'或'( ( ) ] )'均为不正确的格式。

给定一串括号输入（换行作为结束符），检测格式是否正确，若正确输出YES；错误输出NO。

输入

第一行一个正整数T,表示有T组测试数据

接下来T行每行一个字符串。

输出

T行，每一行一个YES 或 NO。

样例输入

2
([]())
([)]

样例输出

YES
NO

C++代码

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool checkParentheses(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[') {
            st.push(c);
        } else if (c == ')' || c == ']') {
            if (st.empty()) {
                return false;
            }
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') || (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return st.empty();
}

int main() {
    int T;
    cin >> T;
    cin.ignore();
    for (int i = 0; i < T; i++) {
        string s;
        getline(cin, s);
        if (checkParentheses(s)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

算法原理

该算法使用栈来存储未匹配的左括号。当遇到右括号时，检查栈顶元素是否与之匹配，如果不匹配则返回false。最后，如果栈为空则说明所有括号都匹配成功，返回true。

应用场景

该算法可以用于检查各种包含括号的表达式、代码或其他文本的格式是否正确，例如：

数学表达式
程序代码
配置文件
JSON数据

总结

本文介绍了使用C++实现的括号匹配检查算法，并提供了详细的代码示例和测试用例。该算法简单易懂，并且应用范围广泛。希望本文能够帮助读者更好地理解括号匹配检查算法的原理和应用场景。