利用两个栈,一个栈a负责入数据和出数据,另一个_min负责放存入数据中目前最小的数。 如果_min中没有数据,那么a入数据的时候,它也入。但是_min里面放的是a中目前最小的数据,所以如果数据小于_min的top所放的数据时也插入。那么相等时候的的数据_min插不插入呢?
当然val和_min.top()数据相同时候也插入。因为再删除数据的时候,当a栈顶出栈的时候,_min栈顶同时也得出栈,这样才能保证_min.top()里面能够保存的是最小值。 所以pop得这样写:
题目要求返回最小值,那么就是返回_min.top():
这里用了两个栈,想要匹配出栈的顺序,最简单的方法就是: 先把入栈序列入栈,如果出现入栈序列和出栈序列的栈顶元素相同,那么两边就同时出数据,直到入栈序列和出栈序列的栈顶元素不匹配,或者出栈序列为空。 想要知道最后匹不匹配就直接判断一下入栈序列是否为空。为空就是已经匹配,否则就不匹配。
逆波兰表达式就是后缀表达式,而我们一般用的是中缀表达式。 举个例子:把中缀表达式换成后缀表达式
用例1来分析一下:
在没有遇到第一个算符之前,就把数据入栈,当遇到运算符,就把它前面两个数2和1出,计算出来结果就是2+1=3,然后再把这个3再入栈;当再一次遇到表达式时候,又把它的前面两个数出栈做对应的运算之后,在把算出的结果入栈,最后输出栈顶元素就可以了。
有问题请指出,大家一起进步!!!