设计算法判断一个算术表达式的圆括号是否正确配对。 提示:对表达式进行扫描,凡遇‘(’就入栈,遇‘)’就将栈顶元素‘(’出栈;表达式被扫描完毕,栈应为空。数据结构的代码 加上主函数
时间: 2024-11-04 22:11:12 浏览: 10
在编写算法来判断一个算术表达式的圆括号是否正确配对时,我们可以使用栈这个数据结构。栈是一种后进先出(LIFO)的数据结构,非常适合处理这种需要匹配的场景。以下是Python的一个示例代码:
```python
def is_valid_brackets(expression):
stack = []
opening_brackets = ['(', '[', '{']
closing_brackets = [')', ']', '}']
for char in expression:
if char in opening_brackets:
stack.append(char)
elif char in closing_brackets:
if not stack or stack.pop() != opening_brackets[closing_brackets.index(char)]:
return False
return len(stack) == 0 # 如果栈为空,说明所有括号都已配对
# 主函数示例
def main():
test_cases = ["()", "({})", "([{}])", ")(", "[)]", "{)}"]
for case in test_cases:
print(f"Expression {case}: Balanced (True/False) = {is_valid_brackets(case)}")
if __name__ == "__main__":
main()
```
在这个代码中,我们遍历输入的表达式,遇到开括号就压入栈中,遇到闭括号时检查栈顶是否有对应的开括号,如果有则弹出并继续检查下一个闭括号,如果没有或者栈空,则表示不匹配。最后,如果栈为空,意味着所有的括号都找到了正确的匹配,返回`True`,否则返回`False`。
阅读全文