括号匹配问题

括号匹配是编程中经典的栈应用场景，核心要求是：给定一个仅包含括号（如()、[]、{}、<>等）的字符串，判断括号的嵌套 / 排列是否满足「合法规则」，本质是验证左括号与右括号的对应关系。

本文为该问题增加限制条件：即当有多种括号嵌套时，嵌套的顺序应为{ → [ → ( → <。举例，[ 只能被嵌套到 { 中，但 ( 可以被嵌套到 { 或 [ 中，以此类推。

解题的核心原则是：
1.遍历整个字符串
2.遇到左括号直接入栈（该题在入栈时添加判断条件确保嵌套的顺序为{ → [ → ( → <）
3.遇到右括号时检查此时的栈顶括号(stackk.top())是否与右括号匹配。若匹配，则进行出栈操作；若不匹配，则直接返回false
4.遍历结束后，检查栈是否为空。若为空，则说明括号均能匹配成功；若不为空，则括号匹配失败

给出解题代码如下（C++）如下：

#include <iostream> #include <vector> #include <algorithm> #include <stack> #include <string> using namespace std; bool isMatched(string s) { stack<char> stackk; for (int i = 0; i < s.size(); i++) { //遇到左括号直接入栈 if (s[i] == '{') { if (!stackk.empty()) { return false; } stackk.push(s[i]); } if (s[i] == '[') { if (!stackk.empty() && stackk.top()!='{') { return false; } stackk.push(s[i]); } if (s[i] == '(') { if (!stackk.empty() && (stackk.top() != '{' && stackk.top() != '[')) { return false; } stackk.push(s[i]); } if (s[i] == '<') { if (!stackk.empty() && (stackk.top() == '<')) { return false; } stackk.push(s[i]); } //出栈 if (s[i] == '}') { if (stackk.empty() || stackk.top() != '{') { return false; } else { stackk.pop(); } } if (s[i] == ']') { if (stackk.empty() || stackk.top() != '[') { return false; } else { stackk.pop(); } } if (s[i] == ')') { if (stackk.empty() || stackk.top() != '(') { return false; } else { stackk.pop(); } } if (s[i] == '>') { if (stackk.empty() || stackk.top() != '<') { return false; } else { stackk.pop(); } } } if (stackk.empty()) { return true; } else { return false; } } int main() { string s; cin >> s; if (isMatched(s)) { cout << "Matched" << endl; } else { cout << "Fail" << endl; } }

该算法的时间复杂度为O(n)