有效的括号
描述：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
函数签名：bool isValid(string s)
示例：
输入：s = "()" 输出：true
输入：s = "()[]{}" 输出：true
输入：s = "(]" 输出：false
约束条件：
- 1 <= s.length <= 104
- s 仅由括号 ‘()[]{}’ 组成
题目解析
这个问题可以通过使用栈来解决。栈是一种后进先出（LIFO）的数据结构，它非常适合处理这种需要“最近匹配”的情况，比如括号匹配。我们可以遍历给定的字符串，每当遇到一个左括号时，将其压入栈中，当遇到一个右括号时，我们将检查栈顶元素是否是相应的左括号，如果是，则弹出栈顶元素，否则返回 false。最后，如果栈为空，则说明所有的括号都能匹配，返回 true；否则，返回 false。
下面是算法的详细步骤：
- 初始化一个空栈。
- 遍历字符串的每个字符：
- 如果当前字符是左括号（‘(’、‘[’、‘{’），则将其压入栈中。
- 如果当前字符是右括号（‘)’、‘]’、‘}’），则检查栈是否为空：
如果栈为空，则返回 false，因为没有相应的左括号与之匹配。
如果栈不为空，则弹出栈顶元素，检查其是否与当前右括号匹配，若不匹配，则返回 false。
- 遍历结束后，检查栈是否为空：
- 如果栈为空，则说明所有括号都能匹配，返回 true。
- 如果栈不为空，则说明有左括号没有匹配的右括号，返回 false。
下面是对应的C++代码实现：
#include <stack> #include <string> class Solution { public: bool isValid(string s) { stack<char> stk; for (char c : s) { if (c == '(' || c == '[' || c == '{') { stk.push(c); } else { if (stk.empty()) { return false; } char topChar = stk.top(); stk.pop(); if ((c == ')' && topChar != '(') || (c == ']' && topChar != '[') || (c == '}' && topChar != '{')) { return false; } } } return stk.empty(); } };
让我们通过一些示例来验证算法的正确性：
- 对于输入字符串 “()”，栈会依次压入 ‘(’ 和 ‘)’，最后栈为空，返回 true。
- 对于输入字符串 “()[]{}”，栈会依次压入 ‘(’, ‘[’, ‘{’，然后弹出 ‘{’, ‘[’, ‘(’，最后栈为空，返回 true。
- 对于输入字符串 “(]”，栈会依次压入 ‘(’, ‘[’，然后弹出 ‘[’, ‘(’，此时栈为空，但是’]'没有对应的左括号，返回 false。
题目延伸
理解你的需求，你希望对给定的算法题目进行延伸和实际应用的讨论，并且希望我能够将内容分成五次发送给你，每次约1000字左右。我会尽力满足你的要求。让我们开始第一部分。
延伸与实际应用：有效的括号
- 算法复杂度分析：
- 时间复杂度：遍历字符串一次，时间复杂度为 O(n)，其中 n 是字符串的长度。
- 空间复杂度：最坏情况下，当字符串中的字符都是左括号时，栈的大小会达到 n/2，因此空间复杂度为 O(n)。
- 括号匹配问题的变体：
括号匹配是一类常见的问题，可以延伸到更复杂的情况，如包含其他符号的括号匹配、带有优先级的表达式求值等。
- 错误信息提示：
在实际应用中，括号匹配可以用于编译器、解释器等程序中，以检查代码中括号的正确性。如果代码中存在括号不匹配的情况，编译器或解释器可以给出错误信息提示，帮助开发者快速定位问题所在。
实际应用
- 编程语言解析器：
在编程语言的解析器中，括号匹配是一个重要的步骤。解析器需要检查代码中的括号是否匹配，以确保代码的语法正确性。如果代码中存在不匹配的括号，解析器会报告错误并指出问题所在，帮助开发者及时修复代码。
代码演示：
#include <iostream> #include <stack> #include <unordered_map> #include <string> using namespace std; class LanguageParser { public: bool isValidCode(string code) { stack<char> brackets; unordered_map<char, char> bracketPairs = {{')', '('}, {']', '['}, {'}', '{'}}; for (char c : code) { if (bracketPairs.find(c) != bracketPairs.end()) { // 右括号 if (brackets.empty() || brackets.top() != bracketPairs[c]) { return false; // 括号不匹配 } brackets.pop(); } else if (bracketPairs.values().find(c) != bracketPairs.values().end()) { // 左括号 brackets.push(c); } } return brackets.empty(); // 所有左括号都匹配了 } }; int main() { LanguageParser parser; string code1 = "()"; string code2 = "()[]{}"; string code3 = "(]"; cout << boolalpha; // 输出true/false而不是1/0 cout << parser.isValidCode(code1) << endl; // 输出true cout << parser.isValidCode(code2) << endl; // 输出true cout << parser.isValidCode(code3) << endl; // 输出false return 0; }
- 表达式求值：
在数学表达式的求值过程中，括号的匹配也起着重要的作用。括号可以改变表达式中运算的优先级，因此在求值之前，需要确保括号的正确匹配，以保证表达式求值的准确性。
以下是一个简单的表达式求值的算法示例，它可以处理加法、减法、乘法和括号操作。
#include <iostream> #include <stack> #include <string> using namespace std; class ExpressionEvaluator { public: int evaluateExpression(string expression) { stack<int> nums; stack<char> ops; for (int i = 0; i < expression.length(); i++) { char c = expression[i]; if (c == ' ') continue; // 忽略空格 if (isdigit(c)) { int num = 0; while (i < expression.length() && isdigit(expression[i])) { num = num * 10 + (expression[i] - '0'); i++; } i--; // 回退一步，因为在循环结束时i多增加了一次 nums.push(num); } else if (c == '(') { ops.push(c); } else if (c == ')') { while (ops.top() != '(') { processOperation(nums, ops); } ops.pop(); // 弹出左括号 } else if (c == '+' || c == '-' || c == '*' || c == '/') { while (!ops.empty() && hasPrecedence(c, ops.top())) { processOperation(nums, ops); } ops.push(c); } } while (!ops.empty()) { processOperation(nums, ops); } return nums.top(); } private: bool hasPrecedence(char op1, char op2) { if (op2 == '(' || op2 == ')') return false; if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) return false; return true; } void processOperation(stack<int>& nums, stack<char>& ops) { int num2 = nums.top(); nums.pop(); int num1 = nums.top(); nums.pop(); char op = ops.top(); ops.pop(); int result = 0; switch (op) { case '+': result = num1 + num2; break; case '-': result = num1 - num2; break; case '*': result = num1 * num2; break; case '/': result = num1 / num2; break; } nums.push(result); } }; int main() { ExpressionEvaluator evaluator; string expression = "2 * (3 + 4) - 9 / 3"; cout << "Expression: " << expression << endl; cout << "Result: " << evaluator.evaluateExpression(expression) << endl; return 0; }
这个算法使用了栈来处理操作数和操作符。它首先遍历表达式中的每个字符，然后根据情况进行处理。处理过程中，操作符的优先级和括号的处理是关键点。
- 正则表达式解析：
正则表达式是一种强大的模式匹配工具，在解析正则表达式时，也需要考虑括号的匹配。括号可以用来分组和捕获匹配的内容，因此在解析正则表达式时，需要确保括号的正确闭合，以保证模式匹配的准确性。
下面是一个简单的正则表达式解析算法示例，它可以解析包含括号、字符集合和通配符的正则表达式。
#include <iostream> #include <stack> #include <string> using namespace std; class RegularExpressionParser { public: bool isMatch(string s, string p) { return isMatchHelper(s, p, 0, 0); } private: bool isMatchHelper(string& s, string& p, int sIndex, int pIndex) { if (pIndex == p.length()) { return sIndex == s.length(); } if (pIndex + 1 < p.length() && p[pIndex + 1] == '*') { if (isMatchHelper(s, p, sIndex, pIndex + 2)) { return true; // 匹配0次 } while (sIndex < s.length() && (s[sIndex] == p[pIndex] || p[pIndex] == '.')) { if (isMatchHelper(s, p, sIndex + 1, pIndex + 2)) { return true; // 匹配1次或多次 } sIndex++; } } else if (sIndex < s.length() && (s[sIndex] == p[pIndex] || p[pIndex] == '.')) { return isMatchHelper(s, p, sIndex + 1, pIndex + 1); // 精确匹配 } return false; } }; int main() { RegularExpressionParser parser; string s = "mississippi"; string p = "mis*is*p*."; cout << "String: " << s << endl; cout << "Pattern: " << p << endl; cout << "Is Match: " << boolalpha << parser.isMatch(s, p) << endl; return 0; }
这个算法采用递归的方式处理正则表达式的匹配过程。它可以处理通配符 . 和 *，其中 . 可以匹配任意字符，* 表示前一个字符可以出现零次或多次。
- 括号匹配的优化：
在实际开发中，我们可以对括号匹配算法进行优化。例如，可以通过使用哈希表来存储左右括号的对应关系，这样可以提高查找速度。此外，还可以通过使用位运算或其他技巧来减少空间复杂度。
下面是一个括号匹配优化的算法示例，它使用了哈希表来存储左右括号的对应关系，以提高查找速度。
#include <iostream> #include <stack> #include <unordered_map> #include <string> using namespace std; class BracketMatcher { public: bool isBracketValid(string s) { stack<char> brackets; unordered_map<char, char> bracketPairs = {{')', '('}, {']', '['}, {'}', '{'}}; for (char c : s) { if (bracketPairs.find(c) != bracketPairs.end()) { // 右括号 if (brackets.empty() || brackets.top() != bracketPairs[c]) { return false; // 括号不匹配 } brackets.pop(); } else if (bracketPairs.find(c) == bracketPairs.end()) { // 左括号 brackets.push(c); } } return brackets.empty(); // 所有左括号都匹配了 } }; int main() { BracketMatcher matcher; string s1 = "()[]{}"; string s2 = "([)]"; cout << boolalpha; // 输出true/false而不是1/0 cout << matcher.isBracketValid(s1) << endl; // 输出true cout << matcher.isBracketValid(s2) << endl; // 输出false return 0; }
这个算法与之前的括号匹配算法类似，但是使用了哈希表存储左右括号的对应关系。这样，可以在 O(1) 的时间复杂度内找到对应的右括号，从而提高了算法的效率。
