C++算法练习-day23——20.有效的括号

2024/10/27 16:47:38 来源：https://blog.csdn.net/L613Z/article/details/142964334 浏览: 次关键词：C++算法练习-day23——20.有效的括号

题目来源：. - 力扣（LeetCode）

题目思路分析

题目是关于验证括号字符串是否有效的经典问题。一个括号字符串是有效的，当且仅当它满足以下条件：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

例如，字符串 "()" 和 "()[]{}" 是有效的，而 "(]" 和 "(()" 则不是有效的括号字符串。

解题思路：

使用栈（Stack）数据结构来处理括号匹配问题。
遍历字符串中的每个字符：
- 如果遇到左括号（'(', '[', '{'），将其压入栈中。
- 如果遇到右括号（')', ']', '}'），检查栈顶元素是否为对应的左括号，如果是，则弹出栈顶元素，否则字符串无效。
最后，如果栈为空，说明所有的括号都成功匹配，字符串有效；否则，字符串无效。

代码：

#include <iostream>  
#include <stack>  
#include <unordered_map>  
#include <string>  using namespace std;  class Solution {  
public:  bool isValid(string s) {  int n = s.size();  // 如果字符串长度为奇数，直接返回false，因为无法匹配  if (n % 2 == 1) {  return false;  }  // 创建一个哈希表，存储右括号到左括号的映射  unordered_map<char, char> pairs = {{'}', '{'}, {']', '['}, {')', '('}};  stack<char> stk;  // 遍历字符串中的每个字符  for (char e : s) {  // 如果当前字符是右括号  if (pairs.count(e)) {  // 如果栈为空，或者栈顶元素不是对应的左括号，则字符串无效  if (stk.empty() || stk.top() != pairs[e]) {  return false;  }  // 弹出栈顶元素，表示成功匹配了一对括号  stk.pop();  } else {  // 如果是左括号，则压入栈中  stk.push(e);  }  }  // 如果栈为空，说明所有括号都成功匹配，返回true  // 否则，返回false，表示有未匹配的左括号  return stk.empty();  }  
};

注释详解

unordered_map<char, char> pairs = {{'}', '{'}, {']', '['}, {')', '('}};：创建一个哈希表，用于存储右括号到左括号的映射。
stack<char> stk;：创建一个栈，用于存储遍历过程中遇到的左括号。
if (n % 2 == 1) { return false; }：如果字符串长度为奇数，直接返回false，因为无法匹配。
if (pairs.count(e)) { ... } else { ... }：判断当前字符是否为右括号，如果是则检查栈顶元素，否则将左括号压入栈中。
if (stk.empty() || stk.top() != pairs[e]) { return false; }：如果栈为空，或者栈顶元素不是对应的左括号，则返回false。
stk.pop();：弹出栈顶元素，表示成功匹配了一对括号。
return stk.empty();：最后检查栈是否为空，如果为空则返回true，否则返回false。