字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是<>,(),[],{},例如。输入: [()] 输出:YES,而输入([]),([)]都应该输出NO。
时间: 2023-11-25 12:45:17 浏览: 47
可以使用栈来解决这个问题。遍历字符串,如果遇到左括号就将其入栈,如果遇到右括号就将栈顶元素出栈并判断是否匹配。如果匹配则继续遍历,否则返回 no。
具体实现可以参考以下代码:
def is_match(s):
stack = []
for c in s:
if c in '([{<':
stack.append(c)
elif c in ')]}>':
if not stack:
return 'no'
top = stack.pop()
if (c == ')' and top != '(') or \
(c == ']' and top != '[') or \
(c == '}' and top != '{') or \
(c == '>' and top != '<'):
return 'no'
if stack:
return 'no'
return 'yes'
输入字符串 s,调用 is_match(s) 即可得到匹配结果。
相关问题
字符串中只含有括号+(),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是<>,(),[],{},例如。输入:+[()]+输出+YES,而输入([]),([)
以下是Python判断字符串中括号是否匹配的代码:
```python
def is_valid(s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
# 测试
print(is_valid("([])"))
print(is_valid("([)]"))
print(is_valid("+[()]+"))
```
输出:
```
True
False
True
```
代码思路:
1. 定义一个栈stack和一个映射mapping,映射中存储右括号和左括号的对应关系。
2. 遍历字符串中的每个字符char,如果char是右括号,则从栈顶弹出一个元素top_element,如果栈为空则将top_element赋值为'#'。如果mapping[char]不等于top_element,则说明括号不匹配,返回False。
3. 如果char是左括号,则将其压入栈中。
4. 遍历完字符串后,如果栈为空,则说明所有括号都匹配,返回True;否则返回False。
字符串中只含有括号 (),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是<>,(),[],{},例如。输入: [()] 输出:YES,而输入([]), ([])都应该输出NO。
这是一个经典的栈的应用。我们需要用到一个栈来维护左括号,遇到左括号就将其压入栈中,遇到右括号就判断其是否与栈顶的左括号匹配,如果匹配则将栈顶的左括号出栈,继续遍历字符串;如果不匹配则说明括号不匹配,直接返回NO。最后如果栈为空,则说明所有左括号都有与之匹配的右括号,返回YES,否则返回NO。
但是本题有一个限制条件,就是括号有互相包含的形式,从内到外必须是<>,(),[],{},因此我们需要对栈的操作进行修改。具体来说,每当遇到左括号时,我们首先将其与栈中的上一个元素进行匹配,如果可以匹配则将两个元素一起压入栈中,否则只将当前左括号压入栈中。当遇到右括号时,我们取出栈顶的元素,如果其与当前右括号匹配,则继续遍历字符串;否则说明括号不匹配,直接返回NO。最后如果栈为空,则说明所有左括号都有与之匹配的右括号,返回YES,否则返回NO。
以下是代码实现(Python):
```python
def is_valid(s: str) -> bool:
stack = []
mapping = {')': '(', ']': '[', '}': '{', '>': '<'}
for char in s:
if char in mapping.values():
if stack and stack[-1] in mapping.keys() and mapping[char] == stack[-1]:
stack.pop()
stack.append(char+mapping[char])
else:
stack.append(char)
elif char in mapping.keys():
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
return not stack
```
时间复杂度为O(n),空间复杂度为O(n)。