首页 > 代码库 > 括号匹配的栈实现
括号匹配的栈实现
括号匹配的栈实现
问题：判断一个文本中，括号是否匹配？
思路：从头到尾扫描字符串，每次遇到左括号（如‘(‘, ‘[‘, ‘{‘）就压入堆栈，如果遇到右括号（如‘)‘, ‘]‘, ‘}‘）就与栈顶元素比较，如果成对，OK，否则判断不匹配。
代码如下：
#include <iostream>#include <stack>#include <set>#include <string>using namespace std;/* * vaild return true, else return false */bool judge_bracket(const string & str){ stack<char> st; set<char> left; set<char> right; left.insert(‘(‘); left.insert(‘[‘); left.insert(‘{‘); right.insert(‘)‘); right.insert(‘]‘); right.insert(‘}‘); for (int i=0; i!=str.size(); i++) { set<char>::iterator it1 = left.find(str[i]); set<char>::iterator it2 = right.find(str[i]); if (it1 != left.end()) { // match left st.push(str[i]); } else if (it2 != right.end()) { // match right if (st.size() == 0 ) return false; // stack is empty if (str[i] - st.top() <= 2 ) { // 右括号的ASCII码比其成对的左括号大1或2 st.pop(); } else { cout << "str[i]=" << str[i] << "top=" << st.top() <<endl; return false; } } } return true;}int main(int argc, char* argv[]){ string test_buffer[5] = {"]({[", "({[]})","([)]{}","(()[{}])","{[((()))]([])}"}; //test for (int i=0; i<5; i++) { cout << "The string is \"" << test_buffer[i] << "\", The result is " << (judge_bracket(test_buffer[i]) ? "matched" : "not matched" ) << endl; } return 0;}
括号匹配的栈实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。