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