括号匹配的栈实现

 

问题：判断一个文本中，括号是否匹配？

思路：从头到尾扫描字符串，每次遇到左括号（如'(', '[', '{'）就压入堆栈，如果遇到右括号（如')', ']', '}'）就与栈顶元素比较，如果成对，OK，否则判断不匹配。

 

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;/* * vaild return true, else return false */bool judge_bracket(const string & str){    stack
         
           st;    set
          
            left; set
           
             right; left.insert('('); left.insert('['); left.insert('{ '); right.insert(')'); right.insert(']'); right.insert('}'); for (int i=0; i!=str.size(); i++) { set
            
             ::iterator it1 = left.find(str[i]); set
             
              ::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() <