采用栈的顺序存储表示,编程实现表达式中圆括号“( )”和方括号“[ ]”匹配的检验。
时间: 2024-10-12 17:07:31 浏览: 31
数据结构课程设计广义表的括号匹配
为了检查表达式中的圆括号和方括号是否匹配,我们可以使用两个栈的数据结构,一个用于存储左括号(()[]),另一个用于存储右括号。遍历输入表达式的每个字符,按照以下规则进行操作:
1. 如果遇到左括号('(' 或 '['),将其压入第一个栈。
2. 如果遇到右括号(')' 或 ']'),检查当前的第一个栈是否为空。如果不空,则弹出栈顶元素并与当前右括号进行比较:
- 如果是相匹配的左括号(如 ')' 对应 '(',']' 对应 '['),则继续处理下一个字符;
- 否则,说明不匹配,返回false。
3. 如果遍历到表达式结束,而第二个栈非空,说明还有未配对的左括号,返回false。
以下是使用 Python 编程的一个简单示例实现这个功能:
```python
def is_matching_brackets(expression):
left_parens = ['(', '[']
right_parens = [')', ']']
stack = []
for char in expression:
if char in left_parens:
stack.append(char)
elif char in right_parens:
if not stack or stack.pop() != left_parens[right_parens.index(char)]:
return False
return len(stack) == 0
# 测试
expression1 = "([{}])" # 匹配
expression2 = "[({})]" # 匹配
expression3 = "([)]" # 不匹配
expression4 = "[{)]" # 不匹配
print(is_matching_brackets(expression1)) # 输出: True
print(is_matching_brackets(expression2))
阅读全文