[C++/PTA] 括号匹配

题目要求

给定仅包含()[]{}六种括号的字符串，请你判断该字符串中，括号的匹配是否是合法的，也就是对应括号的数量、嵌套顺序完全正确。

输入格式:
第一行一个整数T（T<=10）
其后T行每行一个字符串只包含[{()}]六种字符（字符串长度2e5以内）

输出格式:
对于每个字符串，匹配输出Yes,否则输出No

输入样例:
2
{()[]}
([)]

输出样例:
Yes
No

解题思路

这是一道典型的栈的应用题。可以遍历给定的字符串，每次遇到左括号时将其入栈，当遇到右括号时判断栈顶元素是否为对应的左括号，若是则弹出栈顶元素继续匹配，否则括号不匹配。如果遍历结束后栈为空，则说明括号匹配成功。

具体细节如下：

1.首先判断字符串长度是否为奇数，如果是奇数则无法匹配，直接返回 false。

2.遍历字符串中的每个字符，如果是左括号则入栈，如果是右括号则判断栈顶元素是否与之匹配，若匹配则弹出栈顶元素，否则返回 false。

3.遍历结束后，如果栈为空，则说明括号匹配成功，返回 true，否则返回 false。

代码

#include <iostream>
#include <stack>
using namespace std;
stack<char> st;  // 使用栈来进行括号匹配
bool isMarch(string str){  // 定义函数，判断给定字符串中的括号是否匹配
    int len = str.size();  // 获取字符串的长度
    if(len%2) return false;  // 首先判断字符串的长度是否为奇数，如果是奇数则无法匹配，直接返回 false
    for(int i=0;i<str.size();i++){  // 遍历字符串中的每个字符
        switch(str[i]){  // 判断当前字符是否为左括号或右括号
            case '(':
            case '[':
            case '{': st.push(str[i]);break;  // 左括号入栈
            case ')':
                if(!st.empty()&&st.top()=='(') st.pop();  // 当遇到右括号时，判断栈顶是否与之匹配，若匹配则弹出栈顶元素，否则返回 false
                else return false;
                break;
            case ']':
                if(!st.empty()&&st.top()=='[') st.pop();
                else return false;
                break;
            case '}':
                if(!st.empty()&&st.top()=='{') st.pop();
                else return false;
                break;
        }
    }
    return true;  // 遍历结束后如果栈为空，则说明括号匹配成功，返回 true，否则返回 false
}
int main(){
    int T;
    string str;
    cin >> T;  // 输入 T，表示后面有 T 个测试数据
    while(T--){
        cin >> str;  // 输入字符串
        cout << ((isMarch(str)) ? "Yes" : "No") << endl;  // 输出结果，如果括号匹配成功则输出 Yes，否则输出 No
    }
    return 0;
}

总结

该题主要考察栈的应用和字符串的遍历、判断等基本操作。读者需要熟练使用栈的相关操作，包括压栈、出栈、栈顶元素获取等。

我是秋说，我们下次见。