括号匹配算法的数据结构程序
时间: 2024-05-28 15:05:54 浏览: 12
括号匹配算法是一种常见的算法,用于检查一个字符串中的括号是否匹配。下面是一个简单的括号匹配算法的示例程序:
```python
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
else:
return None
def is_empty(self):
return len(self.stack) == 0
def top(self):
if not self.is_empty():
return self.stack[-1]
else:
return None
def is_parentheses_matched(expression):
stack = Stack()
opening_brackets = ['(', '[', '{']
closing_brackets = [')', ']', '}']
for char in expression:
if char in opening_brackets:
stack.push(char)
elif char in closing_brackets:
if stack.is_empty():
return False
top_char = stack.pop()
if opening_brackets.index(top_char) != closing_brackets.index(char):
return False
return stack.is_empty()
# 测试括号匹配算法
expression = input("请输入一个带括号的表达式:")
if is_parentheses_matched(expression):
print("括号匹配成功!")
else:
print("括号匹配失败!")
```
这个程序使用了栈这种数据结构来实现括号匹配。它遍历输入的表达式,当遇到左括号时,将其压入栈中;当遇到右括号时,从栈中弹出一个元素,并检查弹出的左括号与当前右括号是否匹配。如果匹配,则继续遍历;如果不匹配或者栈为空,则括号匹配失败。