假设一个表达式有小写英文字母、运算符+,-,∗,/和左右小(圆)括号构成,以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配,若匹配,则返回“YES”;否则返回“NO”。表达式长度小于300,左圆括号少于25个。
时间: 2024-09-21 10:06:10 浏览: 45
为了检查给定的表达式中的括号是否匹配,你可以使用栈数据结构。栈是一种后进先出(LIFO)的数据结构,非常适合处理这类问题,因为当我们遇到左括号时,就将其压入栈中,当遇到右括号时,我们检查栈顶元素是否与其相配对,如果匹配则弹出,如果不匹配则返回"NO"。
以下是Python中一种简单的解决方案:
```python
def is_valid_expression(expression):
stack = []
brackets_map = {')': '(', '}': '{', ']': '['}
for char in expression:
if char.isalpha() or char.isdigit(): # 这里仅考虑字母和数字,其他字符视为非括号
continue
if char in brackets_map:
if not stack or stack[-1] != brackets_map[char]:
return "NO"
else:
stack.pop()
elif char == '@':
break # 表达式结束,检查剩余的栈是否为空
else:
return "NO"
# 如果还有未匹配的左括号,返回"NO"
return "YES" if not stack else "NO"
```
这个函数会遍历输入的表达式,对于每个字符,判断其是否是括号,并相应地操作栈。当遇到结束符’@’时,表示已经检查完整个表达式,如果没有剩余的左括号在栈中,说明括号匹配,返回"YES",否则返回"NO"。
阅读全文