पोलिश प्रविष्टि उल्टा

दो प्लस दो, दो से गुणा करें?



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



गणित में, ऑपरेंड (x + y) के बीच ऑपरेटर रखने की एक प्राचीन परंपरा है, और ऑपरेंड्स के बाद नहीं (xy +)। ऑपरेंड के बीच ऑपरेटर के साथ एक फॉर्म को इन्फिक्स नोटेशन कहा जाता है। ऑपरेंड्स के बाद एक ऑपरेटर के साथ एक फॉर्म को पोलिश उपसर्गकर्ता जे। लुकासेविक (1958) के सम्मान में पोस्टफिक्स, या रिवर्स पोलिश नोटेशन कहा जाता है, जिन्होंने इस अंकन के गुणों का अध्ययन किया।

बीजगणितीय सूत्रों को व्यक्त करते समय उल्टा पोलिश संकेतन के infix संकेतन पर कई फायदे हैं। सबसे पहले, किसी भी सूत्र को बिना कोष्ठक के व्यक्त किया जा सकता है। दूसरे, यह स्टैक के साथ मशीनों में सूत्रों की गणना के लिए सुविधाजनक है । तीसरा, infix ऑपरेटरों की प्राथमिकताएँ हैं जो मनमानी और अवांछनीय हैं। उदाहरण के लिए, हम जानते हैं कि ab + c का मतलब (ab) + c, a (b + c) नहीं है, क्योंकि यह मनमाने ढंग से निर्धारित किया गया था कि गुणन इसके अलावा पूर्वता लेता है। लेकिन क्या लेफ्ट शिफ्ट ऑपरेशन पर पूर्वता लेता है और? कौन जानता है रिवर्स पोलिश नोटेशन ऐसी गलतफहमी को दूर करता है।



समस्या का बयान

कार्यक्रम के इनपुट में एकल-चरित्र पहचानकर्ताओं और अंकगणितीय संचालन के संकेतों से मिलकर एक अभिव्यक्ति प्राप्त होती है। पोलिश संकेतन को उलटने या त्रुटि की रिपोर्ट करने के लिए इस अभिव्यक्ति को परिवर्तित करना आवश्यक है।



रिवर्स पोलिश रिकॉर्ड एल्गोरिदम

इन्फिक्स फ़ार्मुलों को रिवर्स पोलिश नोटेशन में बदलने के लिए कई एल्गोरिदम हैं। हम संशोधित एल्गोरिथ्म पर विचार करेंगे, जिसका विचार ई। दिक्जस्ट्रा (ईडब्ल्यू दिक्जस्त्र) द्वारा प्रस्तावित किया गया था। मान लीजिए कि सूत्र में चर, दो-ऑपरेंड ऑपरेटर +, -, *, /, ^, साथ ही बाएं और दाएं कोष्ठक हैं। सूत्र के अंत को चिह्नित करने के लिए, हम एक चरित्र को उसके अंतिम वर्ण के बाद और अगले सूत्र के पहले वर्ण से पहले सम्मिलित करेंगे।





आंकड़ा योजनाबद्ध रूप से न्यूयॉर्क से कैलिफोर्निया तक टेक्सास की एक शाखा के साथ एक रेलमार्ग दिखाता है। सूत्र के प्रत्येक प्रतीक को एक गाड़ी द्वारा दर्शाया गया है। ट्रेन पश्चिम की ओर (बाईं ओर) चलती है। तीर के सामने, प्रत्येक कार को रोकना चाहिए और पता लगाना चाहिए कि क्या वह सीधे कैलिफ़ोर्निया जाना चाहिए, या अगर उसे रास्ते में टेक्सास को कॉल करने की आवश्यकता होगी। चर वाले वैगनों को हमेशा कैलिफोर्निया भेजा जाता है और टेक्सास की यात्रा कभी नहीं होती है। अन्य सभी प्रतीकों वाले वैगनों को निकटतम वैगन की सामग्रियों को जानना चाहिए जो तीर को पास करने से पहले टेक्सास गए थे।

