算法运行效果在上。没看错，某人的代码就是这样. 论坛好像没有程序设计的板块，有点尴尬。不过没事，反正没事干。然后嘛......这文章的标题到底叫什么还不好讲......对于爱好者，八九成是新的；对于NOI的dalao或者专业程序设计人员，说不定还不怎么滴; 对于某某科技（不讲算法的都不是好教程！！！）的受害者，那八九成也是新的。但是是不是最简单的嘛......这还真得权衡一下，毕竟会者不难难者不会。
好了切入到正题。打开你的Window$，然后找这个东西: Calculator.exe。你知道它是什么了——计算器。没什么大不了的，对吧。但是我们要自己实现一个呢？你会选用某宝上某某科技的“输入一个数字，然后等待输入一个运算符，然后再输入一个数字来进行运算”的BUG算法（为啥？之后会提），还是会去抱树的大腿呢？一个个来看看就是：
1. 如果你选择了某某科技的算法，那么我个人认为，你深受不佳的编程思路的迫害——那种算法压根无法处理这样的问题：5-2*3。它一定会算错。
2. 如果你选择了第二个，那么我猜八九成看过了一本叫做《编译原理》的书，里面提到的树的确是用来解析表达式的（抽象语法树，简称：AST）。
自然地，第一种方法是不可能使用的，它本身做计算器就会变成BUG。而第二种方法的确可行，但是不觉得有点大材小用了吗？而且好像树的数据结构不是那么的好写，要涉及到孩子、双亲什么的问题。 因此，我介绍第三种方法——后缀表达式，或者叫它：逆波兰表达式，如果你还记得《编译原理》或者是你的那本算法书的内容的话，一定记得它在讲栈的时候被提到过。逆波兰表达式，是1929年波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，这种表达式没有任何括号并且运算符永远都是在后面的，而且是按照运算符优先级排列的。比如，拿刚刚的那个5 - 2 * 3来看，它对应的逆波兰表达式就是：5 2 3 * -（后面会提到怎么转换），然后，计算过程就是下面这样的（注，我用绿色表示被运算的数据和运算符）：[blockquote]5 2 3 * - => 5 6 - => -1[/blockquote] 看出规律了吗？逆波兰表达式的运算符总是操作的是前面的几个数据。在遇到运算符时，会取出前面的数据，然后进行运算，再把运算的结果放回原来的表达式。直到遍历完整个表达式。 好了那么来伪装一下，假设我们会转换后缀表达式了，然后要对它求值，怎么办？先想五秒钟......... 有一个很简单的思路，就是用栈，一种非常简单却非常重要的数据结构。为什么说简单呢？因为它只是一个数组（顺序栈...哎复杂了不管不管不管），然后遵循下面的原则：后进先出。我比较喜欢用摞书来比喻栈——最先放的书被压在最底下，最后放的书在最上面。放书的过程就是入栈，当把书拿出来时，我们从顶上开始拿，自然的最后放进去的会最先被拿出来。这个拿书的过程叫做出栈。那么为什么说它是非常重要的呢？这一点很好说明，在看完本文后，我们可以来想一想下面的问题：如果我要开发一款编程语言，那么我该怎么做？相信我，你一定会用到栈的，尤其是函数调用那块。 因此，按照栈的思想，我们就可以把操作数（5; 2; 3）给暂时的存起来，然后遇到运算符的时候再把它弹出来计算，再将计算的结果丢回去。直到整个表达式被遍历完，栈中应该也只有一个结果了——那个就是我们需要的结果。因此，对于5 2 3 *-这个玩意，用这个思路计算就应该是：[blockquote]1. 一直入栈操作数，直到遇到运算符。现在，我们得到了栈中的数据是：3 2 5。[/blockquote][blockquote]2. 遇到"*"，出栈两个数据（xa = 先出来的3, xb = 后出来的2），然后计算xb * xa（注意，虽然乘法满足交换律，但是我依然把顺序标出来了——栈会把顺序弄反过来，从弹出的数据就可以看出了，它和原表达式是反的（请想想看，为什么？）3. 把xb * xa ( 结果为6）入栈，现在栈中的数据为：6 5 -4. 又遇到操作符"-"，一样的，弹出数据：xa = 6, xb = 5，计算xb - xa5. 把结果（-1）入栈，栈中的数据为：-16. 表达式遍历完成，计算结果表明栈中只有一个元素，证明表达式正确。输出结果：-1[/blockquote] 现在明白了吧？下面来演练一下这个表达式的计算：逆波兰表达式=8 9 3 2 --*4 10 2 -*-。用上面的栈的过程试试？如果你计算正确的话，得到的值应该是32。下面请把这个表达式还原成原始表达式，试试？ 我个人的代码本身是很早以前做的了，现在功能比较全。但是依然可以看得到上面说的过程（背景的大龙猫？我不知道啊......）： 然后，具体实现请开动你的大脑，我相信你可以的。下面再来解决第二个问题——如何构建一个逆波兰表达式。 按照之前的描述，逆波兰表达式的运算符顺序是按照运算优先级排列的。什么是运算符优先级？就是先加减后乘除，如果记不得可以想一下自己是不是把5 - 2 * 3计算出9来过？好继续之前的事情，转换问题。转换的思路多种多样，但是既然之前用了栈，那么我一样用栈来实现看看。比如，对于7+8*2这个表达式，我很快就想到了思路，得到了对应的后缀表达式：[blockquote]1. 遇到操作数7，输出到后缀表达式（结果数据: 7）
2. 遇到运算符"+"，入栈运算符（得到栈的数据：+）
3. 遇到操作数8，输出到后缀表达式（结果数据: 7 8）
4. 遇到运算符"*"，入栈运算符（得到栈的数据：*+）
5. 遇到操作数2，输出到后缀表达式（结果数据: 7 8 2）
6. 把运算符栈里面的数据全部出栈[/blockquote] 等等......有问题。这样是顺序遍历啊，哪里来的运算符优先级的事情？？？
所以，很明显这种简单的方案压根也不通用。我们继续想一下，对于乘、除、幂啊这种运算，它的运算优先级目前来说是最高的——加减都在它的后面。因此，遇到乘号、除号的时候也要把相同优先级的数据弹出来，直到遇到不是同一个优先级的，或者是括号。当遇到加减号的时候，也是要把同一运算优先级的弹出来，直到遇到不是同一个优先级的，或者是括号。自然地，我们还要考虑栈是不是为空的情况（注，这个过程有点抽象，最好拿笔画一画）。那么，考虑一个很简单的式子，5-(2+3+1)，它的构建过程就应该是：[blockquote]01. 输出到后缀表达式: 5
02. 发现栈是空的，因此不管, 入栈"-"（注意顺序，是先判断后入栈）。
03. 入栈"("，注意，为了避免想歪，这里直接声明，"("直接入栈，不管是什么时候。
04. 输出到后缀表达式: 5 2
05. 发现栈不是空的，但是栈顶端的元素是"("，因此不管，入栈"+"。
06. 输出到后缀表达式: 5 2 3
07. 发现栈不是空的，栈顶端的元素是"+"（当前栈数据: + ( - ），因此出栈，直到遇到"("或者栈空了。得到后缀表达式: 5 2 3 +。入栈"+"
08. 输出到后缀表达式: 5 2 3 +1
09. 发现是右括号，因此一直出栈，直到遇到"("。得到栈数据：-，后缀表达式：5 2 3 +1 +。(入栈")",这个并不会执行，括号只是划分优先级而不是用于计算）
10. 遍历完成，弹出栈中所有的数据，得到了5 2 3 +1 +-。执行完毕。[/blockquote] 总结一下，就是遇到操作数直接输出，然后遇到运算符就放入栈中，并按照一定的顺序出栈即可。但是，注意判断和入栈的顺序问题。下面演练一下：7+8*(9-(3+2))【结果:7 8 9 3 2 +-*+】，8*(9-(3-2))-(4*(10-2))【结果： 8 9 3 2 --*4 10 2 -*-】。具体实现嘛......我相信你的。你也可以看我的实现，但是我觉得你可能会头痛——我的实现做了一些拓展，看起来会很烦。
这个，就是算术表达式求值的一种方法的简介。烦请诸位帮忙斧正。 |
|
转播
淘帖
开水来年会吗
