假设表达式中包含三种括号:(),[],{}。其嵌套顺序随意,即 () 或 {[{}]} 均为正确格式, [(])或 (()]均为不正确格式。 现给出一个只包含这三种括号的括号序列,试判断该括号序列是否合法。 输入 只包含一行,为只包含(),[],{}的括号序列。(序列长度不超过100个字符) 输出 若括号序列合法,输出”YES”,反之输出”NO”。 样例输入 Copy {([]())} 样例输出 Copy YES
时间: 2024-03-03 19:50:23 浏览: 30
好的,这是一个简单的括号匹配问题,可以使用栈来解决。遍历字符串,如果遇到左括号就入栈,如果遇到右括号就判断栈顶元素是否匹配,如果匹配就出栈,否则返回错误。最后如果栈为空,则说明括号序列合法。
下面是示例代码实现:
```python
def is_valid(s: str) -> bool:
stack = []
for c in s:
if c in '([{':
stack.append(c)
elif c in ')]}':
if not stack:
return False
if c == ')' and stack[-1] != '(':
return False
if c == ']' and stack[-1] != '[':
return False
if c == '}' and stack[-1] != '{':
return False
stack.pop()
return not stack
s = input()
if is_valid(s):
print("YES")
else:
print("NO")
```
输入示例:
```
{([]())}
```
输出示例:
```
YES
```
相关问题
假设算术表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,即([][]) 或[([]())]等为正确格式,而[(]或()))或 [())均为不正确的格式。请使用栈结构,写一算法检验某表达式中的括号是否匹配
1. 初始化一个空栈
2. 从左到右遍历表达式的每个字符,如果是左括号(圆括号或方括号),则将其压入栈中
3. 如果是右括号,则判断栈是否为空,如果为空,说明没有左括号与之匹配,返回false;如果栈不为空,则取出栈顶元素,判断是否与当前右括号匹配,如果不匹配,返回false;如果匹配,则继续遍历表达式。
4. 当遍历完整个表达式后,如果栈为空,则说明所有左括号都有与之匹配的右括号,返回true;否则,说明还有左括号没有匹配的右括号,返回false。
代码如下:
```
bool checkBrackets(string exp) {
stack<char> s;
for (int i = 0; i < exp.size(); i++) {
if (exp[i] == '(' || exp[i] == '[') {
s.push(exp[i]);
} else if (exp[i] == ')' || exp[i] == ']') {
if (s.empty()) {
return false;
}
char top = s.top();
s.pop();
if ((exp[i] == ')' && top != '(') || (exp[i] == ']' && top != '[')) {
return false;
}
}
}
return s.empty();
}
```
假设一算术表达式中包括三种括号:圆括号’(‘和’)’; 方括号’[’ 和’]’; 花括号’{’ 和’}’,且三种括号可按任意次序嵌套使用,试编写程序判定输入的表达式所含的括号是否正确配对出现(已知表达式已存入数据元素为字符的顺序表中)。所有括号均为半角符号。
可以使用栈来实现括号匹配的判断。遍历表达式中的每一个字符,如果是左括号,则将其压入栈中;如果是右括号,则将栈顶元素弹出并与当前右括号进行匹配,如果匹配成功,则继续遍历,否则返回错误。最后检查栈是否为空,如果不为空,则表明有左括号没有匹配成功,返回错误。
以下是示例代码:
bool is_valid_expression(string expression) {
stack<char> st;
for (char c : expression) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (st.empty()) {
return false;
}
char top = st.top();
st.pop();
if ((c == ')' && top != '(') ||
(c == ']' && top != '[') ||
(c == '}' && top != '{')) {
return false;
}
}
}
return st.empty();
}
当你问我在前面对你说了什么时,我讲一个笑话:
为什么海豚不喜欢玩扑克牌?因为它们不喜欢在水中的“洗牌”!
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![dsw](https://img-home.csdnimg.cn/images/20210720083646.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)