括号序列【第十二届】【省赛】【b组】
时间: 2023-04-20 21:01:32 浏览: 68
括号序列是由一些左括号和右括号组成的序列,其中左括号和右括号要成对出现,且左括号必须在右括号之前闭合。例如,"()"、"()()"、"(())"、"(()())"等都是合法的括号序列,而")("、"())"、"(()"等则不是合法的括号序列。在这道题目中,我们需要判断给定的括号序列是否合法,如果合法则输出"YES",否则输出"NO"。
相关问题
试题 历届真题 括号序列【第十二届】【省赛】【b组】
括号序列问题是一个经典的计算机算法问题,其目的是判断一个给定的括号序列是否合法。在这道题目中,我们需要实现一个程序,判断一个由左右括号组成的字符串是否为合法的括号序列。
具体来说,合法的括号序列需要满足以下条件:
1. 左右括号必须成对出现,即每个左括号都必须有一个对应的右括号。
2. 左右括号的顺序必须正确,即每个左括号必须先于其对应的右括号出现。
3. 括号序列中不能出现嵌套的括号,即一个左括号不能包含另一个左括号或右括号。
为了解决这个问题,我们可以使用栈这种数据结构来实现。具体来说,我们可以遍历字符串中的每个字符,如果当前字符是左括号,则将其压入栈中;如果当前字符是右括号,则从栈中弹出一个左括号,判断其是否与当前右括号匹配。如果栈为空或弹出的左括号与当前右括号不匹配,则说明括号序列不合法。
以下是一个示例代码,用于判断一个字符串是否为合法的括号序列:
```
#include <iostream>
#include <stack>
using namespace std;
bool isValid(string s) {
stack<char> st;
for (int i = ; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
st.push(s[i]);
} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
if (st.empty()) {
return false;
}
char c = st.top();
st.pop();
if ((s[i] == ')' && c != '(') || (s[i] == ']' && c != '[') || (s[i] == '}' && c != '{')) {
return false;
}
}
}
return st.empty();
}
int main() {
string s;
cin >> s;
if (isValid(s)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return ;
}
```
在这个示例代码中,我们使用了一个栈来存储左括号,遇到右括号时从栈中弹出一个左括号进行匹配。如果栈为空或弹出的左括号与当前右括号不匹配,则说明括号序列不合法。最后,如果栈为空,则说明括号序列合法。
试题 历届真题 括号序列【第十二届】【省赛】java
题目描述
给定一个长度为 $2n$ 的括号序列 $S$ ,请你判断这是不是一个合法的括号序列。合法的括号序列定义如下:
- 空串是合法的括号序列。
- 如果 $S$ 是合法的括号序列,那么 $(S)$ 也是合法的括号序列。
- 如果 $S_1$ 和 $S_2$ 都是合法的括号序列,那么 $S_1S_2$ 也是合法的括号序列。
输入格式
第一行输入一个整数 $n(1\le n \le 10^6)$,表示括号序列的长度。
第二行输入一个长度为 $2n$ 的括号序列,序列中只包含 '(', ')' 两种字符。
输出格式
如果输入的括号序列是合法的括号序列,则输出 “YES”,否则输出 “NO”。
数据范围
输入样例1:
2
(())
输出样例1:
YES
输入样例2:
4
()()
输出样例2:
YES
输入样例3:
4
()()))
输出样例3:
NO
Java 代码
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)