मैं एक कार्य में आया जो आपको जांचता है कि आपकी विधि/फ़ंक्शन के लिए एक स्ट्रिंग को पारित किया गया है या नहीं, रिवर्स पोलिश नोटेशन अर्थ में एक सही कथन है। इसमें लोअरकेस वर्णमाला पत्र, ऑपरेशन संकेत और पूर्णांक हो सकते हैं। क्या प्रत्येक चरित्र को अलग से पढ़ने और वास्तव में पूरी अभिव्यक्ति का मूल्यांकन करने की कोशिश करने की तुलना में इसे जांचने का कोई तेज़ तरीका है?इनपुट स्ट्रिंग एक सही आरपीएन अभिव्यक्ति है या नहीं, यह जांचने का सबसे तेज़ तरीका क्या है?
उत्तर
आपको पूरी अभिव्यक्ति का मूल्यांकन करने की आवश्यकता नहीं है, लेकिन आपको इसे टोकन में विभाजित करने की आवश्यकता है, और आपको प्रत्येक ऑपरेटर की वैलेंस जाननी होगी (यानी, यह कितने ऑपरेंड लेता है)। सादगी के लिए, एक ऑपरेंड की वैलेंस 0 हो;
Set stack_size to 0;
For Each token In expression:
Set stack_size to stack_size + 1 - valence(token)
If stack_size <= 0: Report failure
If stack_size == 1: Report success
Else : Report failure
एकल शून्य के लिए _
का उपयोग कर उदाहरण: तो निम्न कार्य करें।
expression: 3 4 + 1 * _
stack_size: 0 1 2 1 2 1 1 -> success
expression: 2 3 4 + 1 * _
stack_size: 0 1 2 3 2 3 2 2 -> failure (not 1 at the end)
expression: 2 3 + + 1 * _
stack_size: 0 1 2 1 0 -> failure (stack_size <= 0)
आप रिवर्स पॉलिश नोटेशन को पहचानने के लिए एक पार्स टेबल का उपयोग कर सकते हैं। इसे प्रत्येक चरित्र को देखने की आवश्यकता है, लेकिन यह तेज़ है।
मुझे लगता है। धन्यवाद :) – Straightfw
Wikipedia अभिव्यक्ति को पार्स करने के लिए एक अच्छा एल्गोरिदम है। जब तक अभिव्यक्ति अमान्य न हो (जिस स्थिति में आप जल्दी समाप्त कर सकते हैं), ओ (एन) से बेहतर तरीके से आप कोई भी तरीका नहीं कर सकते हैं। यही है, यह सुनिश्चित करने के लिए कि आपको मान्य है, आपको स्ट्रिंग में सभी टोकन का मूल्यांकन करना होगा।
बहुत अच्छा। आपका बहुत बहुत धन्यवाद! :) – Straightfw