例题1——合法的括号串（内含stack总结）1、合法的括号串

56 阅读 0 评论 37 点赞

我是靠谱客的博主单纯冬日，最近开发中收集的这篇文章主要介绍例题1——合法的括号串（内含stack总结）1、合法的括号串，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1、合法的括号串

【问题描述】

一个合法的括号串，是指只包含括号的串，如果满足如下条件：
（1）<> () [] {} 这四对括号是合法的；
（2）如果r是合法括号串，则 ® [r] {r}也是；
（3）如果r，s是合法括号串，则rs也是；
所以<<>> , [<>{}(())],[({<>})]是合法的括号串，而)(,[( ])就不是。

【输入形式】

输入第一行正整数t (10 ≤ n ≤ 100)，表示有多少组测试数据。后面有t行，每行一个只包含8种括号符号的括号串。40%的括号串的长度L 2 ≤ L≤ 20；30%的括号串的长度L 2 ≤ L≤ 200；20%的括号串的长度L 2 ≤ L≤ 2000；10%的括号串的长度L 2 ≤ L≤ 20000；
##【输出形式】对于每组测试数据，如果括号串是合法的，输出“Yes”（输出没有引号）占一行，否则，输出“No”（输出没有引号）占一行。

【样例输入】

6
<<>>
)(
[<>{}(())]
[({<>})]
[(])
<([{

【样例输出】

Yes
No
Yes
Yes
No
No

代码

#include <iostream>
#include <stack>
using namespace std;
int main(){
 string str;
 int n,i=0;
 cin>>n;
 while(n--){
  stack<char>ch;
  cin>>str;
  int len;
  bool flag=true;
  len=str.length();
  for(i=0;i<len;i++){
   if(str[i]=='<'||str[i]=='['||str[i]=='{'||str[i]=='('){
    ch.push(str[i]);
   }else if(str[i]=='>'){
    if(!ch.empty()&&ch.top()=='<'){
     ch.pop();
    }else{
     flag=false;
     break;
    }
   }else if(str[i]=='}'){
    if(!ch.empty()&&ch.top()=='{'){
     ch.pop();
    }else{
     flag=false;
     break;
    }
   }else if(str[i]==']'){
    if(!ch.empty()&&ch.top()=='['){
     ch.pop();
    }else{
     flag=false;
     break;
    }
   }else if(str[i]==')'){
    if(!ch.empty()&&ch.top()=='('){
     ch.pop();
    }else{
     flag=false;
     break;
    }
   }
  }
  if(i==len&&flag&&ch.empty()) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
 }
 return 0;
}

知识点来咯！！

一、stack 栈

stack依旧是STL中的容器，重要的是它可以实现先进后出的功能，下面介绍一些他的功能。

1.头文件：#include < stack>

2.stack的定义： stack < typename> name;

<>中是栈中的变量类型，例如：int char······可任意基本数据类型或容器。 name是定义的栈名。

3.stack中的元素访问

stack本身是一种先进后出的数据结构，所以不能像vector一样用下标访问，它只能用top（）访问栈顶元素。
例如：

#include <iostream>
#include <stack> 
using namespace std;
int main(){
 stack<char> ch;
 ch.push('a');
 ch.push('b');
 ch.push('c');
 cout<<ch.top();
 return 0;
}

结果：
在这里结果插入图片描述

4.stack函数

（1）push（x）
向栈推顶加入新元素，可以理解为加入迭代器为0的元素。
（2）pop（x）
栈顶元素出栈，用法与push（x）类似，可以理解为删除栈顶元素。
（3）top（）
访问栈顶元素，返回typename型的元素。
（4）empty（）
返回bool型变量，检测栈是否为空，是空的返回true，否则返回false。
例如：

#include <iostream>
#include <stack> 
using namespace std;
int main(){
 stack<char> ch;
 ch.push('a');
 ch.push('b');
 ch.push('c');
 if(ch.empty()) cout<<"empty"<<endl;
 else cout<<"full"<<endl;
 ch.pop();
 ch.pop();
 ch.pop();
 if(ch.empty()) cout<<"empty"<<endl;
 else cout<<"full"<<endl;
 return 0;
}

结果：
在这里插入图片描述
（5）size（）
返回int型变量，代表栈中元素的个数。
（6）search（）
寻找目标第一个出现的位置距离栈顶的距离，不存在的话返回值为-1。