आरपीएन: एल्गोरिथ्म, तरीके और उदाहरण

आरपीएन एक बार दुनिया में एक कंप्यूटर प्रोग्रामर का आधार बनाया। आज यह इतनी अच्छी तरह से ज्ञात नहीं है। इसलिए, हास्य चित्रण, बाहर एक "रिवर्स" पोलिश सॉसेज रोल चित्रण, अभी भी कुछ जानकार प्रोग्रामर द्वारा गलत समझा जा सकता है। नहीं बहुत अच्छी तरह से मजाक समझाते हैं, लेकिन इस मामले में यह पूरी तरह से उचित नहीं होगा।

इन्फ़िक्स

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

सूत्र अनुवादक

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

क्या इन्फ़िक्स साथ गलत क्या है?

समस्या यह है, कि ऑपरेटरों पूर्वता और संबद्धता के रूप में ऐसे गुण होते हैं। इस वजह से, इन्फ़िक्स समारोह की परिभाषा गैर तुच्छ काम हो जाता है। उदाहरण के लिए, गुणन जिसका अर्थ है कि अभिव्यक्ति 2 + 3 * 4, 2 और 3 का योग है, 4 गुणा के बराबर नहीं है के रूप में यह ऑपरेटरों के प्रदर्शन में होगा बाएं से दाएं अलावा या घटाव की तुलना में अधिक पूर्वता, है। वास्तव में, 4 से 3 गुणा और 2. जोड़ने यह उदाहरण दर्शाता है कि इन्फ़िक्स अभिव्यक्ति की गणना अक्सर ऑपरेटरों और ऑपरेंड के क्रम में बदलाव की आवश्यकता है। इसके अलावा, यह ब्रेसिज़ उपयोग करने के लिए और अधिक स्पष्ट अंकन देखने के लिए आवश्यक है। उदाहरण के लिए, (2 + 3) * (4 + 5), कोष्ठक बिना लिखा नहीं जा सकता क्योंकि 2 + 3 * 4 + 5 मतलब है कि आप 4 से 3 गुणा और 2 और 5 जोड़ने की जरूरत है।

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

उपसर्ग और पोस्टफ़िक्स अंकन

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

ऑपरेंड की असीमित संख्या

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

प्राथमिकता क्रम द्वारा दिए गए

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

गणना एल्गोरिथ्म

OPN ऑपरेटर एक समारोह के रूप तर्क दो मानों उसे छोड़ दिया पर लिखा लेता है कि के रूप में ही लग रहा है। इसके अलावा, यह, प्रोग्रामिंग भाषाओं में इस्तेमाल के लिए एक प्राकृतिक अंकन है के रूप में अपनी गणना के तरीके ढेर संचालन से मेल खाती है और पार्स की आवश्यकता को समाप्त कर रहा है। उदाहरण के लिए, अभिव्यक्ति 5 + 6 * 7 में बन्दी एक 5, 6, 7 *, + के रूप में दिखाई देगा, और बाएं से दाएं यह स्कैनिंग करके गणना की जा सकती है और एक ढेर में मान लिखें। जब भी आपरेशन का एक आम हस्ताक्षर, कंप्यूटर स्मृति के ऊपरी तत्व 2 द्वारा चयनित, ऑपरेटर प्रयोग किया जाता है परिणाम स्मृति में लौट आए। जब गणना अभिव्यक्ति के अंतिम परिणाम ढेर के शीर्ष में होगा।

उदाहरण के लिए:

• एस = () 5, 6, 7, *, + 5 ढेर पर रख दिया गया।
• एस = (5) 6, 7, *, + 6 ढेर पर रख दिया गया।
• एस = (5, 6), 7 *, 7 + ढेर जगह।
• एस = (5, 6, 7), * 2 + ढेर, उपयोग * से मूल्यों को चुन सकते हैं और ढेर में परिणाम जगह।
• एस = (5, 6 * 7) = (5, 42) + 2 मूल्यों ढेर से चयनित, + लागू करते हैं और ढेर में परिणाम डाल करने के लिए।
• एस = (5 + 42) = (47) गणना के पूरा हो गया है, परिणाम ढेर के शीर्ष में संग्रहित है।

इस एल्गोरिथ्म आरपीएन बार-बार जाँच की जा सकती, लेकिन हर बार यह काम करेगा, चाहे कितना जटिल अंकगणितीय अभिव्यक्ति।

OPN और ढेर जुड़े हुए हैं। यह उदाहरण दर्शाता है कैसे स्मृति का उपयोग रिवर्स पोलिश संकेतन के मान की गणना करने के लिए। कम स्पष्ट है कि आप ढेर उपयोग कर सकते हैं, तीव्र गुर्दे की विफलता में मानक इन्फ़िक्स अभिव्यक्ति परिवर्तित है।

प्रोग्रामिंग भाषाओं के उदाहरण

पास्कल आरपीएन एहसास हुआ की तरह इस (कार्यक्रम का हिस्सा दिखाता है)।

चक्र, प्रक्रिया कहा जाता है जो कि क्या टोकन नंबर या हस्ताक्षर करें निर्धारित करता है में संख्या और ऑपरेटरों को पढ़ने के लिए। पहले मामले में, मूल्य ढेर में जमा हो जाती है, और दो ऊपरी ढेर संख्या इसी कार्रवाई के दूसरे किया जाता है और परिणाम संग्रहीत किया जाता है।

toktype: = संख्या;

पढ़ा (रों);

यदि ग में [ '+', '-', '*', '/'] तो शुरू

तो eoln cn: = '' किसी और को पढ़ने (सीएन);

यदि cn = '' तो

एक के मामले

'+': Toktype: = जोड़ने; '-': toktype: = उप;

'*': Toktype: = mul; '/': Toktype: = div

अंत

बाकी शुरू

अगर एक = '-' तो sgn: = -1 बाकी त्रुटि: = ग <> '+';

साथ: = cn

अंत

अंत;

अगर नहीं है (त्रुटि) और (toktype = संख्या) तो getnumber;

यदि toktype <> संख्या तो शुरू

y = पॉप; एक्स: = पॉप;

अगर नहीं तो त्रुटि

के मामले toktype

जोड़ें: जेड: = x + y; उप: जेड: = एक्स-y; mul: जेड: = x * y; div: जेड: = x / y

अंत

धक्का (z);

सी-कार्यान्वयन आरपीएन (कार्यक्रम का पता चला हिस्सा):

{(; की एस = strtok (0, डब्ल्यू) एस = strtok (रों, डब्ल्यू)) के लिए

एक = strtod (रों, और ई);

अगर (ड> रों) धक्का (क);

#define rpnop (एक्स) printf ( "% c:", * रों), ख = पॉप (), एक = पॉप (), धक्का (एक्स)

else if (* रों == '+') rpnop (ए + बी);

else if (* रों == '-') rpnop (a - b);

else if (* रों == '*') rpnop (एक * ख);

else if (* रों == '/') rpnop (a / b);

#undef rpnop

}

हार्डवेयर कार्यान्वयन

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

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

आरपीएन के साथ एक बार कैलकुलेटर लोकप्रिय थे, और कुछ लोगों को अभी भी उन्हें प्राथमिकता देते हैं। इसके अलावा, वे इस तरह के आगे के रूप में एक ढेर-उन्मुख भाषाओँ में, विकसित की है। आज यह थोड़ा इस्तेमाल किया, लेकिन अभी भी अपने पूर्व उपयोगकर्ताओं से उदासीन है।

तो रिवर्स पोलिश सॉसेज के बारे में अर्थ चुटकुले क्या है?

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