第八章：第14节 PHP数据结构与算法——栈的强化学习（一）

更新于：2017-07-03 22:24:13

继续分享一个用“栈”这种数据结构实现计算器的功能。

一个普通的计算器代码：

如果我们设计成这样的计算器：

输入一个运算表达式（字符串），例如“ 3+2*6-2 ”这样的字符串，计算出结果来。

像这样的计算器我们怎么去设计呢？

可能我们首先会想到“eval”这个函数，没错，它的确可以实现，把 “ 3+2*6-2 ” 转成PHP代码执行。我们在这里不用eval函数，我们要自己写代码去分析字符串做计算，用“栈”这种数据结构完成功能。

思路=====>分析图
3+2*6-2 从人的眼睛看是 3+12-2=>15-2=>13，但是怎么让计算机知道呢， 计算机可没长眼睛，它怎么知道要先算2*6，然后再3+12，最后再15-2呢，计算机要扫描3 + 2 * 6 - 2一个个的字符。

思路【怎么做】
思路[怎么做] ★现在的这个思路还不是很完美的，还是有考虑不周全的地方，先死后活，先有思路了，在后面再完善。★
1.程序扫描表达式，一个一个的扫描
2.当发现这个字符是数字的时候，直接入数栈
3.如果发现是运算符
3.1如果符号栈为空，就直接入符号栈
3.2如果符号栈不为空，就要判读。如果当前运算符的优先级小于等于符号栈顶的这个运算符的优先级，就计算，并把计算结果入数栈，然后把当前符号入栈（然后把当前符号入栈，此处会有问题，碰到复杂运算的时候，先考虑简单的，后面再优化，先死后活）
3.3如果符号栈不为空，就要判读。如果当前运算符的优先级大于符号栈顶的这个运算符的优先级，就入栈
4.当扫描完毕后，就依次弹出数栈和符号栈的数据，并计算，最终留在数栈的值，就是运算结果。

3+2*6-2
过程：
（1）首先扫描到一个数字3，直接入数栈
（2）继续扫描发现是一个+，现在符号栈是空的，直接入栈
（3）继续扫描发现是一个数字2，直接入数栈
（4）继续扫描发现是一个*，现在符号栈不为空，并且*大于当前符号栈栈顶+的运算优先级，直接入栈
（5）继续扫描发现是一个数字6，直接入数栈
（6）继续扫描发现是一个-，现在符号栈不为空，并且-小于当前符号栈栈顶*的运算优先级，则计算。怎么计算呢，从数栈弹出两个数，从符号栈弹出一个运算符。即从数栈弹出6和2，然后从符号栈弹出*，并用变量接收。注意此时两个栈的top的指向变化
$num1=6;
$num2=2;
$oper=*;
$res=6*2; ==>12