问题描述
C++栈问题，括号匹配问题求解，无法AC，求指教！
【题目描述】
设有一字符串中有三种括号：()，[]，{}；忽略不看其他字符，判断这些括号的匹配情况是否成立。例如：“(([()])){}”是匹配的，而“([)]”则是不匹配的。
【输入格式】
只有一行且只有一个数据：一串以“@”为结束符的字符串。字符串长度不会超过20000
【输出格式】
只有一行且只有一个数据：如果是匹配的，则输出：“OK!”，否则输出第一个不相匹配的括号位置（输入数据保证相同类型的左右括号个数相等）。
【输入样例 】
82u(idkj[kdk]js{ksf(k[sk)k])o}i@
【输出样例】
25
代码分析
首先读入以@结尾的字符串：
string s; getline(cin, s, '@');
接着定义一个pair类型的栈，用来存储左括号及其位置：
stack<pair<char, int>> st
然后遍历字符串中的每个字符，在遍历过程中，如果是左括号，则将其加入栈中，如果是右括号，则弹出栈顶元素进行比较，如果不匹配则输出位置，匹配则弹出栈顶元素：
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函数判断两个括号是否匹配，这里使用了逻辑运算符的短路性质来判断：
bool isMatch(char left, char right) { return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}'); }
最后，如果遍历完字符串之后，栈中还有元素，则说明不匹配，输出栈顶元素的位置，否则输出"OK!"表示匹配：
if (!stk.empty()) { cout << stk.top().second << endl; } else { cout << "OK!" << endl; }
代码比较简洁明了，这样就能够实现括号匹配的功能。
完整代码
#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; }
![【简单项目实战】用C++实现学生成绩管理系统 | [面向对象]（二）](https://ucc.alicdn.com/images/user-upload-01/df130d5c305b428e82db3759470b0f29.png?x-oss-process=image/resize,h_160,m_lfit)
