“हम अपने कंप्यूटरों से चीज़ों की निगरानी करने को कहने में सक्षम होने वाले हैं, और जब कुछ विशेष शर्तें घटित होंगी, ट्रिगर होंगी, तो कंप्यूटर कुछ निश्चित कार्रवाइयाँ करेंगे और बाद में हमें सूचित करेंगे।”

$\quad$ - स्टीव जॉब्स

3.1 परिचय

हमने कक्षा ग्यारह में मानों को संभालने के लिए Python में विभिन्न डेटा प्रकारों के बारे में सीखा है। याद कीजिए कि String, List, Set, Tuple आदि ऐसे अनुक्रम डेटा प्रकार हैं जिनका उपयोग समान प्रकार या भिन्न प्रकार के तत्वों के संग्रह को दर्शाने के लिए किया जा सकता है। कई डेटा तत्वों को तेज़ पहुँच और डेटा के कुशल भंडारण के लिए एक विशेष तरीके से समूहित किया जाता है। इसीलिए हमने Python में डेटा मानों को संग्रहित करने के लिए विभिन्न डेटा प्रकारों का उपयोग किया है। ऐसे समूहन को डेटा संरचना कहा जाता है।

एक डेटा संरचना डेटा को संग्रहित, संगठित और पहुँचाने के साथ-साथ डेटा पर कुशलतापूर्वक किए जा सकने वाले संचालन (प्रोसेसिंग) के लिए एक तंत्र को परिभाषित करती है। उदाहरण के लिए, string एक ऐसी डेटा संरचना है जिसमें तत्वों का एक अनुक्रम होता है जहाँ प्रत्येक तत्व एक वर्ण होता है। दूसरी ओर, list एक अनुक्रम डेटा संरचना है जिसमें प्रत्येक तत्व भिन्न प्रकार का हो सकता है। हम list और string पर उलट, स्लाइसिंग, तत्वों की गिनती आदि जैसे विभिन्न संचालन लागू कर सकते हैं। इसलिए, एक डेटा संरचना कई तत्वों को इस प्रकार संगठित करती है ताकि प्रत्येक तत्व पर और सामूहिक डेटा इकाई पर कुछ निश्चित संचालन आसानी से किए जा सकें।

कंप्यूटर साइंस में अन्य महत्वपूर्ण डेटा संरचनाओं में ऐरे, लिंक्ड लिस्ट, बाइनरी ट्री, हीप, ग्राफ, स्पार्स मैट्रिक्स आदि शामिल हैं

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

3.2 स्टैक

हमने पुस्तकालय में किताबों के ढेर या घर पर थालियों के स्टैक (चित्र 3.1) देखे हैं। ऐसे ढेर में एक और किताब या थाली रखने के लिए हम हमेशा वस्तु को सबसे ऊपर ही रखते हैं (ढेर में जोड़ते हैं)। इसी प्रकार, ऐसे ढेर से किताब या थाली हटाने के लिए हम हमेशा वस्तु को सबसे ऊपर से ही हटाते हैं (ढेर से मिटाते हैं)। ऐसा इसलिए है क्योंकि बड़े ढेर में बीच या नीचे से वस्तु जोड़ना या हटाना असुविधाजनक होता है। तत्वों की इस प्रकार की रैखिक क्रम में व्यवस्था को स्टैक कहा जाता है। हम नए तत्वों को जोड़ते हैं या मौजूदा तत्वों को हटाते हैं एक ही छोर से, जिसे सामान्यतः स्टैक का शीर्ष कहा जाता है। यह अतः अंतिम-आया-पहला-गया (LIFO) सिद्धांत का अनुसरण करता है। अर्थात्, वह तत्व जो अंत में डाला गया था (सबसे ताजा तत्व) स्टैक से सबसे पहले बाहर निकाला जाएगा।

वह डेटा संरचना जिसमें तत्व क्रमबद्ध रूप से व्यवस्थित होते हैं, रैखिक डेटा संरचना कहलाती है।

चित्र 3.1: प्लेटों और किताबों का स्टैक

3.2.1 स्टैक के अनुप्रयोग

