栈 (Stack) 的使用

本文用 “括号匹配问题” 来了解栈 (Stack) 的使用,不涉及栈的具体实现。(如果没有特殊的标注,本文代码语法基本符合C++11标准)

题目描述:

现在,有一行括号序列,请你检查这行括号是否配对。

输入描述:

第一行输入一个数N(0<N<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有”[“, “]”, “(“, “)” 四种字符

输出描述:

每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No

样例输入:

1
2
3
4
3
[(])
(])
([[]()])

样例输出:

1
2
3
No
No
Yes

题目地址 - NYOJ002

题目分析

通过观察 ([[]()]) 这组数据我们不难发现,如果这个长序列的括号数量是奇数,那么他一定是失配的。

如果当前的括号序列是匹配的,那么相应的一种类型的左括号是必须对应一个该类型的右括号,并且他们的位置也应该是左括号在左,右括号在右,)( 这种是不行的。现在问题就变成了 我如何从这样的一个括号序列中逐个把每组匹配的括号找出来呢。

使用栈这种数据结构来解决。

栈时一种特殊的线性表,并且只能在线性表的一端进行操作,我们称之为栈顶(top),无法对栈底元素进行操作。栈具有LIFO(last-in first-out)的特性。

我们可以这样来操作,如果当前字符是左括号,那么我们就对他进行入栈操作,是右括号,那我们就拿他和栈顶元素进行比较,同一类型则弹出栈顶元素,继续判断下一个括号。不是同一类型,则失配。退出匹配。

如果该组数据的括号全部是匹配的,那么匹配结束后栈应该是空的。但是,考虑到特殊情况(匹配过程中没有元素入栈),我们还需要一个flag标志来保证匹配过程中是否失配。

下面是具体的代码实现,做题的时候现写的代码,也没有整理过,所以代码逻辑可能会有些混乱。emmmm,不排除还会有些冗余的条件判断。仅作参考,有虫子及时拍砖我。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
int main(int argc, char** argv) {
int n;
cin>>n;
while(n--) {
string s;
cin>>s;
bool flag=true;
stack<char>str; //创建一个char类型的栈
if(s.size()%2) {
flag=false; //判断长度是否为奇数
}
for(int i=0; i<s.size(); i++) {
if(s[i]=='('||s[i]=='[') {
str.push(s[i]);
continue;
//遇到左括号入栈,继续判断下一个
} else if(s[i]==')') {
if(str.empty()) {
flag=false; //空栈遇到右括号匹配结束
break;
}
char p=str.top();
if(p=='(') { //遇到右括号栈顶为左括号
str.pop(); //栈顶出栈
continue;
} else {
flag=false;
break;
}
} else if(s[i]==']') { //第二种括号类型判断
if(str.empty()) {
flag=false;
break;
}
char p=str.top();
if(p=='[') {
str.pop();
continue;
} else {
flag=false;
break;
}
}
}
if(flag&&str.empty()) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
}
return 0;
}
Author: Junzhou Liu
Link: https://liujunzhou.top/2019/1/15/stack/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
AliPay
WechatPay