तालिका उस स्थिति की निर्भरता को दर्शाती है जिस पर गाड़ी पिछले दिनों टेक्सास गई थी और कौन सी कार तीर पर है। पहला वैगन (⊥ के साथ चिह्नित) हमेशा टेक्सास के लिए निकलता है।







संख्या निम्न स्थितियों के अनुरूप है:

1. तीर पर वैगन टेक्सास के लिए निकलता है

2. टेक्सास के लिए अंतिम वैगन शीर्षक कैलिफोर्निया की ओर घूम रहा है

3. तीर पर वैगन और टेक्सास जाने वाले अंतिम वैगन चोरी और गायब हो जाते हैं

4. रोक। कैलिफोर्निया शाखा पर स्थित प्रतीक रिवर्स पोलिश संकेतन में सूत्र का प्रतिनिधित्व करते हैं, बाएं से दाएं पढ़ा जाता है

5. बंद करो। एक त्रुटि हुई है। मूल सूत्र गलत तरीके से संतुलित था



प्रत्येक क्रिया के बाद, तीर पर स्थित वैगन से एक नई तुलना की जाती है (यह पिछली तुलना की तरह वैगन हो सकती है, या यह अगला वैगन हो सकता है) और वैगन जो वर्तमान में टेक्सास के लिए अंतिम बचा है। यह प्रक्रिया चरण 4 तक पहुंचने तक जारी रहती है। ध्यान दें कि टेक्सास में लाइन का उपयोग स्टैक के रूप में किया जाता है, जहां एक वैगन को टेक्सास भेजने के लिए एक आइटम को स्टैक पर रखा जाता है, और टेक्सास के लिए एक कार को कैलिफोर्निया की ओर मोड़ते हुए तत्व को बाहर धकेल रहा है। ढेर।

इनफ़िक्स और पोस्टफ़िक्स प्रविष्टियों में चर का क्रम समान है। हालांकि, ऑपरेटरों का क्रम हमेशा समान नहीं होता है। रिवर्स पोलिश नोटेशन में, कथन उस क्रम में दिखाई देते हैं जिसमें उन्हें निष्पादित किया जाएगा।



रिवर्स पोलिश अंकन में अभिव्यक्ति का मूल्यांकन करने का उदाहरण

रिवर्स पोलिश नोटेशन एक स्टैक के साथ कंप्यूटर पर सूत्रों की गणना करने के लिए आदर्श है। सूत्र में n वर्ण होते हैं, जिनमें से प्रत्येक या तो एक ऑपरेटर या एक ऑपरेटर होता है। स्टैक का उपयोग करके रिवर्स पोलिश नोटेशन में सूत्र की गणना के लिए एल्गोरिथ्म सरल है। आपको बस बाएं से दाएं तरफ रिवर्स पोलिश प्रविष्टि को पढ़ने की आवश्यकता है। यदि एक ऑपरेंड पाया जाता है, तो इसे स्टैक पर धकेल दिया जाना चाहिए। यदि कोई ऑपरेटर सामने आता है, तो आपको उसके द्वारा निर्दिष्ट ऑपरेशन करना होगा।

एक उदाहरण के रूप में, निम्नलिखित अभिव्यक्ति की गणना पर विचार करें: (8 + 2 * 5) / (1 + 3 * 2-4)। रिवर्स पोलिश नोटेशन में संगत सूत्र इस तरह दिखता है: 825 * + 132 * + 4- /

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



PS आप, हमेशा की तरह, मेरी साइट पर स्रोत कोड तब तक डाउनलोड कर सकते हैं जब तक कि यह हेब्राफ़ेक्ट के अंतर्गत नहीं आता।

PPS अब हर कोई अपना कैलकुलेटर लिख सकता है। लाठी और कोष्ठक के साथ।