स्टैक के कुछ वास्तविक जीवन में अनुप्रयोग इस प्रकार हैं:

• अलमारी में कपड़ों का ढेर
• ऊध्र्वाधर रूप से रखी गई कई कुर्सियाँ
• कलाई पर पहने हुए चूड़ियों का समूह
• पेंट्री या रसोई की शेल्फ पर खाद्य सामग्री के डिब्बों का ढेर

सोचिए और विचार कीजिए

एक कंपाइलर या इंटरप्रेटर प्रोग्राम में फंक्शन कॉल्स को कैसे संभालता है?

प्रोग्रामिंग में स्टैक के अनुप्रयोगों के कुछ उदाहरण इस प्रकार हैं:

• जब हमें किसी स्ट्रिंग को उलटना होता है, तो स्ट्रिंग को अंतिम वर्ण से पहले वर्ण तक ट्रैवर्स किया जाता है। अर्थात् वर्णों को स्ट्रिंग में उनके प्रकट होने के क्रम के विपरीत क्रम में ट्रैवर्स किया जाता है। यह बहुत आसानी से स्ट्रिंग के वर्णों को एक स्टैक में डालकर किया जाता है।
• हम टेक्स्ट/इमेज एडिटर का उपयोग टेक्स्ट/इमेज को एडिट करने के लिए करते हैं जहाँ हमारे पास किए गए एडिटिंग को रीडू/अंडू करने के विकल्प होते हैं। जब हम रीडू/अंडू आइकन पर क्लिक करते हैं, तो सबसे हाल की एडिटिंग रीडू/अंडू हो जाती है। इस परिदृश्य में सिस्टम किए गए परिवर्तनों को ट्रैक रखने के लिए स्टैक का उपयोग करता है।
• वेब ब्राउज़ करते समय हम एक वेब पेज से दूसरे वेब पेज पर लिंक्स को एक्सेस करके जाते हैं। पिछले विज़िट किए गए वेब पेज पर वापस जाने के लिए हम ब्राउज़र पर बैक बटन का उपयोग कर सकते हैं। मान लीजिए हमने वेब पेज $\mathrm{P}1$ एक्सेस किया जहाँ से हम वेब पेज P2 पर गए और फिर वेब पेज P3 को ब्राउज़ किया। वर्तमान में हम वेब पेज P3 पर हैं और वेब पेज $\mathrm{P}1$ को फिर से देखना चाहते हैं। हम ब्राउज़र के BACK बटन का उपयोग करके पहले विज़िट किए गए वेब पेज पर जा सकते हैं। BACK बटन पर एक बार क्लिक करने पर हम वेब पेज P3 से वेब पेज $\mathrm{P}2$ पर पहुँच जाते हैं, BACK पर एक और क्लिक करने पर वेब पेज $\mathrm{P}1$ दिखाई देता है। इस मामले में ब्राउज़ किए गए पेजेस की हिस्ट्री स्टैक के रूप में मेंटेन की जाती है।
• किसी प्रोग्राम में कोई भी अंकगणितीय एक्सप्रेशन लिखते समय हम ऑपरेटर्स के मूल्यांकन को क्रमबद्ध करने के लिए कोष्ठकों का उपयोग कर सकते हैं। प्रोग्राम को एक्ज़ीक्यूट करते समय कंपाइलर मैच्ड कोष्ठकों की जाँच करता है अर्थात् प्रत्येक खुलने वाला कोष्ठक एक संगत बंद होने वाले कोष्ठक के साथ होना चाहिए और कोष्ठकों के जोड़े उचित रूप से नेस्टेड होने चाहिए। यदि कोष्ठक मिसमैच्ड हैं, तो कंपाइलर को एक एरर थ्रो करनी होती है। कोष्ठकों के मिलान को हैंडल करने के लिए स्टैक का उपयोग किया जाता है।

सोचिए और विचार कीजिए

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

3.3 स्टैक पर संचालन

