计算之魂作者吴军简介(计算之魂内容简介)

本文节选自《计算之魂》电子版：

//第2章//逆向思考一一从递推到递归//例题2.5”简单计算器问题窒窗密现衣实现一个简单计算器，它支持不带括号的四则运算，计算器要满足先乘除后加减的规则。我们先来看两个简单四则运算的例子:“5+4-2=”和“35-4X3/4=。通常计算器的输入是一个字符串，我们会从左到右扫描这个字符串，扫到哪里，就用一个指针指向哪里。第一个问题很简单，先把5压入堆栈，然后压入加号+”和4，同时要用一个临时变量保存栈内最顶部的运算符。接下来，我们看到减号“-\"。由于减号“-”和栈内最项部的运算符加号“+”优先级相同，这时出栈，从堆栈中依次取出4、加号“+”和5。由于加法遵循交换律，我们直接计算4+5就可以了，然后把结果9再压回堆栈中。如果遇到的是减号“-”，那就必须保证是后出栈的5减去4。再接下来,我们将减号“-”和2压栈，见到等号“=”时做两步操作。第一步和前一步一样，完成9\"-2=7的操作;第二步则是输出结果，同时要检查栈是否为空。整个过程如图2.10所示。输入字符堆酚状

计算之魂吴军电子版

态5|[+EhLLLLLL45|]+[4[||-_EETTITTC[flll是图2.10计算“5+4-2=”时，扒栈状态随输入字符变化的过程把上面的描述编写成一个程序并不困难，伪代码留作思考题。唯一要注意是，遇到等号“=”之后的处理不同于遇到其他运算符，不能简单地把结果7压匠堆栈了事，出本疹全和同时检查栈是否已空。有的公司在面试时会问到这些细节。在处理“5-4X3/4=”这个算式时，前三步压栈和上一个例子相同，到了第四步要0851//计算之魂//于看到了更高优先级的乘号“X”，我们就不能进行5-4的运算了，而需要将这个运算符，以及后面的数字3压栈。在随后遇到除法运算符“/”后，我们知道它和栈内顶部的乘号“X”优先级相同，于是i结果。随后的计算和前面基本相同行4X3的运算(结果是12)，并且更改栈内顶部的，无非是在遇到等号“=”时先进行124【〈结果是3)的运算，然后进行5-3的运算，并且输出结果，清空堆栈。需要指出的是，在遇到除法时，我们需要判断除数不等于0。

如何评价吴军的计算之魂

整个过程如图2.11所示。输入字符堆栈状态55|||攻下上-|45|-14[eeX5[-[4[x]3上世人|知人/5[-12了|]|45||3|3图2.11计算“5-4x3/4=”时，扒栈状态随输入字符变化的过程如果没有堆栈这种数据结构，上面这样一个简单的问题解决起来会很复杂。使堆栈之后，实现简单计算器的逻辑就非常清晰。当然，利用堆栈常带需要一些技巧，根据具体的问题灵活使用。有些人在面试时做不出来这道题，原因并不在于没有想到使用堆栈，而是错误地使了推栈。我们在使用堆栈时，是边压栈，边处理，而他们将整个算式全部压入了堆栈后才考虑如何处理。这样，他们在遇到“5-4-3=这一类的算式时就不知道该如何计算了，因为显然不可能在堆栈的顶端先做4-3的运算。有了堆栈，任何需要先进后出、后进先出的算法都很容易实现。但是毕竟在这个世界上有些事情需要先来先处理，084数据需要先进先出(First-联first-Oout，FIFO)而队列〈Queue)这种数据结构则满足这个要求。

计算之魂吴军百度云

综上：计算之魂内容简介值得推荐阅读