需求

由于项目需求，需要在低性能设备高频率地解析计算数学表达式，所以重量级的比如词法分析，语法分析，抽象语法树🌲三件套就不太合适了。（当然也不是不行，只是有点大材小用，而个人能力又有限，对于ANTLR调优之类不太擅长）

说起数学公式解析，当然离不开老朋友逆波兰表达式，也就是后缀表达式，他能忽略括号等优先级问题，按照顺序一一计算。本次也打算从这里入手，慢慢再加入其他一些特性。

先总结下需求：

• 
  
• 支持加减乘除与括号，以及括号嵌套。
  
• 支持负数/负表达式以及连续负号。比如 1*-2=-2, 1*--2=2, 1*-(2+3)=-5。
  
• 支持固定的函数，以及函数与表达式的相互嵌套。比如 1+abs(-2-3)=6。
  
• 支持常量，例如 pi, e。
  

因为使用场景频率较高，所以解析过程中不要使用临时对象，如果非要使用要建立对象池避免 GC 压力过大。

基础实现

首先是最基本的，中缀转后缀表达式。再捋一下基本思想：

准备一个 OP 栈存放操作符。从头开始扫描字符串，遇到数字则直接输出（暂且称之为输出），否则假设 OP 栈顶元素为 A，扫描到的标识符为 B：

1. 
   
2. 若 B 是右括号，则将栈中元素依次出栈输出，直到左括号。括号出栈不输出。
   
3. 若 A 为空 或 A 是左括号 或 B 是左括号，则 B 入栈。
   
4. 若 B 优先级大于 A，则 B 入栈。
   
5. 否则 A 出栈输出并循环，直到满足上述条件之一。
   

扫描结束后将 OP 元素全部出栈输出，得到完整的后缀表达式。

按照上述算法，表达式 2*(3+4) 转换后输出为 234+*。然后只需要按顺序扫描输出，遇到数字入栈，遇到运算符出栈操作数，然后将计算结果再入栈，最后栈中唯一元素就是答案了。

不难看出这种方法相当于遍历了两遍。其实我们可以再准备一个表达式 exp 栈，在输出的过程中直接入 exp，如果遇到操作符，则进行计算再将结果入 exp。这样只需要遍历一遍就能得到答案。

💡 Tips