जैसा कि पिछले खंड में समझाया गया है, स्टैक एक ऐसा तंत्र है जो LIFO व्यवस्था को लागू करता है, इसलिए तत्वों को स्टैक में केवल एक ही छोर से जोड़ा और हटाया जाता है। वह छोर जिससे तत्वों को जोड़ा या हटाया जाता है, स्टैक का TOP कहलाता है। स्टैक पर किए जाने वाले दो मूलभूत संचालन PUSH और POP हैं। इस खंड में हम उनके बारे में सीखेंगे और उन्हें Python का उपयोग करके लागू करेंगे।

3.3.1 PUSH और POP संचालन

• PUSH स्टैक के TOP पर एक नया तत्व जोड़ता है। यह एक सम्मिलन संचालन है। हम तब तक स्टैक में तत्व जोड़ सकते हैं जब तक वह भरा नहीं होता। एक स्टैक तब भरा हुआ माना जाता है जब उसमें और कोई तत्व नहीं जोड़ा जा सकता। भरे हुए स्टैक में तत्व जोड़ने का प्रयास ‘ओवरफ़्लो’ नामक अपवाद उत्पन्न करता है।
• POP संचालन का उपयोग स्टैक के सबसे ऊपर वाले तत्व को हटाने के लिए किया जाता है, अर्थात् वह तत्व जो स्टैक के TOP पर है। यह एक विलोपन संचालन है। हम तब तक स्टैक से तत्व हटा सकते हैं जब तक वह खाली नहीं हो जाता, अर्थात् उसमें कोई तत्व नहीं बचता। खाली स्टैक से तत्व हटाने का प्रयास ‘अंडरफ़्लो’ नामक अपवाद उत्पन्न करता है।

चित्र 3.2: गिलासों के स्टैक पर PUSH और POP संचालन

एक स्टैक का उपयोग LIFO क्रम में तत्वों को सम्मिलित करने और हटाने के लिए किया जाता है। गिलासों के ढेर में गिलास जोड़ने और हटाने में भी यही सिद्धांत अपनाया जाता है। मान लें कि प्रत्येक गिलास क्रमांकित है और हम गिलासों का एक स्टैक बनाते हैं। चित्र 3.2 में गिलासों के स्टैक पर PUSH और POP संचालनों की दृश्य प्रस्तुतियाँ दी गई हैं।

3.4 पायथन में स्टैक का कार्यान्वयन

अब तक हमने जाना है कि स्टैक तत्वों का एक रैखिक और क्रमबद्ध संग्रह है। पायथन में स्टैक को कार्यान्वित करने का सरल तरीका सूची (list) डेटा-प्रकार का उपयोग करना है। हम सूची के किसी एक सिरे को TOP मानकर तत्वों को सम्मिलित/हटा सकते हैं। ध्यान दें कि हम स्टैक के कार्यान्वयन के लिए सूची के अंतर्निहित विधियाँ append() और pop() का उपयोग कर रहे हैं। चूँकि ये अंतर्निहित विधियाँ सूची के दाहिने सिरे पर तत्वों को सम्मिलित/हटाती हैं, इसलिए TOP की स्पष्ट घोषणा आवश्यक नहीं है।

आइए एक कार्यक्रम लिखें जिसमें हम चित्र 3.2 में दिए गए गिलासों के स्टैक जैसा एक STACK बनाएँगे, जिसमें हम:

• तत्वों (गिलासों) को सम्मिलित/हटाएँगे
• जाँच करेंगे कि STACK खाली है या नहीं (स्टैक में कोई गिलास नहीं है)
• STACK में मौजूद तत्वों (गिलासों) की संख्या ज्ञात करेंगे
• STACK के सबसे ऊपर वाले तत्व (सबसे ऊपर वाले गिलास पर अंकित संख्या) का मान पढ़ेंगे

प्रोग्राम निम्नलिखित फ़ंक्शनों को इन ऑपरेशनों को करने के लिए परिभाषित करेगा:

• आइए एक खाली स्टैक बनाते हैं जिसका नाम glassstack होगा। हम ऐसा एक खाली सूची को glassstack नामक पहचानकर्ता को सौंपकर करेंगे:

glassStack = list()

