逆波兰表达式

今天在搜索PHP算法的时候,无意间进入了知乎,有人问,PHP需要算法?有人说需要,有人说不需要,这里不说结论,只谈看到的一个回复,里面提到了逆波兰表达式,原谅我搞PHP两年了还是第一次听到这个词(非计算机专业,算法知识也很弱,正在学习中),觉得很新鲜,所以想分享一下!

逆波兰表达式又称后缀表达式,它的解释器一般都是基于堆栈的,操作数入栈,遇到操作符时,操作数出栈,求值,将结果入栈;写法是运算符在数字的后面,表达式中无需使用小括号”()”,运算顺序也清楚明了,如中缀表达式1 + 2用逆波兰表达式则为 1 2 +,中缀表达式1 + 2 * 3用逆波兰表达式则为 1 2 3 * +,PS:在搜索中缀表达式时,看到百度百科的词条里面好像有错误,理解了这个例子能更好的理解逆波兰表达式,如下图(截图时间是2015-08-30 20:40):

它举了一个例子:中缀表达式8 + 4 – 6 * 2(=0)用逆波兰表达式则为6 2 * 8 4 + -(=0),按照这个逆波兰表达式,如果转为中缀表达式其实是(6 * 2) – (8 + 4)(=0),计算结果没有问题,但计算顺序错误。如果把中缀表达式换为8 + 4 – 6 * 3(= 负6),按照图中写法逆波兰表达式则为6 3 * 8 4 + -(= 正6),所以正确写法应是8 4 + 6 2 * – 或是8 4 + 6 3 * -(如果有理解不对的地方,请快速提醒我,以免误导他人)。

逆波兰表达式的优点(摘自维基百科,自由的百科全书):

用于表达式求值,以利用堆栈结构和减少计算机内存访问。

当有操作符时就计算,因此,表达式并不是从右至左整体计算而是每次由中心向外计算一部分,这样在复杂运算中就很少导致操作符错误。

堆栈自动记录中间结果,这就是为什么逆波兰计算器能容易对任意复杂的表达式求值。与普通科学计算器不同,它对表达式的复杂性没有限制。

逆波兰表达式中不需要括号,用户只需按照表达式顺序求值,让堆栈自动记录中间结果;同样的,也不需要指定操作符的优先级。逆波兰计算器中,没有“等号”键用于开始计算。

逆波兰计算器需要“确认”键用于区分两个相邻的操作数。

机器状态永远是一个堆栈状态,堆栈里是需要运算的操作数,栈内不会有操作符。

教育意义上,逆波兰计算器的使用者必须懂得要计算的表达式的含义。