问题描述
C 栈问题，括号匹配问题求解，无法AC，求指教！ 【题目描述】 设有一字符串中有三种括号：()，[]，{}；忽略不看其他字符，判断这些括号的匹配情况是否成立。例如：“(([()])){}”是匹配的，而“([)]”则是不匹配的。 【输入格式】 只有一行且只有一个数据：一串以“@”为结束符的字符串。字符串长度不会超过20000 【输出格式】 只有一行且只有一个数据：如果是匹配的，则输出：“OK!”，否则输出第一个不相匹配的括号位置（输入数据保证相同类型的左右括号个数相等）。 【输入样例 】 82u(idkj[kdk]js{ksf(k[sk)k])o}i@ 【输出样例】 25
代码分析
首先读入以@结尾的字符串：
代码语言：javascript复制string s;
getline(cin, s, '@');接着定义一个pair类型的栈，用来存储左括号及其位置：
代码语言：javascript复制stack<pair<char, int>> stk;然后遍历字符串中的每个字符，在遍历过程中，如果是左括号，则将其加入栈中，如果是右括号，则弹出栈顶元素进行比较，如果不匹配则输出位置，匹配则弹出栈顶元素：
代码语言：javascript复制for (int i = 0; i < s.size(); i ) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') { // 左括号入栈
stk.push({s[i],i}); // 这里记录了左括号位置
} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') { // 右括号出栈比较
if (stk.empty() || !isMatch(stk.top().first, s[i])) { // 不匹配
cout << i << endl;
return 0;
} else { // 匹配，弹出左括号
stk.pop();
}
}
}isMatch函数判断两个括号是否匹配，这里使用了逻辑运算符的短路性质来判断：
代码语言：javascript复制bool isMatch(char left, char right) {
return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
}最后，如果遍历完字符串之后，栈中还有元素，则说明不匹配，输出栈顶元素的位置，否则输出"OK!"表示匹配：
代码语言：javascript复制if (!stk.empty()) {
cout << stk.top().second << endl;
} else {
cout << "OK!" << endl;
}代码比较简洁明了，这样就能够实现括号匹配的功能。
完整代码
代码语言：javascript复制#include <iostream>
#include <stack>
using namespace std;
bool isMatch(char left, char right) {
return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}');
}
int main() {
string s;
getline(cin, s, '@'); // 读入以@结尾的字符串
stack<pair<char, int>> stk; // 使用pair记录括号类型和位置
for (int i = 0; i < s.size(); i ) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') { // 左括号入栈
stk.push({s[i],i});
} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') { // 右括号出栈比较
if (stk.empty() || !isMatch(stk.top().first, s[i])) { // 不匹配
cout << i << endl;
return 0;
} else { // 匹配，弹出左括号
stk.pop();
}
}
}
// 遍历完字符串后，栈中还有元素说明不匹配
if (!stk.empty()) {
cout << stk.top().second << endl;
} else {
cout << "OK!" << endl;
}
return 0;
}
