1 我们常用的是中缀表达式,特点是运算符在中间,其结合的运算数在左边和右边。而后缀表达式的特点是运算符在后面,前面俩位置是其结合的运算数。如 : 4 - (1+2) * ( 3-2) + 1 ,其对应的后缀表达式是 4 1 2 + 3 2 - * - 1 +
2 这个问题,用栈来解决。最难的地方不是栈 的使用,栈的应用很多,我们完全可以不挑后缀表达式这个非常难的地方来学习栈(单端插入单端删除)。难点在于如何把中缀表达式转化为后缀表达式,依据的原理是什么,转换的每一步是否正确,为什么要这么转化。所以对于加减乘除这最基本的问题,我们也要再仔细思考一下我们为什么要这么进行数学计算,而且结果也是正确的。
3 中缀表达式的运算法则是 ① 从左到右扫描计算整个式,左右两个运算符的优先级相等时候,先计算左面的那个运算符②乘除运算符优先级高于+ -,括号的优先级高于乘除。
所以对于中缀表达式,我们无法严格的从左到右扫描并计算整个算式得到运算结果,总是可能有后面的乘除运算或者括号导致后面的某一地方反而要先运算。换句话说,我们计算中缀表达式的次序是混乱的,按照优先级最高的原则,而非从左到右的原则。而我们的计算机只适合从左到右扫描整个算式,computer不会像人类一样会先知般的通过观察知道要计算算式里的某一部分,还有条不紊。
4 后缀表达式则解决了这一问题。后缀表达式里取消了括号,只有运算数和+ - × ÷ 四种运算符。后缀表达式的运算法则是:严格按照运算符的从左到右的运算顺序进行计算,所有运算符具有同样的优先级。排左面的运算符先运算,排右面的后运算。
5所以我们写后缀表达式时候,要按照我们期望的运算顺序写表达式,而且会很不直观。我们要遵循的规则是严格让算式从左到右计算,不许从中间的某一运算符计算。而我们中缀表达式里的原则是算式意义优先,计算顺序则是其次。
6 还有一个难点在于,我们手写的中缀转后缀表达式,和计算机程序做的转换,思路和过程是不一样的。我们人类可以充分观察中缀算式,写的时候,从算式整体和大局出发,也未必严格按照从左到右的顺序,反正完善和补充了整个后缀算式,计算机也可以这么飘逸么?计算机只会从左到右扫描整个算式,从左到右开始转换,我们需要有细致的思路,告诉计算机每一步该怎么做。而对我们人类手工计算后缀表达式来讲,这种思路是不需要的,或者是因为我们人类的思维太快,大脑里的转换规则,我们根本没有清晰的意识到。我们的任务就是要把思路清晰完整起来,告诉计算机需要怎么做。
7 举个例子,如 “2 + 3 - 4“
+ 在前面,但我们也没有立即计算 (2 + 3 ),我们要参考右面的运算符 - ,属于同级运算符,然后我们才敢于计算(2 + 3 )。
8 再举个例子,如 “2 + 3 × 4”
我们看式子,先遇到 + 号,我们仍然没有计算 (2 + 3 ),参考后面的 × ,我们先计算
3 × 4 ,再计算 2 + 12 ,那么这个 + 号,计算机已经扫描过了,存储在哪里呢?很显然存储在栈里,计算完 × 后,把 + 号从栈顶弹出来,写入到后缀表达式字符数组里即可。
总结后缀转换 :① 从左到右扫描算式,数字字符原样输出,位置不变,为什么不变呢?因为不需要改变数据的相对位置,我们要改变的是运算符的相对位置。运算符入栈后,保存右操作数到后缀表达式,运算符再出栈保存在后缀表达式里时,位置已经在右操作数后面了。刚好符合我们后缀表达式的书写规则。举例如(2 + 3),写成 (2 3 +)
②中缀转后缀的核心问题就是,把运算符的优先级(包括括号),转换成从左到右的运算顺序,排左面的先运算,排右面的后运算。
③具体转换过程是,遇到中缀式里的运算符,一律入栈,作为栈顶运算符。其是否出栈,依赖于其右面的运算符的优先级。若左高右低,则栈顶运算符可以出栈并写入后缀表达式,表示其可以先计算,这个“先“是相对于其右面的运算符,与此同时,右运算符入栈,作为新的栈顶;若左低右高,则右运算符也要进栈,右运算符是否可以出栈也同样取决于其更右面的运算符的优先级。
④若右运算符是(,遵循先计算括号里数据的原则,(必须入栈,作为右运算符的(优先级最高。
⑤若右运算符是 ),表示括号结束,则出栈所有运算符直至栈顶运算符是(,表示已出栈完括号内所有运算符,对应于后缀表达式已可以完整计算整个括号里的数值。这时弹出栈顶 ( ,并且不必写入后缀表达式,因为后缀表达式里是没有括号的。
⑥依次循环,直至转换完整个表达式。作为运算符优先级比较的基准,我们先在栈顶存入 = 号,任何运算符优先级都比等号 = 高,都会入栈,而 = 号会最终成为栈底的最底层的元素,等以后出栈完所有运算符再次遇到 = 时,就说明整个表达式已经转换完成了,program可以ends 了。
⑦附上运算符优先级比较表:这是处理整个转后缀表达式问题的核心依据。摘自李春葆老师课本,这种思路我感觉挺好的。
⑧再补充一点,我感觉左运算符里 ) = 6,这种情况是不可能出现的。左运算符是栈顶运算符,左运算符变成 ) 之前,已经把它对应的括号里的运算符全部弹出栈了。左元算符取值0 1 3 5 6,右运算符取值:0 1 2 4 6 ,右运算符也不会是 = 的,因为我们没有输入= 号,也不必要。6 = 6 也是不可能出现的。 唯一程序里出现的 运算符优先级 1 = 1,表示括号里的运算符已经全部出栈了。
最后一点,程序里的功能只能计算正整数的+ - × ÷,不能计算负数比如-5+6,因为我们的程序只能处理双目运算符,不能处理单目运算符,同理正数也不能写+3+2,同样会程序报错。而且,只能计算正数运算。不能计算小数的计算,那样会让程序的功能进一步复杂。
然,设计这样的一个阉割了的算术计算表达式程序,功能也不全面,目的是什么?为了学习,凡事总是由易到难。谢谢阅读。下篇里附上完整的程序