गणित अभिव्यक्ति को सरल बनाने के लिए रणनीति

Question

मेरे पास एक अच्छी तरह से गठित पेड़ है जो गणितीय अभिव्यक्ति का प्रतिनिधित्व करता है। उदाहरण के लिए, स्ट्रिंग दिया:

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

कौन इस पेड़ के रूप में व्यक्त किया जाता है: "1+2-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) (^वें 42 की रूट ^वें शक्ति) 42 है?

मुझे पता है इस सवाल का बहुत व्यापक है, लेकिन मैं थोड़ी देर के लिए इस के खिलाफ मेरे सिर पिटाई कर रहे हैं और कुछ भी संतोषजनक पर्याप्त के साथ नहीं आए हैं।

Answer 1

आप शायद एक term rewriting system लागू करना चाहते हैं। अंतर्निहित गणित के बारे में, WikiPedia पर एक नज़र डालें। एक शब्द पुनर्लेखन मॉड्यूल

जब से मैं एक समाधान हाल ही में लागू की

संरचना ...

• सबसे पहले, एक वर्ग CExpression, जो मॉडल अपने अभिव्यक्ति की संरचना तैयार करते हैं।

• CRule लागू करें, जिसमें एक पैटर्न और प्रतिस्थापन शामिल है। पैटर्न चर के रूप में विशेष प्रतीकों का प्रयोग करें, जो पैटर्न मिलान के दौरान बाध्य होने और प्रतिस्थापन अभिव्यक्ति में प्रतिस्थापित करने की आवश्यकता है।

• फिर, CRule कक्षा को लागू करें। यह मुख्य विधि applyRule(CExpression, CRule) अभिव्यक्ति के किसी भी लागू उप-अभिव्यक्ति के खिलाफ नियम से मिलान करने का प्रयास करती है। यदि यह मेल खाता है, तो परिणाम वापस कर दें।

• फिनली, कक्षा CRuleSet को लागू करें, जो कि केवल CRule ऑब्जेक्ट्स का एक सेट है।मुख्य विधि reduce(CExpression) तब तक नियमों का सेट लागू करती है जब तक कोई नियम लागू नहीं किया जा सकता है और फिर कम अभिव्यक्ति देता है।

• इसके अतिरिक्त, आपको कक्षा CBindingEnvironment की आवश्यकता है, जो पहले से मिलान किए गए मानों के लिए मिलान किए गए प्रतीकों से मेल खाते हैं।

कोशिश एक सामान्य रूप

मत भूलना के लिए अभिव्यक्ति के पुनर्लेखन के लिए, कि इस दृष्टिकोण एक निश्चित बिंदु तक काम करता है, लेकिन गैर पूरा होने की संभावना है। यह इस तथ्य के कारण है कि निम्नलिखित सभी नियम स्थानीय शब्द पुनर्लेखन करते हैं।

इस स्थानीय पुनर्लेख तर्क को मजबूत बनाने के लिए, किसी को अभिव्यक्ति को किसी सामान्य रूप में बदलने की कोशिश करनी चाहिए। यह मेरा दृष्टिकोण है:

• यदि किसी शब्द में शाब्दिक मूल्य होते हैं, तो यथासंभव यथासंभव अवधि को स्थानांतरित करने का प्रयास करें।

• आखिरकार, यह शाब्दिक मूल्य सही दिखाई दे सकता है और पूरी तरह से शाब्दिक अभिव्यक्ति के हिस्से के रूप में मूल्यांकन किया जा सकता है।

जब पूरी तरह से शाब्दिक अभिव्यक्ति का मूल्यांकन करने के

एक दिलचस्प सवाल है जब पूरी तरह से शाब्दिक अभिव्यक्ति का मूल्यांकन करने के। मान लीजिए आप एक अभिव्यक्ति

x * (1/3) 

जो करने के लिए

x * 0.333333333333333333 

अब मान लीजिए कि एक्स को कम करेगा 3. द्वारा बदल दिया जाता है इस तरह