• एक फ़ंक्शन isEmpty जो यह जांचे कि स्टैक glassStack खाली है या नहीं। याद रखें कि खाली स्टैक से एक तत्व निकालने की कोशिश ‘अंडरफ़्लो’ का कारण बनेगी। यह फ़ंक्शन True लौटाता है यदि स्टैक खाली है, अन्यथा False लौटाता है।

def isEmpty(glassStack):
$\quad$ if len(glassStack)==0:
$\qquad$ return True
$\quad$ else:
$\qquad$ return False

• एक फ़ंक्शन opPush जो स्टैक में एक नया तत्व डाले (PUSH)। इस फ़ंक्शन के दो पैरामीटर हैं – वह स्टैक जिसमें तत्व डालना है (glassStack) और वह तत्व जिसे डालना है। हम जानते हैं कि तत्व हमेशा स्टैक के शीर्ष पर डाला जाता है। इसलिए, हम सूची के अंत में हमेशा जोड़ने वाले built-in append() मेथड का उपयोग करेंगे। चूँकि Python में सूची के आकार की कोई सीमा नहीं है, लागू किया गया स्टैक कभी भरा नहीं होगा जब तक कि मेमोरी में जगह खत्म न हो। इसलिए हमें स्टैक के लिए ‘ओवरफ़्लो’ (नए तत्व के लिए कोई जगह नहीं) की स्थिति का सामना नहीं करना पड़ेगा।

def opPush(glassStack,element):
$\quad$ glassStack.append(element)

• एक फ़ंक्शन size जो glassStack में मौजूद तत्वों की संख्या पढ़े। हम Python में सूची के len() फ़ंक्शन का उपयोग करके glassstack में तत्वों की संख्या ज्ञात करेंगे।

def size(glassStack):
$\quad$ return len(glassStack)

• एक फ़ंक्शन top जो glassstack में सबसे ताज़ा तत्व (TOP) को पढ़ता है।

def top(glassStack):
$\quad$ if isEmpty(glassStack):
$\qquad$ print(‘Stack is empty’)
$\qquad$ return None
$\quad$ else:
$\qquad$ x =len(glassStack)
$\qquad$ element=glassStack[x-1]
$\qquad$ return element

• एक फ़ंक्शन opPop जो स्टैक से सबसे ऊपर का तत्व हटाता है। इसमें एक पैरामीटर होता है – स्टैक का नाम (glassStack) जिससे तत्व हटाना है और यह हटाए गए तत्व का मान लौटाता है। फ़ंक्शन पहले जाँचता है कि स्टैक खाली है या नहीं। यदि खाली नहीं है, तो यह सबसे ऊपर का तत्व हटा देता है। हम Python सूची के अंतर्निहित pop() मेथड का उपयोग करेंगे जो सूची के अंत से तत्व को हटाता है।

def opPop(glassStack):
$\quad$ if isEmpty(glassStack):
$\qquad$ print(‘underflow’)
$\qquad$ return None
$\quad$ else:
$\qquad$ return(glassStack.pop())

• एक फ़ंक्शन display जो स्टैक की सामग्री दिखाता है।

def display(glassStack):
$\quad$ x=len(glassStack)
$\quad$ print(“Current elements in the stack are: “)
$\quad$ for i in range(x-1,-1,-1):
$\qquad$ print(glassStack[i])

एक बार उपरोक्त फ़ंक्शन्स को परिभाषित करने के बाद हम नीचे दिया गया Python कोड उपयोग करके गिलासों का एक स्टैक लागू कर सकते हैं।

glassStack = list() # create empty stack

#स्टैक में तत्व जोड़ना
element=‘glass1’
print(“Pushing element “,element)
opPush(glassStack,element)
element=‘glass2’
print(“Pushing element “,element)
opPush(glassStack,element)

#स्टैक में तत्वों की संख्या दिखाना
print(“Current number of elements in stack is”,size(glassStack))

#स्टैक से एक तत्व हटाना
element=opPop(glassStack)
print(“Popped element is”,element)

#स्टैक में नया तत्व जोड़ना
element=‘glass3’
print(“Pushing element “,element)
opPush(glassStack,element)