复盘 B 入栈的条件，可以发现栈中可能存在的元素包含运算符与左括号。右括号永远不会入栈。也就是说 A 可能的值为运算符与左括号。反直觉地，我们只需要将左括号(定义为优先级最低，即可将括号也作为运算符看待一并计入优先级比较，避免一小段特殊逻辑代码。

但请注意 AB 都是左括号时，虽然优先级相等，但是 B 应当入栈而不是 A 出栈。 因此相比于直接定义 int 优先级，我更偏向于定义一个二维 bool 数组，用于快捷查找任意两个符号比较，应当出栈还是入栈。

到此为止已经解决了四则运算与括号的问题。

额外需求

函数

我的基本思想就是将函数作为一个特殊的操作符（和加号一样）处理。那么就会产生几个问题：

1. 
   
2. 函数的操作数都在操作符的后面。
   
3. 函数的优先级如何定义。
   
4. 参数的分隔符,怎么办。
   
5. 函数什么时候可以出栈？
   

第一个问题其实不影响什么。我们思考一下常规减号-的处理流程。首先将左边操作数输出，然后将减号入栈，最后输出右边操作数。对比一下函数：首先将函数（特殊操作符）入栈，然后将参数依次输出（当作操作数）。显然，两者最终的输出以及栈是一样的，即：操作数从左至右依次输出，操作符入栈。因此操作数与操作符的相对位置并不重要。

问题二则更简单，显然函数的优先级应该是最高，遇到直接入栈就完事了，但是两个函数之间该如何比较？其实这种情况根本不可能发生，因为函数后必定紧跟着一个左括号(，一旦左括号入栈，则后续的操作符必定直接入栈。因此函数入栈时，栈顶不可能也是函数。

至于参数分隔符，我将其视为一个表达式的结束。因为每一个参数都可能是一个嵌套的表达式，我们知道函数在执行前必须先计算出所有参数的值。如此一来，参数分隔符,和右括号)一样不需要入栈，同时要弹出栈中的其他元素，直到遇左括号(。但是不要把左括号出栈，因为左括号和函数是一体的，分隔符只是参数的结束，并不是函数的结束。

最后，既然函数的优先级最高，那么什么时候才能轮到它出栈呢？显而易见肯定不能等最后集中出栈，否则就成了薛定谔的参数了。之前讨论到函数的操作数都在右边，换句话说，当操作数全部输出时，就应该立即让函数出栈。答案呼之欲出：当函数结束的时候函数本身应该出栈，而右括号)就是函数的结束符。这个符号在基础章节已经被定义过了，遇到右括号，我们要循环出栈直到左括号。此时应该加上一条：左括号出栈后如果栈顶元素是函数，那么将其出栈并输出。 这就能保证在后缀表达式中函数可以紧挨着它的所有参数。

负号

负号可以视为一个单目运算符，为了区别于减号(-)，这里用波浪线(~)指代负号。那么只需解决两个问题：

1. 
   
2. 什么情况下减号需要视为负号？
   
3. 负号优先级如何？
   

先来解决简单的，负号优先级应该是最高（除了函数之外）。因为负号总是和后面的数或表达式结合，不受前方运算符的影响。比如 1*~2=2。

下面为了解决问题一，我罗列了整个表达式中所有可能的数据类型，然后一一判断此时减号应该如何解释。

右括号等情况稍微复杂，正常来说前面是个表达式，那么后边应该为减号。但是我们的语法允许空括号 ()，这种表达式经过解析后其实什么都没有。所以遇到右括号)得额外判断 exp 栈，如果栈不为空且栈顶是数字则为负号~，否则为减号-。

这样我们就需要用一个变量来记录上一个符号的类型，以便判断语义时使用。连续负号情况不需要额外处理。

常量

常量可以说是最简单的额外需求了，简单到甚至不需要额外处理。读取到常量后直接视为数字处理就行了。

解析问题

最后来说一下解析问题。因为一个 Token 可能由多个字符组成，例如数字 12.3 有4个字符，函数 abs 有3个字符。所以本质上我们要手写一个定制的词法解析器，因为语法相对简单，所以难度不算太大。考虑到使用场景，这里的宗旨是整个字符串只扫描一遍，不回退不预读。 容错就不过多考虑了，最外层之间 try 一下。

首先是最简单的常量与函数解析。先来明确下他们的语法定义：以字母开头，只能包含字母数字与下划线_，大小写敏感。我们就可以提炼出下面的特征：（为了便于描述，这里把常量和函数名统称为标识符id）

• 
  
• 遇到的第一个字母一定是 id 的开头。
  
• 之后遇到的第一个非字母数字下划线一定表示 id 结束。
  

那么算法就水到渠成了。为了提高 id 拼凑效率，我在外部定义了一个 StringBuilder 用来拼接。当然，还有其他方案，例如记录 id 首末 index 然后一次性提取等。

接下来是识别数字，包括小数。数字可以包含数字和小数点.。类似的，遇到的一个数字或小数点.表示一个数字的开始，之后遇到的第一个非数字且非小数点表示数字的结束。

可以用上面 id 的方法来记录数字字符串，最后一次性地调用 kotlin 标准库函数转换为 double 类型。不过这里扣个字眼：标准库转换的时候必然要扫描字符串，而我们已经扫描一遍了，所以做了重复工作。为此，我定义一个 double 变量 num=0，以及一个表示小数位数的 double fraction=1。扫描到数字后将 num *10 然后加上当前数字。若在小数点之后，则先把 fraction / 10，然后乘以当前数字最后加到 num 上。

如此一来，在扫描的同时我们就实现了字符串到数字类型的转换。