बच्चों के शैक्षिक सॉफ्टवेयर के लिए बुनियादी गणित समीकरणों को पार्स करना?

Question

recent TED talk से प्रेरित, मैं शैक्षिक सॉफ्टवेयर का एक छोटा टुकड़ा लिखना चाहता हूं। शोधकर्ता ने "Siftables" नामक ब्लॉक के आकार में छोटे लघु कंप्यूटर बनाए।

alt text http://images.ted.com/images/ted/tedindex/embed-posters/DavidMerrill-2009.embed_thumbnail.jpg
[David Merril, inventor - with Siftables in the background.]

कई अनुप्रयोगों वह में ब्लॉक का इस्तेमाल किया थे लेकिन मेरी पसंदीदा जब प्रत्येक ब्लॉक एक नंबर या बुनियादी आपरेशन प्रतीक था। फिर आप लाइनों में संख्याओं या ऑपरेशन प्रतीकों के ब्लॉक को फिर से व्यवस्थित कर सकते हैं, और यह किसी अन्य siftable ब्लॉक पर एक जवाब प्रदर्शित करेगा।

alt text http://i44.tinypic.com/m7us6g.png

तो, मैं एक सीएस कोर्स मैं ले रहा हूँ के लिए मेरा अंतिम परियोजना के रूप में एक सीमित पैमाने पर "गणित Siftables" का एक सॉफ़्टवेयर संस्करण कार्यान्वित करने के लिए मैं चाहता था फैसला किया है।

गणित अभिव्यक्तियों की एक स्ट्रिंग को पार्स करने और व्याख्या करने के लिए आम तौर पर स्वीकार्य तरीका क्या है, और यदि वे मान्य हैं, तो ऑपरेशन करें?

क्या यह एक ऐसा मामला है जहां मुझे एक पूर्ण पार्सर/लेक्सर लागू करना चाहिए? मुझे लगता है कि बुनियादी गणित अभिव्यक्तियों की व्याख्या करना कंप्यूटर विज्ञान में एक अर्ध-आम समस्या होगी, इसलिए मैं इस दृष्टिकोण के लिए सही तरीका ढूंढ रहा हूं।

उदाहरण के लिए, अगर मेरी गणित Siftable अवरुद्ध कर देता है की तरह की व्यवस्था की:

[1 ] [+ ] [2 ]

यह एक वैध अनुक्रम होगी और मैं "3" पर पहुंचने के लिए आवश्यक कार्रवाई करने के होगा।

हालांकि, अगर बच्चे को एक साथ इस तरह के रूप में कई संचालन ब्लॉक खींचें करने के लिए किए गए:

[2 ] [\ ] [\ ] [5 ]

यह स्पष्ट रूप से अमान्य होगा।

आखिरकार, मैं उन ब्लॉकों के साथ संचालन के किसी भी श्रृंखला को पार्स और व्याख्या करने में सक्षम होना चाहता हूं जो उपयोगकर्ता एक साथ खींच सकते हैं। क्या कोई मुझे बुनियादी गणित अभिव्यक्तियों को पार्स करने के लिए संसाधनों को समझा सकता है या मुझे बता सकता है?

मैं जितना संभव हो उतना भाषा अज्ञेय उत्तर पसंद करूंगा।

Answer 1

आप Shunting Yard Algorithm पर देख सकते हैं। लिंक किए गए विकिपीडिया पेज में एल्गोरिदम के विभिन्न उदाहरणों की जानकारी और लिंक का एक टन है।

असल में, इंफिक्स गणितीय नोटेशन में एक अभिव्यक्ति दी गई, यह एक एएसटी या रिवर्स पोलिश नोटेशन वापस दे, जो भी आपकी वरीयता हो सकती है।

यह page बहुत अच्छा है। SO पर एक couplerelated प्रश्न भी हैं।

Answer 2

कई आधुनिक भाषाओं में अंकगणितीय स्ट्रिंग अभिव्यक्तियों का मूल्यांकन करने के तरीके हैं। उदाहरण के लिए पाइथन

>>> a = '1+3*3'  
>>> eval(a)   
10  

आप अमान्य वाक्यविन्यास को पकड़ने के लिए अपवाद हैंडलिंग का उपयोग कर सकते हैं।

वैकल्पिक रूप से आप गणित अभिव्यक्ति के पेड़ का निर्माण कर सकते हैं, वहाँ SO: Expression Trees for Dummies.

Answer 3

में इन यहाँ के कुछ उदाहरण जैसा कि ऊपर बताया है, मैं एक पोस्ट ठीक अभिव्यक्ति करने के लिए सामान्य स्ट्रिंग (इन्फ़िक्स संकेतन) में परिवर्तित होगी।

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

इस मामले में अधिकांश काम शायद रूपांतरण में किया जाएगा। आप कनवर्ट किए गए फॉर्म को किसी एक्सेस या सरणी में आसान पहुंच के लिए स्टोर कर सकते हैं ताकि आपको वास्तव में प्रत्येक मान को फिर से पार्स करने की आवश्यकता न हो।

Answer 4

आप कहते हैं कि एक पंक्ति में कई ऑपरेटरों वैध नहीं हैं। लेकिन इसके बारे में सोचें:

5 + -2 

जो पूरी तरह से मान्य है।

सबसे बुनियादी अभिव्यक्ति व्याकरण की तरह है:

Expression = Term | Expression, AddOp, Term 
Term  = Factor | Term, MulOp, Factor 
Factor  = Number | SignOp, Factor | '(', Expression, ')' 

AddOp  = '+' | '-' 
MulOp  = '*' | '/' 
SignOp  = '+' | '-' 

Number  = Digit | Number, Digit 
Digit  = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' 

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

Answer 5

एक और नोट यह है कि कई पार्सिंग पुस्तकालय उपलब्ध हैं जो एक व्यक्ति इस कार्य को पूरा करने के लिए उपयोग कर सकते हैं। खरोंच से एक अच्छा अभिव्यक्ति पार्सर लिखना मुश्किल नहीं है, इसलिए मैं पुस्तकालय की जांच करने की सिफारिश करता हूं।

मैं सिंगुलर सिस्टम के लिए काम करता हूं जो गणित घटकों में माहिर हैं। हम दो गणित पार्सर्स जेप जावा और Jep.Net प्रदान करते हैं जो आपकी समस्या को हल करने में आपकी मदद कर सकते हैं। सौभाग्य!

Answer 6

इस दर्शकों के लिए आप स्थिति फ़ू पर "सिंटेक्स त्रुटि: अप्रत्याशित '/' जैसे संदेशों के लिए उपयोग किए जाने वाले प्रोग्रामर से भिन्न त्रुटि प्रतिक्रिया देना चाहते हैं।"

http://github.com/darius/expr

मुख्य विचारों: एक न्यूनतम संपादित parsability बहाल करने को खोजने के लिए असामान्य लंबाई करने के लिए जाना (व्यावहारिक के बाद से इनपुट भाव लंबे पृष्ठों नहीं कर रहे हैं), और एक उत्पन्न मैं कुछ शिक्षा के लिए बेहतर यहाँ applets करने की कोशिश की पार्सर पर फंस गया है कि लंबे सादे अंग्रेजी व्याख्या।