浅谈表达式求值

说到表达式求值问题，相信很多人都是迷茫或者不知道该如何下手去解决问题。首先要知道什么是表达式求值？可以解决什么问题？

通过看了表达式求值的一系列题目得知，要解决的问题一般是输入一个字符串表示的表达式，要求输出它的值。当然也有变种比如表达式中是否包含括号，指数运算，含多少变量，判断多个表达式是否等价，等等。

表达式一般需要先进行语法分析再求值，也可以边分析边求值，语法分析的作用是检查输入的字符串是否是一个合法的表达式，一般使用语法分析器解决。

表达式包含两类字符：运算数和运算符。对于长度为n的表达式，借助合适的分析方法，可以在O(n)的时间复杂度内完成分析与求值。

说到表达式求值的问题，表达式求值的顺序一部分是由操作符的优先级和结合性决定。

同样，有些表达式的操作数在求值的过程中可能需要转换为其他类型。

（1）常用表达式求值分析

①方法

常见的方法有两种，一种是中缀表达式求值，一种是后缀表达式求值

②优缺点

中缀表达式：符合人的习惯，但是在计算机中计算时要考虑其优先级和括号的关系，实现起来比较麻烦

后缀表达式：在计算机中实现时不需要考虑优先级和括号，因为后缀表达式已经将其解决了，但是不符合人的习惯

（2）相互转换分析

①关于前缀的转换是从右向左扫描的

②关于后缀的转换是从左向右转换的

3.总结

不管是怎么样转换和怎么样计算，思路理解起来都没那么难，难就难在代码的实现上，这个还是需要大家做大量的题，去通过实践来理解。

当你代码有了、思路有了，用代码敲出自己的思路，记住：代码的实践很重要！