一个“自然”表达式求值器
计算表达式值的自然方法
引言
我一直对用于评估表达式的 AST 或 RPN 算法的反直觉性感到困扰。在本文中，我将展示一种不同的、更“自然”的方法来解决计算表达式的值的问题。
想法
假设我需要计算这个表达式
1+3*(5-(8-4)+(2+3)^2)
如果我用笔和纸进行计算，我会首先计算优先级最高的操作的数值结果来简化表达式，并迭代地简化表达式，直到剩下最终数值
| 步骤 1 | 1+3*(5-4+5^2) |
| 第二步 | 1+3*(5-4+25) |
| 步骤 3 | 1+3*26 |
| 步骤 4 | 1+78 |
| 步骤 5 | 79 |
我编写的表达式求值器完全遵循这个想法，其中操作的优先级是通过组合运算符的优先级及其嵌套级别来计算的。
运算符优先级
每个算术运算符都被分配一个基本优先级。
| 运算符 | 优先级 |
+ | 1 |
- | 1 |
* | 2 |
/ | 2 |
^ | 3 |
如果运算符嵌套在括号内，则优先级等于基本优先级加上嵌套级别乘以10。我们刚才看到的表达式中运算符的优先级将如下所示
通过从最高级别开始执行操作，并将运算符和操作数替换为结果，我们可以将表达式简化为最终值
实现
实现步骤如下
- 包含表达式的输入字符串将被格式化。
- 将构建一个包含表达式所有标记的数组。
- 将构建第二个包含所有运算符级别的数组。
格式化
格式化过程会将输入字符串转换为符合某些规则的字符串。例如，空空格将被消除，像2(3+1)这样的表达式将被转换为2*(3+1)等等。此外，如果输入字符串以加号或减号以外的运算符开头以及其他情况，它将抛出异常。
分词
标记化过程接受格式化的表达式并产生
- 包含标记的数组（如上所示）。
- 包含每个运算符优先级的数组。
- 包含优先级列表的数组。此数组将被排序，我们将从最高优先级值开始简化过程。
示例
假设我们需要评估表达式字符串
-5+2*(1+((7/8^2)-12^(-2))+9/4)
格式化后，该字符串将转换为
0-5+2*(1+((7/8^2)-12^(0-2))+9/4)
标记化过程将创建这三个数组
_tokens
_tokenPriority
_priorityValues
再次，让我们回顾一下运算符的优先级是如何计算的
我们从每个运算符的基本优先级开始
+ -> 1
- -> 1
* -> 2
/ -> 2
^ -> 3
然后，我们加上运算符所在的括号级别乘以10。
计算
数组_priorityValues被排序，并且从最高值（在我们的例子中是33）开始，_tokens数组中的所有运算符都被计算，然后它们被该计算的结果替换。所以数组_tokens和_tokensPriority从
to
等等，直到我们得到最终结果。
结论和关注点
显然，该算法可以以许多不同的方式进行扩展和优化，但这超出了我今天的范围。本文附带一个压缩的 Visual Studio 项目，其中包含一个类中的所有解析器代码和一个简单的Form。
历史
- 2022年12月21日：初始版本