#स्टैक में जोड़ा गया अंतिम तत्व दिखाना
#stack
print(“top element is”,top(glassStack))

#स्टैक में सभी तत्व दिखाना
display(glassStack)

#स्टैक से सभी तत्व हटाना
while True:
$\quad$ item=opPop(glassStack)
$\quad$ if item == None:
$\quad$ print(“Stack is empty now”)
$\qquad$ break
$\quad$ else:
$\qquad$ print(“Popped element is”,item)

उपरोक्त प्रोग्राम का आउटपुट इस प्रकार होगा:
Pushing element glass1
Pushing element glass2
Current number of elements in stack is 2
Popped element is glass2
Pushing element glass3
top element is glass3
Current elements in the stack are:
glass3
glass1
Popped element is glass3
Popped element is glass1
Underflow

Stack is empty now

3.5 अंकगणितीय व्यंजकों के लिए संकेतन

हम अंकगणितीय व्यंजकों को ऑपरेटरों को ऑपरैंडों के बीच में लिखकर व्यक्त करते हैं, जैसे $x+y, 2-3 * y$, आदि और जटिल व्यंजकों में ऑपरेटरों के मूल्यांकन को क्रमबद्ध करने के लिए कोष्ठक () का उपयोग करते हैं। ये व्यंजक इनफिक्स प्रतिनिधित्व का पालन करते हैं और BODMAS नियम का उपयोग करके मूल्यांकित किए जाते हैं।

पोलिश गणितज्ञ जान लुकासिएविच ने 1920 के दशक में अंकगणितीय व्यंजक को दर्शाने का एक भिन्न तरीका प्रस्तुत किया, जिसे पोलिश नोटेशन कहा जाता है। इस नोटेशन में ऑपरेटरों को उनके ऑपरैंडों से पहले लिखा जाता है। इसलिए संचालनों और ऑपरैंडों का क्रम परिणाम को निर्धारित करता है, जिससे कोष्ठक अनावश्यक हो जाते हैं। उदाहरण के लिए, हम $\mathrm{x}+\mathrm{y}$ को पोलिश नोटेशन में $+\mathrm{xy}$ के रूप में लिख सकते हैं। इसे प्रीफिक्स नोटेशन भी कहा जाता है क्योंकि हम ऑपरेटर को ऑपरैंडों से पहले लगाते हैं।

इस तर्क को उलटकर, हम एक व्यंजक को ऑपरेटरों को उनके ऑपरैंडों के बाद रखकर लिख सकते हैं। उदाहरण के लिए, $\mathrm{x}+\mathrm{y}$ को $\mathrm{xy}+$ के रूप में लिखा जा सकता है। इसे रिवर्स पोलिश नोटेशन या पोस्टफिक्स नोटेशन कहा जाता है। संक्षेप में, कोई भी अंकगणितीय व्यंजक इन तीनों में से किसी भी नोटेशन में प्रस्तुत किया जा सकता है अर्थात् इनफिक्स, प्रीफिक्स और पोस्टफिक्स और इन्हें तालिका 3.1 में उदाहरणों के साथ सूचीबद्ध किया गया है।

$\hspace{1cm}$ तालिका 3.1 इनफिक्स, प्रीफिक्स और पोस्टफिक्स नोटेशन

3.6 इनफिक्स से पोस्टफिक्स संकेतन में रूपांतरण

इनफिक्स अभिव्यक्ति का मूल्यांकन मनुष्यों के लिए आसान है। एक इनफिक्स अभिव्यक्ति $\mathrm{x}+\mathrm{y} / \mathrm{z}$ पर विचार करें। बाएँ से दाएँ जाते हुए हम पहले + ऑपरेटर से मिलते हैं, लेकिन हम $\mathrm{x}+\mathrm{y}$ नहीं जोड़ते बल्कि $\mathrm{y} / \mathrm{z}$ का मूल्यांकन करते हैं, फिर जोड़ संचालन करते हैं। ऐसा इसलिए है क्योंकि हमें ऑपरेटरों की प्राथमिकता क्रम का पता है जो BODMAS नियम का अनुसरण करता है। लेकिन हम इस प्राथमिकता ज्ञान को कंप्यूटर को अभिव्यक्ति के माध्यम से कैसे देते हैं?

