简化数学表达式的策略
Dav*_*ong 65 algorithm math simplify
我有一个结构良好的树,代表一个数学表达式.例如,给定字符串:"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 个权力的根源)是42？
我意识到这个问题相当广泛,但是我一直在打击这个问题一段时间并没有得到足够令人满意的东西.
Ste*_*eAp 85
您可能希望实现术语重写系统.关于基础数学,请看看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.
- +1这真是令人着迷,是迄今为止最有前途的方法. (2认同)
How*_*ard 11
这个任务可能变得非常复杂(除了最简单的转换).基本上这就是代数软件一直在做的事情.
您可以找到一个可读的介绍如何完成(基于规则的评估),例如Mathematica.
- 当然,人们会使用CAS软件来简化术语.但是,如果需要在应用程序中实现术语重写,则标准CAS不是可行的方法,因为大多数都不可嵌入. (2认同)