Blog of CodeJELLOW’S ENGINEERING NOTES
← 返回文章

括号匹配算法

给定仅包含“()[]{}”六种括号的字符串,请你判断该字符串中,括号的匹配是否是合法的,也就是对应括号的数量、嵌套顺序完全正确。

本文目录 ⌄

    括号匹配算法很经典,这个题解十分简洁。

    给定仅包含“()[]{}”六种括号的字符串,请你判断该字符串中,括号的匹配是否是合法的,也就是对应括号的数量、嵌套顺序完全正确。

    输入格式:

    第一行一个整数T(T<=10)

    其后T行每行一个字符串只包含[{()}]六种字符(字符串长度2e5以内)

    输出格式:

    对于每个字符串,匹配输出Yes,否则输出No

    输入样例:

    TEXT
    2
    {()[]}
    ([)]
    

    输出样例:

    TEXT
    Yes
    No
    

    题解

    还是利用栈

    TEXT
    /*
      1.建立栈,左括号压入,同时压入对应的右括号
      2.遇到右括号弹出,看是否与栈顶元素匹配
    
    */
    #include <iostream>
    #include <stack>
    #include <vector>
    using namespace std;
    
    int main() {
      vector<bool> ans;
      int n;
      cin >> n;
      string str;
      while (n-- > 0) {
        cin>>str;
        stack<char> sta;
        int length=str.size();
        if(length==0){
          ans.push_back(true);
          continue;
        }
        if(length%2){
          ans.push_back(false);
          continue;
        }
        sta.push(str[0]);  
        for(int i=1;i<length;i++){
          if(sta.empty()){
            sta.push(str[i]);
          }
          if(str[i]-sta.top()==1||str[i]-sta.top()==2){//利用asc2码
            sta.pop();
          }else{
            sta.push(str[i]);
          }
        }
        if(sta.empty()){
          ans.push_back(true);
        }else{
          ans.push_back(false);
        }
      }
    //控制输出,pta要求输出比较麻烦
      bool flag = true;
      for(bool out:ans){
        if(flag==true){
          if(out==1){
            cout<<"Yes";
          }else{
            cout<<"No";
          }
          flag=false;
        }else{
          if(out==1){
            cout<<endl<<"Yes";
          }else{
            cout<<endl<<"No";
          }
        }
      }
      system("pause");
    }

    使用asc2码检测括号是否匹配很方便,因为回括号和括号之间的asc2码只差了2或1

    小技巧get,核心算法其实只有一点,但不得不吐槽pta要素过多,把核心算法提出来不好吗。。。

    TEXT
        cin>>str;
        stack<char> sta;
        int length=str.size();
        if(length==0){
          ans.push_back(true);
          continue;
        }
        if(length%2){
          ans.push_back(false);
          continue;
        }
        sta.push(str[0]);  
        for(int i=1;i<length;i++){
          if(sta.empty()){
            sta.push(str[i]);
          }
          if(str[i]-sta.top()==1||str[i]-sta.top()==2){//利用asc2码
            sta.pop();
          }else{
            sta.push(str[i]);
          }
        }
        if(sta.empty()){
          ans.push_back(true);
        }else{
          ans.push_back(false);
        }

    还有更简化的方式

    TEXT
    bool isValid(string str) {
         stack<char> sta;
        if (str.length() % 2) {
          return false;
        }
        for (int i = 0; i < str.size(); i++) {
          if (sta.empty()) {
            sta.push(str[i]);
          } else if (str[i] - sta.top() == 1 || str[i] - sta.top() == 2) {
            sta.pop();
          }else{
            sta.push(str[i]);
          }
          
        }
          return sta.empty();
      }


    通过 RSS 订阅更新 →