如何用栈实现括号匹配的长尾？

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

题目：设计算法，检测一个通过键盘输入的表达式中是否包含括号匹配。

思路：当读取到一个左括号时，生成一个匹配的意愿，如果接下来读取到的是右括号，则匹配成功；否则，将匹配的意愿存入栈中。当读取到右括号时，如果栈为空，则表示没有匹配的左括号，匹配失败；如果栈不为空，则弹出栈顶元素，表示当前右括号已经匹配。最后，如果栈为空，则表示所有括号都已正确匹配；如果不为空，则表示存在未匹配的左括号。

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

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

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

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

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

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