括号匹配算法

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

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

输入格式:

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

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

输出格式:

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

输入样例:

2
{()[]}
([)]

输出样例:

Yes
No

题解

还是利用栈

/*
  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要素过多,把核心算法提出来不好吗。。。

    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);
    }

还有更简化的方式

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();
  }


发表评论