【[20] 有效的括号】
- @lc app=leetcode.cn id=20 lang=cpp
- @lcpr version=30202
- [20] 有效的括号 */ 这段代码是用来验证括号是否有效的，下面是注释的版本：
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>bool isValid(string s) {
std::stack<char> stack;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.empty()) {
return false;
}
char top = stack.top();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false;
}
stack.pop();
}
}
return stack.empty();
}这段代码主要通过使用栈实现括号匹配。每遇到一个开括号就压入栈中，每遇到一个闭括号就检查是否与栈顶的开括号匹配，匹配则继续处理，不匹配则验证失败。最终如果栈为空，则说明所有的括号都已匹配，返回true；如果栈不为空，则说明存在未匹配的括号，返回false。
为了将给定的代码转换为C++98的版本（因为C++11引入了基于范围的for循环和auto类型推断等特性），我们需要替换基于范围的for循环并适当修改代码风格。以下是修改后的C++98兼容代码：
#include <stack>
#include <string>
bool isValid(std::string s) {
std::stack<char> stack;
// 用传统的for循环替代基于范围的for循环
for (size_t i = 0; i < s.length(); i++) {
char c = s[i]; // 获取当前字符
// 检查字符是否为开括号
if (c == '(' || c == '[' || c == '{') {
stack.push(c); // 将开括号压入栈
} else {
// 当遇到闭括号时，如果栈为空，说明没有相应的开括号可以匹配
if (stack.empty()) {
return false;
}
char top = stack.top();
// 检查栈顶的开括号是否与当前闭括号匹配
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false; // 如果不匹配，返回false
}
stack.pop(); // 匹配成功，弹出栈顶的开括号
}
}
// 最后检查栈是否为空，如果为空，则所有括号都正确匹配，返回true
return stack.empty();
}在这个版本中，我们使用size_t i = 0; i < s.length(); i++来代替原来基于范围的for循环，并直接通过下标访问字符串中的每个字符。这保证了代码是C++98标准兼容的。这种方式在处理字符串和数组元素时仍然是常见且有效的。
您提供的示例字符串 “(1)[]{}” 中包含了数字和括号。原始的括号验证代码只处理了括号字符，对于数字和其他非括号字符没有进行处理。如果需要该代码片段正确处理这种包含非括号字符的字符串，我们需要对原有代码进行一些简单修改，忽略非括号字符。
以下是修改过的代码，它会忽略所有非括号字符：
#include <stack>
#include <string>
bool isValid(std::string s) {
std::stack<char> stack;
for (size_t i = 0; i < s.length(); i++) {
char c = s[i];
// 只处理括号字符
switch(c) {
case '(':
case '[':
case '{':
stack.push(c); // 如果是开括号，压入栈
break;
case ')':
if (stack.empty() || stack.top() != '(') return false; // 如果栈为空或栈顶不是匹配的开括号，返回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:
// 忽略所有非括号字符
break;
}
}
return stack.empty(); // 如果栈为空，说明所有开括号都被匹配了，返回true
}在这个修改版中，我们通过一个switch语句来处理每个字符。如果字符是一个括号，它将进入相应的处理逻辑；如果是其他字符，如数字或字母，将直接忽略。这样的处理可以确保函数能适用于包含任意字符的字符串。
如果不想使用switch语句来处理字符，可以使用if语句来分别判断每种情况。下面是使用if语句改写的代码：
#include <stack>
#include <string>
bool isValid(std::string s) {
std::stack<char> stack;
for (size_t i = 0; i < s.length(); i++) {
char c = s[i];
// 处理开括号
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
// 处理闭括号
} else if (c == ')' || c == ']' || c == '}') {
if (stack.empty()) {
return false;
}
char top = stack.top();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
stack.pop();
}
// 忽略所有非括号字符
}
// 检查栈是否为空
return stack.empty();
}在这个改写的版本中，我们用连串的if和else if语句来识别并处理开括号和闭括号，而忽略了所有非括号的字符。这种方法同样有效，并且没有使用switch语句，避免对某些开发者来说可能在逻辑判断上不够直观的问题。这两种代码（使用switch和使用if）在功能上是等价的，具体使用哪种取决于个人或项目的编码风格偏好。