수학 표현을 단순화하기위한 전략

수학 표현을 단순화하기위한 전략

---

수학적 표현을 나타내는 잘 구성된 트리가 있습니다. 예를 들어, 문자열 "1+2-3*4/5"이 주어지면 다음 과 같이 구문 분석됩니다.

subtract(add(1,2),divide(multiply(3,4),5))

이 트리로 표현됩니다.

제가 할 수있는 것은이 나무를 가져다가 가능한 한 많이 줄이는 것입니다. 위의 경우 모든 숫자가 상수이기 때문에 이것은 매우 간단합니다. 그러나 알 수없는 항목 ( $다음에 식별자가 표시됨)을 허용하면 문제가 발생하기 시작합니다 .

"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)(단, A ^번째 받는 42의 루트를 ^일 전력)이다 42?

나는이 질문이 꽤 광범위하다는 것을 알고 있지만, 나는 이것에 대해 잠시 동안 머리를 치고 있었으며 충분히 만족스러운 것을 얻지 못했습니다.

---

용어 재 작성 시스템 을 구현하고 싶을 것입니다 . 기본 수학과 관련하여 WikiPedia를 살펴 보십시오 .

용어 다시 쓰기 모듈의 구조

최근에 솔루션을 구현했기 때문에 ...

• 먼저 표현식의 구조를 모델링하는 CExpression 클래스를 준비합니다.

• CRule패턴 및 대체를 포함하는을 구현하십시오 . 패턴 일치 중에 바인딩되고 대체 표현식에서 대체되어야하는 패턴 변수로 특수 기호를 사용하십시오.

• 그런 다음 클래스를 구현하십시오 CRule. 주요 방법 applyRule(CExpression, CRule)은 표현식의 적용 가능한 하위 표현식에 대해 규칙을 일치 시키려고합니다. 일치하는 경우 결과를 반환합니다.

• 마지막으로, CRuleSet단순히 CRule 객체의 집합 인 클래스를 구현 합니다. 기본 메서드 reduce(CExpression)는 더 이상 규칙을 적용 할 수없는 한 규칙 집합을 적용한 다음 축소 된 식을 반환합니다.

• 또한 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' ) );

규칙을 최상급 식으로 만들기

흥미로운 점 : 위의 규칙은 표현식 파서에 의해 올바르게 평가되는 특수 표현식이므로 사용자는 새 규칙을 추가하여 애플리케이션의 재 작성 기능을 향상시킬 수도 있습니다.

구문 분석 (또는 더 일반적인 : 언어)

들어 코코아 / OBjC 응용 프로그램 , 데이브 드롱의 DDMathParser는 구문 수학적 표현식을 분석 할 수있는 완벽한 후보입니다.

다른 언어의 경우 오랜 친구 Lex & Yacc 또는 최신 GNU Bison 이 도움이 될 수 있습니다.

Far younger and with an enourmous set of ready to use syntax-files, ANTLR is a modern parser generator based on Java. Besides purely command-line use, ANTLRWorks provides a GUI frontend to construct and debug ANTLR based parsers. ANTLR generates grammars for various host language, like JAVA, C, Python, PHP or C#. The ActionScript runtime is currently broken.

In case you'd like to learn how to parse expressions (or languages in general) from the bottom-up, I'd propose this free book's text from Niklaus Wirth (or the german book edition), the famous inventor of Pascal and Modula-2.

---

This task can become quite complicated (besides the simplest transformation). Essentially this is what algebra software does all the time.

You can find a readable introduction how this is done (rule-based evaluation) e.g. for Mathematica.

---

You're wanting to build a CAS (compute algebra system) and the topic is so wide that there is an entire field of study dedicated to it. Which means there are a few books that will probably answer your question better than SO.

I know some systems build trees that reduce constants first and then put the tree into a normalized form and then use a large database of proven/known formulas to transform the problem into some other form.

---

I believe you have to "brute force" such trees.

You will have to formulate a couple of rules that describe possible simplifications. Then you habe to walk through the tree and search for applicable rules. Since some simplifications might lead to simpler results than others you will have to do a similar thing that you do for finding the shortest route on a subway plan: try out all possibilities and sort the results by some quality criteria.

Since the number of such scenarios is finite you might be able to discover the simplification rules automatically by trying out all combinations of operators and variables and again have a genetic algorithm that verifies that the rule has not been found before and that it actually simplifies the input.

Multiplications can be represented as additions, so one rule might be that a - a cancels itself out: 2a-a = a+a-a

Another rule would be to first multiply out all divisions because those are fractions. Example:

1/2 + 3/4 Discover all the divisions and then multiply each fraction with the divisor on both sides of all other fractions

4/8 + 6/8 Then all elements have the same divisor and so can the unified to (4+6)/8 = 10/8

Finally you find the highest common divisor between top and bottom 5/4

Applied to your tree the strategy would be to work from the bottom leaves upwards simplifying each multiplication first by converting it to additions. Then simplifying each addition like the fractions

All the while you would check agains your shortcut rules to discover such simplifcations. To know that a rule applies you probably have to either try out all permutations of a subtree. E.g. The a-a rule would also apply for -a+a. There might be a a+b-a.

Just some thoughts, hope that gives you some ideas...

---

You actually can't in general do this because, although they are the same mathematically, the may not be the same in computer arithmetic. For instance, -MAX_INT is undefined, so --%a =/= %a. Similarly for floats, you have to deal with NaN and Inf appropriately.

---

내 순진한 접근 방식은 각 함수 (예 : divide및 multiply)의 역을 갖는 일종의 데이터 구조를 갖는 것 입니다. 3을 곱한 다음 4로 나누는 것은 실제로 역이 아니기 때문에 실제로 역인지 확인하려면 추가 논리가 필요합니다.

이것은 원시적이지만 문제에 대한 적절한 첫 번째 통과라고 생각하며 질문에서 언급 한 많은 경우를 해결할 것입니다.

나는 당신의 완전한 해결책을보고 경외심을 느끼는 것이 수학적 탁월함을 기대합니다. :)

참고 URL : https://stackoverflow.com/questions/7540227/strategies-for-simplifying-math-expressions