栈在括号匹配中的应用是如何实现的？

本文共计803个文字，预计阅读时间需要4分钟。

题目：设计算法，检测一个通过键盘输入的表达式中是否只出现括号（）和[]，并允许任意顺序的嵌套。

思路：当读取到一个左括号时，产生一个匹配的意愿，若再读取到右括号，则检查是否有一个未使用的匹配的意愿，如果有，则使用它，否则表达式中存在不匹配的括号。重复此过程，直到读取完整个表达式。如果所有左括号都有对应的右括号，则表达式中括号匹配；否则，不匹配。

例题：假设通过键盘输入的一个表达式中只出现()和[]并允许任意顺序的嵌套，设计算法，检测括号是否匹配。

思路：当读取到一个左括号时，将产生一个“匹配的意愿”，若再读取到一个左括号，又将产生一个“匹配的意愿”，且后读取到的比先读取到的“匹配的意愿更强烈”

因此可借助栈，按“意愿强烈的优先级” 保存所有未匹配的左括号，即读到左括号即入栈。

当遇到右括号时，则从栈中弹出左括号，检验匹配情况。

( ) [ ] 的ASCII码分别为40、41、91、93

在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。