数学表达式求值器
4.87/5 (53投票s)
数学表达式求值器。
引言
如果你经常编写依赖于某种脚本的应用程序，那么一个数学表达式求值器将是一个有用的代码片段。图形应用程序（使用模板创建复合图像）、表单填写或电子表格软件（根据用户输入执行可配置的计算），或者数据分析应用程序（根据脚本对批量数据执行计算）只是我想到的几个例子。
一些关于词法分析、状态机和解析的知识会很有帮助，但并非必需。这里简短的讨论以及在调试器中对代码进行一些实验，应该能提供足够的解释，让你至少能够开始使用这段代码。
词法扫描
求值表达式的第一步是识别表达式的各个组成部分，即标记。此求值器使用基于有限状态机的词法扫描器来识别标记，并为每个标记分配一个类别，例如“数字”、“运算符”、“标点符号”或“函数”。状态机使用一组预定义的规则，根据当前状态和输入（来自缓冲区的字符）在状态之间进行转换。它最终会到达一个结束状态（希望如此），届时可以执行特定于结束状态的代码。在这种情况下，结束状态表示找到了一个标记，特定于结束状态的代码会识别输入缓冲区中的标记，并将其存储到标记列表中。
状态机通常由一个类似下表的表驱动，该表用于本文提供的代码。状态显示在每一行，列由输入字符确定。所有条目都为 1 的状态是结束状态。当达到这些结束状态之一时，代码通过跟踪其起始位置和当前位置，从缓冲区中截取出标记，将其与关联的类型（“数字”、“运算符”等）一起存储到列表中，然后返回到起始状态，即状态一。
例如，让我们从缓冲区“73 ”（添加了一个空格作为结束标记）开始。转换如下：从状态 1 开始，输入 7（数字）表示移动到状态 4。从状态 4 开始，输入 3（数字）表示停留在状态 4。从状态 4 开始，输入空格（' '）表示移动到状态 5。状态 5 是数字的结束状态。此时，数字 73 已被识别，然后将被存储到标记列表中。
| 字母 | 数字 | 选项卡 | 空间 | . | 标点符号 | 运算符 | |
| 1 | 2 | 4 | 1 | 1 | 4 | 6 | 7 |
| 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 |
| 3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 4 | 2 | 4 | 5 | 5 | 4 | 5 | 5 |
| 5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
你可能已经注意到“运算符”列有些取巧。通常，每个运算符可能都有自己的列，当输入该运算符字符时，会指导状态机进行相应的操作。然而，单字符运算符可以组合，前提是添加一些特殊的处理来正确设置列。这样做是为了能够轻松添加新的运算符，而无需修改状态表。稍后将详细介绍。
解析和求值
一旦生成了标记列表，每个标记都分配了一个适当的类型（“运算符”、“数字”等），然后对表达式进行解析和求值。解析验证表达式的语法，重构表达式以考虑运算符的优先级，并在本例中还求值表达式。此代码使用相对简单的递归下降解析算法。
递归下降解析是通过一系列递归函数实现的，每个函数处理表达式语法中的不同部分。递归下降解析的优点是易于实现。然而，主要缺点是表达式的语言（在本例中是数学）被硬编码到代码的结构中。因此，语言的变化通常需要修改代码本身。有标准的解析算法由表驱动，而不是函数，但通常需要额外的软件来生成部分代码和表，并且可能需要更大的努力来实现。
然而，此代码中使用的递归下降解析器以一种允许对数学表达式（函数和运算符）中的典型语言修改（例如添加新函数和运算符）而不改变代码结构的方式编写的。
添加新的运算符和函数
此代码处理了表达式中通常遇到的大多数基本运算符和函数。然而，添加对其他运算符和函数支持的实现起来很简单。
递归下降解析函数已编写为一系列级别，每个级别处理特定优先级、关联性（左或右）和可能称为“度”（一元或二元）的运算符。对于二元、左关联运算符有 3 个优先级级别（level1、level2 和 level3）。默认情况下，level1 处理加法和减法（+,-），level2 处理乘法运算符（*, /, %, \），level3 处理指数（^）。在任何一个级别添加新运算符需要 2 个步骤。一是修改 `init_operators` 函数以包含新运算符的符号，指定优先级级别和表示操作的字符。只有单字符运算符可以添加，而无需对词法扫描器进行其他更改。第二个步骤是修改 `calc_op` 函数来处理操作，这在代码中应该会很清楚。Level4 处理右关联一元运算符（-, + 即取反等），level5 处理左关联一元运算符（! 阶乘）。在这些级别添加新运算符的过程与上述相同。
添加函数同样简单。必须首先将新函数名添加到 `m_funcs` 数组中，该数组在 `mcCalc` 类的声明中初始化。然后必须修改 `calc_function` 函数以执行函数操作。函数参数以集合的形式传递给 `calc_function` 函数。解析器简单地传递它在函数后面的括号内找到的逗号分隔值的数量。`calc_function` 函数负责移除函数所需的参数数量，并在传递的参数数量不正确时生成任何错误。甚至可以通过在第一个参数中指示函数参数的数量来实现可变长度参数列表。
关注点
此代码有几种有趣的修改可以提供额外的实用性。变量标识符和替换也可能对那些需要更彻底的求值工具的人有用。通过使用委托支持调用者定义的函数或运算符，对于任何有兴趣将此代码用作外部程序集的人来说，都将是一个不错的补充。当然还有更多，任何关于此类功能的建议或修改都欢迎。希望这段代码在您的应用或至少在其对表达式求值原理的解释中能证明对您有用。