इसके विपरीत, प्रीफिक्स/पोस्टफिक्स अभिव्यक्तियों को ऐसी प्राथमिकता से नहीं जूझना पड़ता क्योंकि ऑपरेटर पहले से ही मूल्यांकन के क्रम के अनुसार स्थित होते हैं। इसलिए बाएँ से दाएँ एक ही पारि भ्रमण अभिव्यक्ति के मूल्यांकन के लिए पर्याप्त है। इस खंड में हम एक स्टैक का उपयोग करके अंकगणितीय अभिव्यक्ति को इनफिक्स संकेतन से उसके समतुल्य पोस्टफिक्स संकेतन में रूपांतरण के बारे में सीखेंगे।

ऐसे रूपांतरण के दौरान, इनफिक्स अभिव्यक्ति में आए ऑपरेटरों का ट्रैक रखने के लिए एक स्टैक का उपयोग किया जाता है। इक्विवेलेंट पोस्टफिक्स अभिव्यक्ति को स्टोर करने के लिए स्ट्रिंग टाइप की एक वेरिएबल का उपयोग किया जाता है। एल्गोरिदम 3.1 एक अभिव्यक्ति को इनफिक्स नोटेशन से पोस्टफिक्स नोटेशन में रूपांतरित करता है:

सोचें और विचार करें

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

एल्गोरिदम 3.1: अभिव्यक्ति का इनफिक्स से पोस्टफिक्स नोटेशन में रूपांतरण

चरण 1: रूपांतरित पोस्टफ़िक्स अभिव्यक्ति को संग्रहित करने के लिए postExp नामक एक खाली स्ट्रिंग बनाएं।
चरण 2: एक चर, मान लीजिए inExp में इनफ़िक्स अभिव्यक्ति INPUT करें
चरण 3: inExp में प्रत्येक वर्ण के लिए, चरण 4 दोहराएं
चरण 4: यदि वर्ण एक बायाँ कोष्ठक है तो स्टैक पर PUSH करें
$\quad$ अन्य यदि वर्ण एक दायाँ कोष्ठक है
$\qquad$ तब स्टैक से तत्वों को POP करें और स्ट्रिंग से जोड़ें
$\hspace{1cm}$ postExp जब तक संगत बायाँ कोष्ठक POP न हो जाए
$\hspace{1cm}$ बायें और दायें दोनों कोष्ठकों को त्यागते हुए
$\quad$ अन्य यदि वर्ण एक ऑपरेटर है
$\qquad$ तब यदि इसकी प्राथमिकता स्टैक के शीर्ष पर स्थित ऑपरेटर से कम है
$\hspace{1cm}$ तब स्टैक से तत्वों को POP करें जब तक
$\hspace{1.5cm}$ एक ऐसा ऑपरेटर न मिले जिसकी प्राथमिकता वर्तमान
$\hspace{1.5cm}$ ऑपरेटर से कम हो और उसे स्ट्रिंग
$\hspace{1.5cm}$ postExp से जोड़ें इससे पहले कि इस ऑपरेटर को
$\hspace{1.5cm}$ postStack पर PUSH किया जाए
$\hspace{1cm}$ अन्य स्टैक पर ऑपरेटर PUSH करें
$\qquad$ अन्य वर्ण को postExp से जोड़ें
चरण 5: स्टैक से तत्वों को POP करें और postExp से जोड़ें जब तक स्टैक खाली न हो जाए
चरण 6: postExp OUTPUT करें

