优先级就是全部问题
读懂 2 + 3 * 4 需要知道乘法比加法结合得更紧,因此答案是 14 而不是 20。每个运算符都带有优先级和结合性。乘法、除法和取余高于加减;幂运算高于以上全部,并且是右结合的,所以 2^3^2 意为 2^(3^2),结果是 512 而不是 64。
一元负号是微妙的情形。数学惯例把它排在幂运算之下,这就是 -3^2 等于 -9 的原因:指数作用于 3,取负作用于结果。电子表格软件以持不同意见著称,它会返回 9;如果你曾见过两个工具对同一公式给出不同答案,通常正是这个原因。本求值器遵循数学惯例。
括号可以覆盖上述一切,而且值得放心大胆地使用。一个需要查优先级表才能读懂的表达式,迟早会被人读错。
简述调度场算法
表达式首先被拆分为记号——数字、名称、运算符和标点——然后由 Dijkstra 的调度场算法重排为后缀形式,即运算符跟在操作数之后。2 + 3 * 4 会变成 2 3 4 * +。后缀形式不需要括号也不需要优先级规则,因为记号的顺序已经编码了结构,一台简单的栈式机器一趟就能求值。
该算法维护两个结构:一个输出列表和一个运算符栈。数字直接进入输出;运算符在自己入栈之前,先弹出栈中所有结合力不低于它的运算符。括号在栈上充当标记,右括号会一路弹出直到遇见它的配对。函数调用则作为带参数计数的运算符一同参与,每遇到一个逗号计数加一。
电子表格引擎和查询规划器内部用的正是同一套技术。它以线性时间运行,无需递归,并且能自然地报出格式错误:如果最后栈没有干净地清空,说明输入本身不平衡。
关于浮点数,说实话
结果以 IEEE 754 双精度计算,这与所有浏览器和多数编程语言使用的算术相同。它以二进制存储数字,而 0.1 这样的十进制小数没有精确的二进制表示,这正是 0.1 + 0.2 众所周知会得到 0.30000000000000004 而不是 0.3 的原因。
把显示结果舍入到设定的有效数字位数,可以在不改变底层值的前提下隐藏这些噪声,这正是这里精度控件的作用。设为 12 位既能保持可读,又距离双精度真正能区分的 15 到 17 位留有充足余量。
有两个限制值得记住。整数只在 2^53 以内保持精确,因此非常大的阶乘和乘积会产生漂移;超过 170! 会直接溢出为无穷大。另外,两个几乎相等的数相减会摧毁精度——前导数字相互抵消,只剩下带噪声的尾部数字——因此重新整理公式以避开这类减法,往往会比直观写法精确得多。