超简单 C++ 代码：用栈判断括号序列合法性，时间复杂度仅 O(n)！

以下是一个相对简单且符合你需求的 C++ 代码实现，同样是判断只由 `(`, `)`, `[`, `]`, `{`, `}` 这 6 种括号字符组成的字符串是否为合法括号序列。核心思路还是借助栈来处理，不过代码结构上会更简洁一些。 ```cpp #include <iostream> #include <stack> #include <string> // 判断字符串是否为合法括号序列 bool isValid(const std::string& str) { std::stack<char> st; for (char ch : str) { if (ch == '(' || ch == '[' || ch == '{') { st.push(ch); } else { if (st.empty()) return false; char top = st.top(); st.pop(); if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) { return false; } } } return st.empty(); } int main() { int T; std::cin >> T; std::cin.ignore(); for (int i = 0; i < T; ++i) { std::string input; std::getline(std::cin, input); if (isValid(input)) { std::cout << "YES" << std::endl; } else { std::cout << "NO" << std::endl; } } return 0; } ``` 代码解释： 1. `isValid` 函数： - 函数接收一个字符串作为参数，用于判断该字符串是否为合法括号序列。 - 定义一个 `std::stack<char>` 类型的栈 `st` 来辅助判断。 - 遍历输入字符串中的每个字符： - 若字符是左括号（`(`, `[`, `{`），将其压入栈中。 - 若字符是右括号（`)`, `]`, `}`），先检查栈是否为空，若为空则说明没有对应的左括号匹配，返回 `false`；若栈不为空，取出栈顶元素，检查栈顶的左括号和当前右括号是否匹配，若不匹配则返回 `false`。 - 遍历结束后，若栈为空，说明所有左括号都有对应的右括号匹配，返回 `true`；否则返回 `false`。 2. `main` 函数： - 读取输入的测试数据组数 `T`。 - 使用 `std::cin.ignore()` 忽略掉 `T` 后面的换行符。 - 循环 `T` 次，每次读取一个字符串，调用 `isValid` 函数判断该字符串是否合法，根据判断结果输出 `YES` 或 `NO`。 这个代码的时间复杂度是 $O(n)$，其中 $n$ 是输入字符串的长度，因为只需要对字符串进行一次遍历；空间复杂度是 $O(m)$，$m$ 是栈中最多元素的数量，最坏情况下是 $O(n)$。 ######[AI问答 | 722点数解答 | 2025-12-03 18:32:38]