动态公式处理库

• 下载 dynamicformula_demo - 213.88 KB
• 下载 dynamicformula_library - 247.6 KB

引言

该库将字符串中的公式计算为一个值，例如 "2+4*6+2" 返回 28。

背景

中缀表达式

简单来说，中缀表达式是我们普通人使用的符号，例如 2+4*6+2。在中缀表达式中，运算符（例如 + 或 *）位于操作数（例如 2、4 和 6）之间。虽然这种表示法对于人类来说很容易理解，但对于处理来说却不那么方便，因为计算机通常需要知道要做什么，然后才能知道操作数值的具体内容，因此产生了前缀表达式。

前缀

前缀表达式或其变体被大多数编程语言和处理算术逻辑单元（ALU）使用，可以定义为 operator operand_1 operand_2 operand_3 等。考虑以下中缀公式 2 + 4 * 6 + 2，它可以表示为前缀表达式 + 2 + * 4 6 2，或者更逻辑地表示为一棵树；

然后按 + 2 (+ (* 4 6) 2) 进行处理，公式的计算沿着树向上进行；

前缀表达式的树结构表示构成了该库的基础，但是由于普通人理解有限，因此不希望以这种形式要求用户输入。

中缀 -> 前缀转换

中缀到前缀的转换是在堆栈上使用分词器（在这种情况下通过空格边界生成标记）执行的。

1. 反转输入字符串。
2. 检查输入中的下一个元素。
3. 如果是操作数，则将其添加到输出字符串。
4. 如果是右括号，则将其压入堆栈。
5. 如果它是运算符，则
   1. 如果堆栈为空，则将运算符压入堆栈。
   2. 如果堆栈顶部是右括号，则将运算符压入堆栈。
   3. 如果它的优先级与堆栈顶部相同或更高，则将运算符压入堆栈。
   4. 否则，从堆栈中弹出运算符并将其添加到输出字符串，重复步骤 5。
6. 如果它是左括号，则从堆栈中弹出运算符并将其添加到输出字符串，直到遇到右括号。弹出并丢弃右括号。
7. 如果还有更多输入，请转到步骤 2。
8. 如果没有更多输入，则将剩余的运算符出栈并将其添加到输出字符串。
9. 反转输出字符串。

鸣谢 C 语言表达式、转换和求值。

假设我们要将 2 + 4 * 6 + 2 转换为前缀形式：反转表达式：2 + 6 * 4 + 2

当前标记	堆栈内容（右侧为顶部）	前缀表达式（从右到左）
2		2
+	+	2
4	+	2 4
4	+	2 4
*	+ *	2 4
6	+ *	2 4 6
+	+ +	2 4 6 *
2	+ +	2 4 6 * 2
	+	2 4 6 * 2 +
		2 4 6 * 2 + +

反转输出字符串：+ + 2 * 4 6 2

处理动态公式

每个数学运算符都通过一个类封装，该类包含运算符和运算符所需的所有操作数（请记住操作数可能是其他数学运算符和操作数），从而允许如上所述的树模式。

注意：在此动态公式处理实现中，不仅可以处理标准数学运算符和值，还可以处理常量（例如 x 和 y）。就中缀到前缀转换而言，值和常量的处理方式相同，因为在此过程中标记的值并不重要，重要的是类型。

每个运算符类都包含以下方法；

• String parse(String s); - 解析（和子解析字符串）；返回要处理的字符串的其余部分
• double evaluate(Hashtable variables); - 返回评估结果，使用变量哈希表中定义的适当变量
• bool nextIs(String s); - 如果下一个标记是这些运算符之一，则返回 true
• ArrayList getVariableNames(); - 返回此运算符和子运算符中所有必需常量的列表

parse 方法的执行如下（* 假设运算符需要两个操作数）；

1. 读取并移除第一个标记；即运算符
2. 读取第一个标记（即操作数）
3. 如果操作数是值或常量，则移除标记并保存为操作数 1
4. 否则确定运算符类型并使用剩余输入字符串调用 parse（保存为操作数 1）
5. 使用剩余字符串（或操作数 1 的 parse 结果，如果操作数 1 确实是运算符）移除并保存为操作数 2，如果标记是值或常量
6. 否则确定运算符类型并使用剩余输入字符串调用 parse（保存为操作数 2）
7. 返回剩余字符串（或操作数 2 的 parse 结果，如果操作数 2 确实是运算符）。

因此，处理可以按以下方式完成；

1. 获取公式字符串
2. 转换为前缀表示法
3. 确定第一个标记的运算符类型
4. 使用相关运算符类型解析整个公式字符串

一旦完成，将形成如下树数据结构，例如 2 + 4 * 6 + 2 或 + + 2 * 4 6 2；

    <add><add>2, <multiply>4, 6</multiply></add>, 2</add>

因此调用递归的 evaluate 方法执行；

1. * 4 6
2. + 2 24
3. + 2 26
4. 28

在执行常量的情况下，evaluate 方法在提供的 Hashtable 中执行查找。

Using the Code

所提供的库可以计算数学函数 + - * / ^（幂）。

• + 由 Add 封装
• - 由 Subtract 封装
• * 由 Multiply 封装
• / 由 Divide 封装
• ^ 由 Power 封装

此外；

• 值由 Value 封装
• 常量由 Variable 封装

要使用该库，只需创建一个新的 Formula，并在构造函数中提供公式字符串。使用包含常量的 Hashtable（如果没有，则为 new Hashtable()）调用 evaluate 会返回公式结果。

关注点

这是动态计算公式的最佳方法吗？不是，当需要处理大量公式时，这种方法的性能不佳，因为在计算时方法调用次数很多。然而，当与遗传算法（进化算法）结合使用时，这种方法特别有益，因为易于变异和交叉。我关于这个主题的下一篇文章将展示如何使用该库生成一个自动适应任何趋势的曲线函数。

历史

版本 1.0.0.0 - 初始构建

其他许可说明

请随意在您的工作中使用此代码，但请注意，此处使用的是修改后的 The Code Project Open License (CPOL)；基本上，它与标准许可证相同，只是未经事先授权，此代码不得用于商业或非营利性商业用途。请参阅随附的源代码和演示文件中的 license.txt 或 license.pdf。