आइए अब इस एल्गोरिद्म का उपयोग करें एक दी गई इनफिक्स अभिव्यक्ति $(x+y) /\left(z^{*} 8\right)$ को समतुल्य पोस्टफिक्स अभिव्यक्ति में बदलने के लिए एक स्टैक का उपयोग करते हुए। चित्र 3.3 उन चरणों को दिखाता है जिन्हें दी गई इनफिक्स अभिव्यक्ति में एक ऑपरेटर या ऑपरेंड मिलने पर अपनाया जाना चाहिए। यहाँ ध्यान दें कि स्टैक का उपयोग ऑपरेटरों और कोष्ठकों को ट्रैक करने के लिए किया जाता है, और एक स्ट्रिंग चर समतुल्य पोस्टफिक्स अभिव्यक्ति को रखता है। प्रारंभ में दोनों खाली हैं। दी गई इनफिक्स अभिव्यक्ति में से प्रत्येक अक्षर को बाएँ से दाएँ संसाधित किया जाता है और एल्गोरिद्म में विस्तृत के अनुसार उपयुक्त कार्रवाई की जाती है। जब दी गई इनफिक्स अभिव्यक्ति में से प्रत्येक अक्षर संसाधित हो जाता है, तो स्ट्रिंग में समतुल्य पोस्टफिक्स अभिव्यक्ति होगी।

चित्र 3.3: इनफिक्स अभिव्यक्ति $(x+y) /\left(z^{*} 8\right)$ को पोस्टफिक्स संकेतन में रूपांतरण

3.7 पोस्टफिक्स अभिव्यक्ति का मूल्यांकन

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

एल्गोरिदम 3.2: पोस्टफिक्स अभिव्यक्ति का मूल्यांकन

चरण 1: पोस्टफिक्स अभिव्यक्ति को किसी चर, मान लीजिए postExp में INPUT करें
चरण 2: postExp के प्रत्येक वर्ण के लिए, चरण 3 को दोहराएं
चरण 3: यदि वर्ण एक ऑपरेंड है
$\quad$ तो उस वर्ण को स्टैक पर PUSH करें
$\qquad$ अन्यथा स्टैक से दो एलिमेंट्स POP करें, POP किए गए एलिमेंट्स पर
$\quad$ ऑपरेटर लागू करें और परिकलित मान को स्टैक पर PUSH करें
चरण 4: यदि स्टैक में एक ही एलिमेंट है
तो उस एलिमेंट को POP करें और निवल परिणाम के रूप में OUTPUT करें
अन्यथा OUTPUT “Invaild Postfix expression”

उदाहरण 3.2

चित्र 3.4 एल्गोरिदम 3.2 का उपयोग करके पोस्टफिक्स अभिव्यक्ति $782 * 4 /+$ के मूल्यांकन की चरणबद्ध प्रक्रिया दिखाता है।

चित्र 3.4: पोस्टफिक्स अभिव्यक्ति $782 * 4 /+$ का मूल्यांकन

सोचें और विचार करें

स्टैक का उपयोग करके किसी भी प्रीफिक्स अभिव्यक्ति का मूल्यांकन करने के लिए एक एल्गोरिदम लिखें।

सारांश

• स्टैक एक डेटा संरचना है जिसमें सम्मिलन और विलोपन केवल एक ही छोर से किया जाता है, जिसे सामान्यतः टॉप कहा जाता है।
• स्टैक LIFO सिद्धांत का पालन करता है जिससे अंत में सम्मिलित किया गया तत्व पहले बाहर निकलेगा।
• PUSH और POP स्टैक पर किए जाने वाले दो मूलभूत संचालन हैं जो क्रमशः तत्वों के सम्मिलन और विलोपन के लिए उपयोग किए जाते हैं।
• खाली स्टैक से तत्व को POP करने का प्रयास एक विशेष स्थिति अंडरफ़्लो उत्पन्न करता है।
• Python में, स्टैक को लागू करने के लिए list का उपयोग किया जाता है और इसके अंतर्निहित फ़ंक्शन append और pop क्रमशः सम्मिलन और विलोपन के लिए उपयोग किए जाते हैं। इसलिए, टॉप की स्पष्ट घोषणा की आवश्यकता नहीं होती है।
• कोई भी अंकगणितीय व्यंजक तीन में से किसी भी संकेतन में प्रस्तुत किया जा सकता है: इनफ़िक्स, प्रीफ़िक्स और पोस्टफ़िक्स।
• प्रोग्रामिंग करते समय, इनफ़िक्स संकेतन का उपयोग व्यंजक लिखने के लिए किया जाता है जिसमें बाइनरी ऑपरेटरों को ऑपरेंडों के बीच में लिखा जाता है।
• प्रीफ़िक्स/पोस्टफ़िक्स व्यंजक की बाईं से दाईं ओर एकल ट्रैवर्सल व्यंजक का मूल्यांकन करने के लिए पर्याप्त होता है क्योंकि ऑपरेटर अपनी प्राथमिकता क्रम के अनुसार सही स्थान पर रखे जाते हैं।
• स्टैक इनफ़िक्स व्यंजक को समतुल्य प्रीफ़िक्स/पोस्टफ़िक्स संकेतन में परिवर्तित करने के लिए सामान्यतः उपयोग की जाने वाली डेटा संरचना है।
• जब किसी इनफ़िक्स संकेतन को उसके समतुल्य प्रीफ़िक्स/पोस्टफ़िक्स संकेतन में परिवर्तित किया जाता है, तो केवल ऑपरेटरों को स्टैक पर PUSH किया जाता है।
• जब किसी पोस्टफ़िक्स व्यंजक का मूल्यांकन स्टैक का उपयोग करके किया जाता है, तो केवल ऑपरेंडों को उस पर PUSH किया जाता है।

