栈的运用之括号匹配

Posted on Edited on In

B2165 括号匹配

题目描述

给定只由 $6$ 种括号字符组成的字符串：(, ), [, ], {, }。判断每个字符串是否为“合法括号序列”，合法则输出 YES，否则输出 NO。合法括号序列的定义：

  • 空串合法；
  • 若 A 合法，则 (A), [A], {A} 均合法；
  • 若 A 与 B 均合法，则 AB 合法。

输入格式

第一行一个整数 $T$，表示数据组数。接下来 $T$ 行，每行一个只包含上述 $6$ 种字符的字符串。

输出格式

对于每个字符串，输出一行：

  • 若其为合法括号序列，输出 YES；
  • 否则输出 NO。

输入输出样例 #1

输入 #1

1
2
1
()[]{}

输出 #1

1
YES

输入输出样例 #2

输入 #2

1
2
3
4
5
6
7
6
()
([)]
([]){}
((((
{[()()]}
}{

输出 #2

1
2
3
4
5
6
YES
NO
YES
NO
YES
NO

说明/提示

记单串长度记为 $|S|$。测试数据满足 $1 \leq |S| \leq 10^6$，$1 \leq T \leq 2\times 10^5$，同一输入文件内总长度 $\sum |S| \leq 2\times 10^6$，字符串只包含字符 ()[]{}。

解:

我们知道括号像栈一样，遵循 LIFO(后进先出)

比如:
{{}
第二位{是后进的，那么与之匹配的是第三位的}

那么我们用栈的方式思考，
我们把 左括号 认为是无条件push， 右括号 认为是有条件pop，
条件是栈顶的括号一定和右括号匹配
比如(]不符合规则的

还有其他可能的情况需要注意

比如(((它没有右括号所以也是不符合的，
我们可以判断所有push,pop操作后栈顶下标是否>0，大于则代表栈不为空
比如)))
栈顶下标是否<0，如果是则说明少左括号了

答案

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
#include <bits/stdc++.h>
using namespace std;
char arr[1000000];
int main(){
    int N;
    cin >> N;
    for(int i = 0;i<N;i++){
    	int sz = 0;
        string s;
        cin >> s;
        int f = 0;
        for(int j = 0;j<s.size();j++){
        	if(s[j] == '(' || s[j] == '[' || s[j] == '{'){
        		arr[sz] = s[j];
        		sz++;
        	}
        	else{
        		if(s[j] == ')'){
        			if(arr[sz-1] == '(')sz--;
        			else {
        				f = 1;
        				break;
        			}
        		}
        		else if(s[j] == '}'){
        			if(arr[sz-1] == '{')sz--;
        			else {
        				f = 1;
        				break;
        			}
        		}
        		else if(s[j] == ']'){
        			if(arr[sz-1] == '[')sz--;
        			else {
        				f = 1;
        				break;
        			}
        		}
        	}
        }
        if(f == 1)cout << "NO\n";
        else if(sz > 0)cout << "NO\n";
        else cout << "YES\n";
    }
    return 0;
}