假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如（［ ］（））或［（［ ］［ ］）］等为正确的匹配，［（ ]）或（［ ］（ ）或 ( ( ) ) ）均为错误的匹配。
现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？
检验括号是否匹配的方法可用"期待的急迫程度"这个概念来描述。即后出现的"左括弧"，它等待与其匹配的"右括弧"出现的"急迫"心情要比先出现的左括弧高。换句话说，对"左括弧"来说，后出现的比先出现的"优先"等待检验，对"右括弧"来说，每个出现的右括弧要去找在它之前"最后"出现的那个左括弧去匹配。显然，必须将先后出现的左括弧依次保存，为了反映这个优先程度，保存左括弧的结构用栈最合适。这样对出现的右括弧来说，只要"栈顶元素"相匹配即可。如果在栈顶的那个左括弧正好和它匹配，就可将它从栈顶删除。
例如考虑下列括号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号"["只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号"]"的出现，类似地，因等来的是第三个括号"["，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，…，依次类推。
1．来的右括弧非是所"期待"的；
2．来的是"不速之客"；
3．直到结束，也没有到来所"期待"的。
这三种情况对应到栈的操作即为：
1．和栈顶的左括弧不相匹配；
2．栈中并没有左括弧等在哪里；
3．栈中还有左括弧没有等到和它相匹配的右括弧。
在以上分析的基础上就可以写出检验括弧匹配的算法了。
|
|||
|
怎么样，看了这些分析，你是不是已经知道该怎样写这个算法了？
|
|||
|