अभ्यास

1. निम्नलिखित स्थितियों के लिए TRUE या FALSE बताएँ:

अ) स्टैक एक रैखिक डेटा संरचना है
ब) स्टैक LIFO नियम का पालन नहीं करता
स) PUSH ऑपरेशन अंडरफ़्लो स्थिति उत्पन्न कर सकता है
द) अभिव्यक्ति के लिए POSTFIX संकेतन में, ऑपरेटरों को ऑपरेंडों के बाद रखा जाता है

2. निम्नलिखित कोड का आउटपुट ज्ञात कीजिए:

अ)

result=0
numberList=[10,20,30]
numberList.append(40)
result=result+numberList.pop()
result=result+numberList.pop()
print(“Result=",result)

ब)

answer=[]; output=”
answer.append(‘T’)
answer.append(‘A’)
answer.append(‘M’)
ch=answer.pop()
output=output+ch
ch=answer.pop()
output=output+ch
ch=answer.pop()
output=output+ch
print(“Result=",output)

3. स्टैक का उपयोग करके एक स्ट्रिंग को उलटने के लिए प्रोग्राम लिखिए।

4. निम्नलिखित अंकगणितीय अभिव्यक्ति के लिए:

$$ \left((2+3)^{*}(4 / 2)\right)+2 $$

स्टैक डेटा संरचना का उपयोग करते हुए कोष्ठक मिलान की चरणबद्ध प्रक्रिया दिखाइए।

5. निम्नलिखित पोस्टफ़िक्स अभिव्यक्तियों का मूल्यांकन कीजिए, प्रत्येक ऑपरेशन के बाद स्टैक की स्थिति दिखाते हुए, दिया गया है $A=3, B=5$, $\mathrm{C}=1, \mathrm{D}=4$

अ) $\mathrm{AB}+\mathrm{C}$ *
ब) $\mathrm{AB} * \mathrm{C} / \mathrm{D}$ *

6. निम्नलिखित इनफ़िक्स संकेतनों को पोस्टफ़िक्स संकेतनों में रूपांतरित कीजिए, प्रत्येक चरण में स्टैक और स्ट्रिंग सामग्री दिखाते हुए।

अ) $\mathrm{A}+\mathrm{B}-\mathrm{C} * \mathrm{D}$
ब) $A *((C+D) / E)$

7. एक ऐसा प्रोग्राम लिखिए जो सभी संख्याओं में से केवल विषम संख्याओं को स्टोर करने के लिए एक स्टैक बनाए, जो उपयोगकर्ता द्वारा दर्ज की जाती हैं। स्टैक की सामग्री को सबसे बड़ी विषम संख्या के साथ प्रदर्शित करें। (संकेत: स्टैक से तत्वों को बाहर निकालते रहें और अब तक प्राप्त सबसे बड़े तत्व को एक चर में बनाए रखें। स्टैक खाली होने तक दोहराएं)