0.999999999999999999999999 

इस प्रकार उत्सुक मूल्यांकन कुछ लाभ होगा एक से थोड़ा गलत रिटर्न है मूल्य।

दूसरे पक्ष पर

, अगर आप (1/3) और पहले से 3

3 * (1/3) 

एक्स की जगह रीराइट नियम

1 

इस प्रकार देना होगा, यह मूल्यांकन करने के लिए उपयोगी हो सकता है रखने के देर से पूरी तरह से शाब्दिक अभिव्यक्ति।

पुनर्लेखन नियमों के उदाहरण

यहाँ कैसे मेरे नियमों अनुप्रयोग के भीतर दिखाई देते हैं:

addRule(new TARuleFromString('0+_1', // left hand side :: pattern 
           '_1'  // right hand side :: replacement 
          ) 
     ); 

या थोड़ा और अधिक जटिल

: _1, _2, ... प्रतीकों किसी भी उपसूचक से मेल खाते हैं

addRule(new TARuleFromString('_1+_2*_1', 
           '(1+_2)*_1' 
          ) 
     ); 

कुछ विशेष प्रतीकों केवल विशेष उप-अभिव्यक्तियों से मेल खाते हैं। जैसे _ लिटरल 1, _ लिटरल 2, ...केवल शाब्दिक मान से मेल:

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 अनुप्रयोगों के लिए, Dave DeLong's DDMathParser एक आदर्श उम्मीदवार वाक्य रचना गणितीय अभिव्यक्ति का विश्लेषण करने के लिए है।

अन्य भाषाओं के लिए, हमारे पुराने दोस्त Lex & Yacc या नए GNU Bison मदद की जा सकती है।

बहुत छोटा और enourmous set of ready to use syntax-files, ANTLR जावा पर आधारित एक आधुनिक पार्सर जनरेटर है। पूरी तरह से कमांड लाइन उपयोग के अलावा, ANTLRWorks एएनटीएलआर आधारित पार्सर्स बनाने और डिबग करने के लिए GUI फ्रंटएंड प्रदान करता है। एएनटीएलआर various host language, जैसे JAVA, C, Python, PHP or C# के लिए व्याकरण उत्पन्न करता है। एक्शनस्क्रिप्ट रनटाइम वर्तमान में broken है।

मामले में आप जानने के लिए नीचे-ऊपर से भाव (या सामान्य तौर पर भाषाओं) पार्स करने के लिए कैसे करना चाहते हैं, मैं इस free book's text from Niklaus Wirth (या german book edition), पास्कल और Modula- के प्रसिद्ध आविष्कारक का प्रस्ताव करता हूँ 2।

Answer 2

यह कार्य काफी जटिल हो सकता है (सबसे सरल परिवर्तन के अलावा)। अनिवार्य रूप से यह algebra software हर समय होता है।

आप यह कैसे किया जाता (नियम के आधार पर मूल्यांकन) एक पठनीय परिचय प्राप्त कर सकते हैं जैसे कि Mathematica के लिए।

Answer 3

आप वास्तव में सामान्य रूप में इस वजह से, हालांकि वे गणितीय ही कर रहे हैं, कंप्यूटर अंकगणित में एक ही नहीं हो सकता है नहीं कर सकते। उदाहरण के लिए, -MAX_INT अपरिभाषित है, इसलिए -% a =/=% a। इसी प्रकार फ्लोट्स के लिए, आपको उचित रूप से NaN और Inf से निपटना होगा।

Answer 4

आप एक कैस (गणना बीजगणित प्रणाली) का निर्माण करने के लिए इच्छुक रहे हैं और विषय इतना व्यापक है कि यह करने के लिए समर्पित अध्ययन के एक पूरे क्षेत्र है कि वहाँ है। जिसका अर्थ है कि कुछ books हैं जो शायद आपके प्रश्न को एसओ से बेहतर जवाब देंगे।

