20_有效的括号
【问题描述】
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例一：
输入：s = "()"
输出：true
示例二：
输入：s = "()[]{}"
输出：true
示例三：
输入：s = "(]"
输出：false
示例四：
输入：s = "([])"
输出：true
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
【算法设计思想】
在解决本题时，我们要使用一种类似于键值对的数据结构，要确保左右括号的对应关系。在Python中我们可以直接使用内置的字典数据类型，在Java中我们可以使用HashMap类，在C++中我们可以使用STL中的unordered_map来实现，在什么都没有的C语言中我们可以直接自己定义一个pairs函数用来实现这种对应关系。然后我们依次遍历给定的字符串s，如果碰到了左括号，那么我们把它加入到栈中，如果碰到了右括号，那么我们调用这种对应关系，然后判断栈顶的元素和其是否匹配，如果匹配，那么我们继续遍历，只要有一个不匹配，那么我们直接返回false即可。最后我们看一下栈是否为空，即可得出结论。
注意：
- Java中和C++中各种数据结构的调用
【算法描述】
Python：
class Solution:
def isValid(self, s: str) -> bool:
# 定义括号对应关系的字典，右括号为键，左括号为值
brackets = {')': '(', ']': '[', '}': '{'}
# 初始化一个空栈，用于存放左括号
stack = []
# 遍历字符串中的每个字符
for char in s:
# 如果字符是左括号，将其压入栈中
if char in brackets.values():
stack.append(char)
# 如果字符是右括号，检查匹配情况
elif char in brackets:
# 当栈为空或栈顶元素不匹配当前右括号时，返回False
if not stack or brackets[char] != stack[-1]:
return False
# 如果栈顶元素匹配当前右括号，弹出栈顶元素
stack.pop()
# 遍历结束后，检查栈是否为空
# 如果栈为空，说明所有括号成功匹配；否则返回False
return not stack
C++:
class Solution {
public:
bool isValid(const std::string& s) {
// 定义括号对应关系的 unordered_map，右括号为键，左括号为值
std::unordered_map<char, char> brackets = {
{')', '('}, // 右括号 ')' 对应左括号 '('
{']', '['}, // 右括号 ']' 对应左括号 '['
{'}', '{'} // 右括号 '}' 对应左括号 '{'
};
// 初始化一个空栈，用于存放左括号
std::stack<char> stack;
// 遍历字符串中的每个字符
for (char elem : s) {
// 如果字符是左括号，将其压入栈中
if (elem == '(' || elem == '[' || elem == '{') {
stack.push(elem);
}
// 如果字符是右括号，检查匹配情况
else if (brackets.count(elem)) {
// 当栈为空或栈顶元素不匹配当前右括号时，返回 false
if (stack.empty() || stack.top() != brackets[elem]) {
return false;
}
// 如果栈顶元素匹配当前右括号，弹出栈顶元素
stack.pop();
}
// 如果字符既不是左括号也不是右括号，返回 false（可以选择忽略或处理非法字符）
else {
return false;
}
}
// 遍历结束后，检查栈是否为空
// 如果栈为空，说明所有括号成功匹配；否则返回 false
return stack.empty();
}
};
Java：
class Solution {
public boolean isValid(String s) {
// 获取字符串的长度
int n = s.length();
// 如果长度是奇数，括号不可能成对匹配，直接返回 false
if (n % 2 == 1) {
return false;
}
// 定义一个 HashMap 来存储括号的配对关系
// 右括号为键，左括号为值
Map<Character, Character> pairs = new HashMap<Character, Character>() {
{
put(')', '('); // 右括号 ')' 对应左括号 '('
put('}', '{'); // 右括号 '}' 对应左括号 '{'
put(']', '['); // 右括号 ']' 对应左括号 '['
}
};
// 初始化一个空栈，用于存放左括号
Deque<Character> stack = new LinkedList<Character>();
// 遍历字符串中的每个字符
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
// 如果字符是右括号，检查是否有匹配的左括号
if (pairs.containsKey(ch)) {
// 如果栈为空，或栈顶的左括号不匹配当前的右括号，返回 false
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
// 如果栈顶元素匹配当前右括号，弹出栈顶元素
stack.pop();
}
// 如果字符是左括号，将其压入栈中
else {
stack.push(ch);
}
}
// 遍历结束后，检查栈是否为空
// 如果栈为空，说明所有的括号都成功匹配；否则返回 false
return stack.isEmpty();
}
}
C：
/**
* 根据给定的右括号字符返回对应的左括号字符。
* @param ch 一个右括号字符。
* @return 对应的左括号字符，如果不存在则返回0。
*/
char pairs(char ch)
{
if (ch == ')')
return '(';
if (ch == ']')
return '[';
if (ch == '}')
return '{';
return 0;
}
/**
* 检查给定的字符串中的括号是否正确匹配。
* @param s 包含括号的字符串。
* @return 如果括号正确匹配，则返回true；否则返回false。
*/
bool isValid(char *s)
{
int n = strlen(s);
// 如果字符串长度为奇数，则括号无法完全匹配
if (n % 2 == 1)
{
return 0;
}
char stack[n + 1];
int top = 0;
for (int i = 0; i < n; i++)
{
char ch = pairs(s[i]);
if (ch)
{
// 如果当前字符是右括号，检查它是否与栈顶的左括号匹配
if (top == 0 || stack[top - 1] != ch)
{
return 0;
}
top--;
}
else
{
// 如果当前字符是左括号，将其压入栈顶
stack[top++] = s[i];
}
}
// 如果栈为空，说明所有括号都正确匹配
return top == 0;
}