给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
时间: 2024-09-30 08:16:43 浏览: 53
这个问题描述的是检查一个字符串中的括号是否匹配的问题,通常这种类型的问题可以通过栈数据结构来解决。栈是一种后进先出(LIFO)的数据结构,非常适合处理这类问题,因为它可以在遇到打开括号时将其压入栈,在遇到关闭括号时检查栈顶元素是否匹配。
下面是使用 C++ 实现的一个解决方案:
```cpp
#include <stack>
bool isValid(const std::string& s) {
std::stack<char> stack;
const char validPairs[] = {"()", "[]", "{}"};
for (char c : s) {
switch (c) {
case '(':
case '[':
case '{':
stack.push(c);
break;
case ')':
if (stack.empty() || stack.top() != '(') return false;
stack.pop();
break;
case ']':
if (stack.empty() || stack.top() != '[') return false;
stack.pop();
break;
case '}':
if (stack.empty() || stack.top() != '{') return false;
stack.pop();
break;
default:
// 如果遇到非括号字符,直接忽略
continue;
}
}
// 判断所有括号是否都被正确配对了
return stack.empty();
}
```
这个函数遍历输入字符串`s`,每当遇到一个开放括号就将其压入栈,如果遇到一个关闭括号,就检查栈顶的括号是否与其匹配并弹出。如果在遍历结束时栈为空,说明所有的括号都已经被正确地配对了,返回 `true`;否则返回 `false`。
阅读全文