试题 历届真题 括号序列【第十二届】【省赛】【b组】

括号序列问题是一个经典的计算机算法问题，其目的是判断一个给定的括号序列是否合法。在这道题目中，我们需要实现一个程序，判断一个由左右括号组成的字符串是否为合法的括号序列。

具体来说，合法的括号序列需要满足以下条件：

1. 左右括号必须成对出现，即每个左括号都必须有一个对应的右括号。

2. 左右括号的顺序必须正确，即每个左括号必须先于其对应的右括号出现。

3. 括号序列中不能出现嵌套的括号，即一个左括号不能包含另一个左括号或右括号。

为了解决这个问题，我们可以使用栈这种数据结构来实现。具体来说，我们可以遍历字符串中的每个字符，如果当前字符是左括号，则将其压入栈中；如果当前字符是右括号，则从栈中弹出一个左括号，判断其是否与当前右括号匹配。如果栈为空或弹出的左括号与当前右括号不匹配，则说明括号序列不合法。

以下是一个示例代码，用于判断一个字符串是否为合法的括号序列：

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

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

int main() {
    string s;
    cin >> s;
    if (isValid(s)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return ;
}

在这个示例代码中，我们使用了一个栈来存储左括号，遇到右括号时从栈中弹出一个左括号进行匹配。如果栈为空或弹出的左括号与当前右括号不匹配，则说明括号序列不合法。最后，如果栈为空，则说明括号序列合法。