首页 > 代码库 > 括号匹配
括号匹配
题目：如果一个括号序列包含完整的左右括号对（按此顺序），可嵌套的括号，则称为平衡括号序列，如"(())()"、"()"和"(()(()))"是平衡的，而"(()"和"(()))("不是平衡的；
编写一个函数确定给定字符串是否包含平衡括号序列，如果有成对括号序列，则返回成对括号序列的对数，否则返回-1；
百度笔试的一道题，还是比较简单的，就是不知道时间能不能过。
void parentheses(string ss){ stack<int> lefts; int num = 0; if (ss.size() % 2 != 0) { cout << -1; return; } for (int i = 0; i < ss.size(); i++) { if (ss[i] == ‘(‘) { lefts.push(i); } else { if (lefts.empty()) cout << -1; else { lefts.pop(); num++; } } } if (!lefts.empty()) cout << -1; else cout << num;}int main(){ string ss; while (cin >> ss) { parentheses(ss); cout << endl; } return 0;}leetcode上有两道类似的题，不过比这题要难。
第一题如下：
这题的难点在于符号是不一样的，解题的思路也很巧妙：
bool isValid(const string& ss){ string left = "([}"; string right = ")]}"; stack<char> stk; for (auto c : ss) { if (left.find(c) != left.npos) { stk.push(c); } else { if (stk.empty() || stk.top() != left[right.find(c)]) { return false; } stk.pop(); } } if (!stk.empty()) return false; else return true; }第二题要更复杂一些：
int longestValidPar(string ss){ stack<int>lefts; int last = -1; int max_len = 0; for (int i = 0; i < ss.size(); ++i) { if (ss[i] == ‘(‘) { lefts.push(i); } else { if (lefts.empty()) last = i; else { lefts.pop(); if (lefts.empty()) max_len = max(max_len, i - last); else max_len = max(max_len, i - lefts.top()); } } } return max_len;}
括号匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。