括号匹配问题（栈的运用）

悠悠 2022-01-30 09:04 207阅读 0赞

### 栈的运用以及STL stack的用法 ###

#### 题目描述： ####

在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$“标注,不能匹配的右括号用”?"标注。

#### 题意： ####

*  字符串匹配，如果 ‘（’ 有 ‘）’ 与其匹配，则匹配的两个位置都用空格 ’ ’ 标注
 *  出现除左右括号外的其他字符，则用空格 ’ ’ 标注
 *  当左括号 ‘（’ 没有右括号 ‘）’ 与其匹配，则用 ‘$’ 标注
 *  相反，当右括号 ‘）’ 没有左括号 ‘（’ 与其匹配，则用 ’？‘ 标注
 *  且匹配中任何一个左括号 ’（‘ 都与在它右边且距离 **最近** 的右括号 ’（‘ 匹配。
 *  最后输出这一行标注即可；

#### 解法： ####

*  栈的模拟

#include<bits/stdc++.h>
    using namespace std;
    
    stack<int>st;
    char a[120];
    
    int main(){ 
    
        string s;
        while(getline(cin,s)) {  
        
            memset(a,0,sizeof(a));
            while(!st.empty()) st.pop();  //初始化操作，把栈与标注数组都清空；
            
            int i;
            for(i=0; i<s.length(); i++) {  //开始匹配
                if(s[i]=='('){         //遇到左括号，入栈
                    st.push(i);       //注意：这里是把左括号的位置入栈
                    a[i]=' ';         //先将左括号的位置都标注为空格' '
                }
                else if(s[i]==')'){    //遇到右括号
                    if(!st.empty()){   //如果栈不为空，说明会有左括号与其匹配
                        st.pop();	  //出栈，这个地方出栈，说明栈内这个位置的左括号匹配了
                        a[i]=' ';     //这里匹配了就把这个位置标注为空格' '
                    }
                    else a[i]='?';    //反之，栈为空，说明没有左括号与其匹配，就将这个位置标注为'?'
                }
                else a[i]=' ';    //遇到其他字符是都标注为空格' '
            }
            while(!st.empty()){    //注意：当栈不为空时，说明有左括号没有被匹配
                a[st.top()]='$';  //这里我们就把没有匹配的左括号的位置标注为'$'
                st.pop();         
            }
            
            cout<<s<<endl;
            for(int j=0;j<i;j++){ 
                printf("%c",a[j]);
            }
            printf("\n");
        }
    }

#### C++ stack 用法介绍 ####

C++的 stack 在 stack头文件中 ，它是一个封装了栈的结构。具体栈的实现可以点开 [这里][Link 1] ——也就是说实现了一个先进后出（***FILO***）的数据结构

##### 常用函数： #####

<table> 
 <thead> 
  <tr> 
   <th align="center">函数</th> 
   <th align="center">功能</th> 
   <th align="center">复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">b.size()</td> 
   <td align="center">返回栈的元素数</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td align="center">top()</td> 
   <td align="center">返回栈顶的元素</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td align="center">pop()</td> 
   <td align="center">从栈顶取出并删除元素</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td align="center">push(x)</td> 
   <td align="center">向栈中添加元素x</td> 
   <td align="center">O(1)</td> 
  </tr> 
  <tr> 
   <td align="center">empty()</td> 
   <td align="center">在栈为空时返回true</td> 
   <td align="center">O(1)</td> 
  </tr> 
 </tbody> 
</table>

#include<iostream>
    #include<stack>
    using namespace std;
    
    
    int main(){ 
    
        stack<int> st;
        st.push(1);
        st.push(2);
        st.push(3);
        cout << st.size() << endl;     // 3
    
        cout << st.top() << endl;      // 3
        st.pop();
    
        cout << st.empty() << endl;      // false
        st.pop();
    	st.pop();
    
        cout << st.empty() << endl;      // true
        return 0;
    }

[Link 1]: https://blog.csdn.net/weixin_43054397/article/details/84112957