我有一个表示数学表达式的格式良好的树。例如，给定字符串: "1+2-3*4/5"，它会被解析为：
subtract(add(1,2),divide(multiply(3,4),5))
这表示为这棵树：
我想做的就是尽可能地减少这棵树。在上面的例子中，这很简单，因为所有的数字都是常数。但是，一旦我允许未知数（用 a$后跟标识符表示），事情就会变得更加棘手：
"3*$a/$a"变成divide(multiply(3,$a), $a)
这应该简化为3，因为这些$a条款应该相互抵消。问题是，“我如何以通用的方式识别这一点？” 我怎么知道这min(3, sin($x))总是会发生的sin($x)？我怎么知道那sqrt(pow($a, 2))是abs($a)？我如何识别nthroot(pow(42, $a), $a)（42 次方的 a次方根）是？42
我意识到这个问题非常广泛，但我一直在努力反对这个问题并且没有想出任何令人满意的东西。
您可能想要实现一个术语重写系统。关于基础数学，请查看WikiPedia。
术语重写模块的结构
由于我最近实施了一个解决方案......
首先，准备一个类 CExpression，它对表达式的结构进行建模。
实现CRule，其中包含一个模式和一个替换。使用特殊符号作为模式变量，在模式匹配时需要绑定，在替换表达式中替换。
然后，实现一个类CRule。它的主要方法applyRule(CExpression, CRule)尝试将规则与任何适用的表达式子表达式进行匹配。如果匹配，则返回结果。
最后，实现一个类CRuleSet，它只是一组 CRule 对象。reduce(CExpression)只要不能应用更多规则，main 方法就会应用规则集，然后返回简化的表达式。
此外，您需要一个类CBindingEnvironment，它将已经匹配的符号映射到匹配的值。
尝试将表达式重写为正常形式
不要忘记，这种方法在一定程度上有效，但可能并不完整。这是因为以下所有规则都执行本地术语重写。
为了使这种本地重写逻辑更强大，应该尝试将表达式转换为我称之为正常形式的东西。这是我的方法：
如果术语包含文字值，请尝试将术语尽可能向右移动。
最终，这个文字值可能出现在最右边，并且可以作为完全文字表达式的一部分进行评估。
何时评估完全文字表达式
一个有趣的问题是何时评估完全文字表达式。假设你有一个表达式
x * ( 1 / 3 )
这将减少到
x * 0.333333333333333333
现在假设 x 被 3 替换。这将产生类似
0.999999999999999999999999
因此，急切的评估会返回一个稍微不正确的值。
另一方面，如果您保留 ( 1 / 3 ) 并首先将 x 替换为 3
3 * ( 1 / 3 )
重写规则会给
1
因此，晚评估完全文字表达式可能很有用。
重写规则示例
以下是我的规则在应用程序中的显示方式： _1、_2、... 符号匹配任何子表达式：
addRule( new TARuleFromString( '0+_1', // left hand side :: pattern
'_1' // right hand side :: replacement
)
);
或者更复杂一点
addRule( new TARuleFromString( '_1+_2*_1',
'(1+_2)*_1'
)
);
某些特殊符号只匹配特殊子表达式。例如 _Literal1, _Literal2, ... 仅匹配文字值：
addRule( new TARuleFromString( 'exp(_Literal1) * exp(_Literal2 )',
'exp( _Literal1 + _Literal2 )'
)
);
此规则将非文字表达式向左移动：
addRule( new TARuleFromString( '_Literal*_NonLiteral',
'_NonLiteral*_Literal'
)
);
任何以“_”开头的名称都是模式变量。当系统匹配规则时，它会保留一堆已匹配符号的分配。
最后，不要忘记规则可能会产生非终止替换序列。因此，在减少表达式的同时，让过程记住之前已经到达过哪些中间表达式。
在我的实现中，我不直接保存中间表达式。我保留了一组中间表达式的 MD5() 哈希值。
一套规则作为起点
以下是一组入门规则：
addRule( new TARuleFromString( '0+_1', '_1' ) );
addRule( new TARuleFromString( '_Literal2=0-_1', '_1=0-_Literal2' ) );
addRule( new TARuleFromString( '_1+0', '_1' ) );
addRule( new TARuleFromString( '1*_1', '_1' ) );
addRule( new TARuleFromString( '_1*1', '_1' ) );
addRule( new TARuleFromString( '_1+_1', '2*_1' ) );
addRule( new TARuleFromString( '_1-_1', '0' ) );
addRule( new TARuleFromString( '_1/_1', '1' ) );
// Rate = (pow((EndValue / BeginValue), (1 / (EndYear - BeginYear)))-1) * 100
addRule( new TARuleFromString( 'exp(_Literal1) * exp(_Literal2 )', 'exp( _Literal1 + _Literal2 )' ) );
addRule( new TARuleFromString( 'exp( 0 )', '1' ) );
addRule( new TARuleFromString( 'pow(_Literal1,_1) * pow(_Literal2,_1)', 'pow(_Literal1 * _Literal2,_1)' ) );
addRule( new TARuleFromString( 'pow( _1, 0 )', '1' ) );
addRule( new TARuleFromString( 'pow( _1, 1 )', '_1' ) );
addRule( new TARuleFromString( 'pow( _1, -1 )', '1/_1' ) );
addRule( new TARuleFromString( 'pow( pow( _1, _Literal1 ), _Literal2 )', 'pow( _1, _Literal1 * _Literal2 )' ) );
// addRule( new TARuleFromString( 'pow( _Literal1, _1 )', 'ln(_1) / ln(_Literal1)' ) );
addRule( new TARuleFromString( '_literal1 = pow( _Literal2, _1 )', '_1 = ln(_literal1) / ln(_Literal2)' ) );
addRule( new TARuleFromString( 'pow( _Literal2, _1 ) = _literal1 ', '_1 = ln(_literal1) / ln(_Literal2)' ) );
addRule( new TARuleFromString( 'pow( _1, _Literal2 ) = _literal1 ', 'pow( _literal1, 1 / _Literal2 ) = _1' ) );
addRule( new TARuleFromString( 'pow( 1, _1 )', '1' ) );
addRule( new TARuleFromString( '_1 * _1 = _literal', '_1 = sqrt( _literal )' ) );
addRule( new TARuleFromString( 'sqrt( _literal * _1 )', 'sqrt( _literal ) * sqrt( _1 )' ) );
addRule( new TARuleFromString( 'ln( _Literal1 * _2 )', 'ln( _Literal1 ) + ln( _2 )' ) );
addRule( new TARuleFromString( 'ln( _1 * _Literal2 )', 'ln( _Literal2 ) + ln( _1 )' ) );
addRule( new TARuleFromString( 'log2( _Literal1 * _2 )', 'log2( _Literal1 ) + log2( _2 )' ) );
addRule( new TARuleFromString( 'log2( _1 * _Literal2 )', 'log2( _Literal2 ) + log2( _1 )' ) );
addRule( new TARuleFromString( 'log10( _Literal1 * _2 )', 'log10( _Literal1 ) + log10( _2 )' ) );
addRule( new TARuleFromString( 'log10( _1 * _Literal2 )', 'log10( _Literal2 ) + log10( _1 )' ) );
addRule( new TARuleFromString( 'ln( _Literal1 / _2 )', 'ln( _Literal1 ) - ln( _2 )' ) );
addRule( new TARuleFromString( 'ln( _1 / _Literal2 )', 'ln( _Literal2 ) - ln( _1 )' ) );
addRule( new TARuleFromString( 'log2( _Literal1 / _2 )', 'log2( _Literal1 ) - log2( _2 )' ) );
addRule( new TARuleFromString( 'log2( _1 / _Literal2 )', 'log2( _Literal2 ) - log2( _1 )' ) );
addRule( new TARuleFromString( 'log10( _Literal1 / _2 )', 'log10( _Literal1 ) - log10( _2 )' ) );
addRule( new TARuleFromString( 'log10( _1 / _Literal2 )', 'log10( _Literal2 ) - log10( _1 )' ) );
addRule( new TARuleFromString( '_Literal1 = _NonLiteral + _Literal2', '_Literal1 - _Literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_Literal1 = _NonLiteral * _Literal2', '_Literal1 / _Literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_Literal1 = _NonLiteral / _Literal2', '_Literal1 * _Literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_Literal1 =_NonLiteral - _Literal2', '_Literal1 + _Literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_NonLiteral + _Literal2 = _Literal1 ', '_Literal1 - _Literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_NonLiteral * _Literal2 = _Literal1 ', '_Literal1 / _Literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_NonLiteral / _Literal2 = _Literal1 ', '_Literal1 * _Literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_NonLiteral - _Literal2 = _Literal1', '_Literal1 + _Literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_NonLiteral - _Literal2 = _Literal1 ', '_Literal1 + _Literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_Literal2 - _NonLiteral = _Literal1 ', '_Literal2 - _Literal1 = _NonLiteral' ) );
addRule( new TARuleFromString( '_Literal1 = sin( _NonLiteral )', 'asin( _Literal1 ) = _NonLiteral' ) );
addRule( new TARuleFromString( '_Literal1 = cos( _NonLiteral )', 'acos( _Literal1 ) = _NonLiteral' ) );
addRule( new TARuleFromString( '_Literal1 = tan( _NonLiteral )', 'atan( _Literal1 ) = _NonLiteral' ) );
addRule( new TARuleFromString( '_Literal1 = ln( _1 )', 'exp( _Literal1 ) = _1' ) );
addRule( new TARuleFromString( 'ln( _1 ) = _Literal1', 'exp( _Literal1 ) = _1' ) );
addRule( new TARuleFromString( '_Literal1 = _NonLiteral', '_NonLiteral = _Literal1' ) );
addRule( new TARuleFromString( '( _Literal1 / _2 ) = _Literal2', '_Literal1 / _Literal2 = _2 ' ) );
addRule( new TARuleFromString( '_Literal*_NonLiteral', '_NonLiteral*_Literal' ) );
addRule( new TARuleFromString( '_Literal+_NonLiteral', '_NonLiteral+_Literal' ) );
addRule( new TARuleFromString( '_Literal1+(_Literal2+_NonLiteral)', '_NonLiteral+(_Literal1+_Literal2)' ) );
addRule( new TARuleFromString( '_Literal1+(_Literal2+_1)', '_1+(_Literal1+_Literal2)' ) );
addRule( new TARuleFromString( '(_1*_2)+(_3*_2)', '(_1+_3)*_2' ) );
addRule( new TARuleFromString( '(_2*_1)+(_2*_3)', '(_1+_3)*_2' ) );
addRule( new TARuleFromString( '(_2*_1)+(_3*_2)', '(_1+_3)*_2' ) );
addRule( new TARuleFromString( '(_1*_2)+(_2*_3)', '(_1+_3)*_2' ) );
addRule( new TARuleFromString( '(_Literal * _1 ) / _Literal', '_1' ) );
addRule( new TARuleFromString( '(_Literal1 * _1 ) / _Literal2', '(_Literal1 * _Literal2 ) / _1' ) );
addRule( new TARuleFromString( '(_1+_2)+_3', '_1+(_2+_3)' ) );
addRule( new TARuleFromString( '(_1*_2)*_3', '_1*(_2*_3)' ) );
addRule( new TARuleFromString( '_1+(_1+_2)', '(2*_1)+_2' ) );
addRule( new TARuleFromString( '_1+_2*_1', '(1+_2)*_1' ) );
addRule( new TARuleFromString( '_literal1 * _NonLiteral = _literal2', '_literal2 / _literal1 = _NonLiteral' ) );
addRule( new TARuleFromString( '_literal1 + _NonLiteral = _literal2', '_literal2 - _literal1 = _NonLiteral' ) );
addRule( new TARuleFromString( '_literal1 - _NonLiteral = _literal2', '_literal1 - _literal2 = _NonLiteral' ) );
addRule( new TARuleFromString( '_literal1 / _NonLiteral = _literal2', '_literal1 * _literal2 = _NonLiteral' ) );
制定规则一流的表达方式
有趣的一点：由于上述规则是特殊的表达式，可以被表达式解析器正确评估，用户甚至可以添加新规则，从而增强应用程序的重写能力。
解析表达式（或更一般的：语言）
对于Cocoa/OBjC 应用程序，Dave DeLong 的 DDMathParser是语法分析数学表达式的完美候选者。
对于其他语言，我们的老朋友Lex & Yacc或更新的GNU Bison可能会有所帮助。
ANTLR是一个基于 Java 的现代解析器生成器，它年轻得多，并且拥有大量可立即使用的语法文件。除了纯粹的命令行使用，ANTLRWorks还提供了一个GUI 前端 来构建和调试基于 ANTLR 的解析器。ANTLR 为各种宿主语言生成语法，如JAVA、C、Python、PHP 或 C#。ActionScript 运行时当前已损坏。
如果您想学习如何自下而上地解析表达式（或一般语言），我建议您从 Niklaus Wirth （或德文版），Pascal 和 Modula 的著名发明者那里获得这本免费书籍的文本-2。
这个任务可能变得相当复杂（除了最简单的转换）。本质上，这就是代数软件一直在做的事情。
您可以找到一个可读的介绍如何做到这一点（基于规则的评估），例如Mathematica。
您想要构建一个 CAS（计算代数系统），并且该主题非常广泛，以至于有一个专门的研究领域。这意味着有几本书可能会比 SO 更好地回答您的问题。
我知道有些系统首先会构建减少常量的树，然后将树放入规范化形式，然后使用经过验证/已知公式的大型数据库将问题转换为其他形式。
我相信你必须“蛮力”这样的树。
您将必须制定一些描述可能简化的规则。然后你必须遍历树并搜索适用的规则。由于某些简化可能会导致比其他简化更简单的结果，因此您必须做与在地铁计划中寻找最短路线类似的事情：尝试所有可能性并按某些质量标准对结果进行排序。
由于此类场景的数量是有限的，您可以通过尝试运算符和变量的所有组合来自动发现简化规则，并再次使用遗传算法来验证之前没有找到该规则并且它实际上简化了输入.
乘法可以表示为加法，因此一个规则可能是 a - a 自行抵消：2a-a = a+aa
另一个规则是首先将所有除法相乘，因为它们是分数。例子：
1/2 + 3/4 发现所有除数，然后将每个分数与所有其他分数两边的除数相乘
4/8 + 6/8 那么所有元素都有相同的除数，所以可以统一为 (4+6)/8 = 10/8
最后你找到顶部和底部 5/4 之间的最大公约数
应用于您的树的策略是从底部叶子向上工作，首先通过将其转换为加法来简化每个乘法。然后像分数一样简化每个加法
一直以来，您都会再次检查您的快捷方式规则以发现此类简化。要知道规则是否适用，您可能必须尝试子树的所有排列。例如，aa 规则也适用于 -a+a。可能有a+ba。
只是一些想法，希望能给你一些想法......
您实际上通常不能这样做，因为尽管它们在数学上是相同的，但在计算机算术中可能不一样。例如，-MAX_INT 未定义，所以 --%a =/= %a。同样对于浮点数，您必须适当地处理 NaN 和 Inf。
我幼稚的方法是拥有某种数据结构，每个函数（即divide和multiply）都是逆的。您显然需要进一步的逻辑来确保它们实际上是逆的，因为乘以 3 然后除以 4 实际上并不是逆。
尽管这是原始的，但我认为这是解决问题的不错的第一步，并且可以解决您在问题中提到的许多情况。
我确实期待看到您的完整解决方案，并敬畏地盯着数学才华:)