मुझे पता है कि कुछ सिस्टम पेड़ों का निर्माण करते हैं जो पहले स्थिरांक को कम करते हैं और फिर पेड़ को सामान्यीकृत रूप में डालते हैं और फिर किसी अन्य रूप में समस्या को बदलने के लिए large database of proven/known formulas का उपयोग करते हैं।

Answer 5

मेरा बेवकूफ दृष्टिकोण प्रत्येक कार्य के उलटा (यानी divide और multiply) के साथ कुछ प्रकार की डेटा संरचना होगी। आपको स्पष्ट रूप से यह सुनिश्चित करने के लिए और तर्क की आवश्यकता होगी कि वे 3 से गुणा होने के बाद वास्तव में व्यस्त हैं और फिर 4 से विभाजित करना वास्तव में एक विपरीत नहीं है।

हालांकि इस आदिम है, मुझे लगता है कि समस्या पर एक सभ्य पहले पास है और मामलों आप अपने प्रश्न में नोट का एक बहुत हल होगा।

मैं आगे अपना पूरा समाधान देखने और पर विस्मय में घूर के लिए लग रहे हो गणितीय प्रतिभा :)

Answer 6

मेरा मानना ​​है कि आप करने के लिए "जानवर बल" जैसे पेड़ है।

आपको संभावित नियमों का वर्णन करने वाले कुछ नियम तैयार करना होगा। फिर आप पेड़ से घूमने और लागू नियमों की खोज करने के लिए तैयार हैं। चूंकि कुछ सरलीकरणों से दूसरों के मुकाबले सरल परिणाम हो सकते हैं, इसलिए आपको एक समान काम करना होगा जो आप सबवे योजना पर सबसे कम मार्ग खोजने के लिए करते हैं: सभी संभावनाओं को आजमाएं और परिणामों को कुछ गुणवत्ता मानदंडों से क्रमबद्ध करें।

चूंकि इस तरह के परिदृश्यों की संख्या सीमित है, इसलिए आप ऑपरेटरों और चर के सभी संयोजनों को स्वचालित रूप से सरलीकरण नियमों को खोजने में सक्षम हो सकते हैं और फिर एक अनुवांशिक एल्गोरिदम है जो सत्यापित करता है कि नियम पहले नहीं मिला है और यह वास्तव में इनपुट को सरल बनाता है।

गुणा अतिरिक्त के रूप में प्रतिनिधित्व किया जा सकता है, तो एक नियम हो सकता है कि एक - एक ही रद्द आउट: 2 ए-एक = एक + एक-एक

एक और नियम पहले सब डिवीजनों बाहर गुणा करने के लिए, क्योंकि उन भिन्न हैं होगा। उदाहरण:

1/2 + 3/4 डिस्कवर सब डिवीजनों और उसके बाद अन्य सभी अंशों

4/8 + 6/8 तो सभी तत्वों है के दोनों किनारों पर भाजक के साथ प्रत्येक अंश गुणा एक ही भाजक और इतने (4 + 6)/8 = 10/8

को एकीकृत अंत में आप ऊपर और नीचे के बीच उच्चतम आम भाजक को खोजने 5/4

अपने ट्री पर लागू रणनीति होगी कर सकते हैं नीचे पत्तियों से ऊपर काम करने के लिए सरलीकृत करें प्रत्येक गुणा को पहले इसे जोड़कर परिवर्तित करना। फिर प्रत्येक अतिरिक्त को सरल बनाने जैसे

जब भी आप इस तरह के सरलीकरणों को खोजने के लिए अपने शॉर्टकट नियमों को फिर से जांचेंगे। यह जानने के लिए कि एक नियम लागू होता है, आपको शायद उप-उपरोक्त सभी क्रमिक प्रयासों को आज़माएं। जैसे एक नियम भी एए + ए के लिए आवेदन करेगा। एक + बी-ए हो सकता है।

बस कुछ विचार, आशा है कि आप कुछ विचार देता है ...