परिचय
स्टैक कंप्यूटर विज्ञान में आमतौर पर इस्तेमाल होने वाला एक तरह का संग्रह है।
इनकी पहचान इनके दो मुख्य ऑपरेशन से होती है: push और pop।
push स्टैक के सबसे ऊपर एक एलिमेंट जोड़ता है।
pop सबसे ऊपर वाले एलिमेंट को हटाता है और उसे लौटाता है।
स्टैक को प्लेटों के ढेर की तरह समझिए।
आप ढेर के सबसे ऊपर एक प्लेट रख सकते हैं या सबसे ऊपर वाली प्लेट उठा सकते हैं।
उससे नीचे रखी किसी चीज़ तक पहुँचने के लिए आपको उसके ऊपर की सारी प्लेटें हटानी पड़ेंगी।
Rust का वेक्टर std::vec::Vec अपने push() और pop() मेथड के ज़रिए स्टैक की तरह इस्तेमाल किया जा सकता है।
स्वाभाविक है कि push() किसी एलिमेंट को Vec के अंत में जोड़ता है और pop() अंतिम एलिमेंट को हटाकर लौटाता है।
ये ऑपरेशन बहुत तेज़ हो सकते हैं (बिग ओ नोटेशन में O(1)), इसलिए Vec का इस्तेमाल करने के सबसे स्वाभाविक तरीकों में ये ऑपरेशन भी शामिल हैं।
स्टैक किसी भी संख्या के एलिमेंट को एक खास क्रम में रखने के लिए उपयोगी होते हैं।
क्योंकि सबसे अंत में डाला गया एलिमेंट ही सबसे पहले लौटाया जाता है, इसलिए स्टैक को आमतौर पर LIFO (अंत में डाला गया, सबसे पहले निकाला गया) कहा जाता है।
स्टैक में जो क्रम अपने आप बनता है, उसका इस्तेमाल कई कामों में किया जा सकता है, जैसे रिवर्स पोलिश नोटेशन का मूल्यांकन करते समय स्थिति का ध्यान रखना।
निर्देश
1. अवलोकन
रिवर्स पोलिश नोटेशन (RPN) गणितीय व्यंजक लिखने का एक तरीका है।
पारंपरिक इन्फिक्स नोटेशन के विपरीत, RPN में ऑपरेटर अपने ऑपरेंड के बाद आते हैं।
उदाहरण के लिए, यह लिखने के बजाय:
2 + 2
आप यह लिखेंगे:
2 2 +
रिवर्स पोलिश नोटेशन का सबसे बड़ा फायदा यह है कि इसे इन्फिक्स नोटेशन की तुलना में पार्स करना कहीं आसान है।
RPN जटिल व्यंजकों में संक्रियाओं के क्रम या कोष्ठक की ज़रूरत हटा देता है।
उदाहरण के लिए:
(4 + 8) / (7 - 5)
इसे इस तरह लिखा जा सकता है
4 8 + 7 5 - /
दोनों ही मामलों में इस व्यंजक का मूल्यांकन 6 होता है।
2. उदाहरण
आइए उस जटिल व्यंजक का मूल्यांकन हाथ से करते हैं।
जैसा कि हमने परिचय में सीखा, RPN के मूल्यांकन के लिए एक स्टैक चाहिए।
यह स्टैक उन संख्यात्मक वैल्यू को रखने के लिए इस्तेमाल होता है जिन पर ऑपरेटर काम करते हैं।
हम अपना कैलकुलेटर एक खाली स्टैक से शुरू करते हैं और फिर एक-एक करके हर एलिमेंट का मूल्यांकन करते हैं।
सबसे पहले हमें एक 4 मिलता है,
इसलिए हम उसे अपने अभी-अभी बनाए स्टैक पर पुश करते हैं।
4
इसके बाद हमें एक 8 मिलता है।
हम उसे भी स्टैक पर पुश करते हैं।
4 8
अब हमें एक + मिलता है।
हम स्टैक के सबसे ऊपर की दो वैल्यू (4 और 8) पॉप करते हैं,
उन्हें आपस में जोड़ते हैं,
और जोड़ को वापस स्टैक पर पुश कर देते हैं।
12
हम 7, 5 और - के लिए भी कुछ ऐसा ही करते हैं:
12 7
12 7 5
12 2
अब हमें एक / मिलता है।
हालाँकि हमें सबसे पिछली बार एक - मिला था,
स्टैक पर दो एलिमेंट मौजूद हैं।
हम उन दोनों एलिमेंट को पॉप करते हैं,
उन्हें भाग देते हैं,
और परिणाम को वापस स्टैक पर पुश करते हैं।
6
अंत में, चूँकि स्टैक पर ठीक एक एलिमेंट है,
हम कह सकते हैं कि व्यंजक का मूल्यांकन 6 हुआ।
3. लक्ष्य
आपका लक्ष्य एक ऐसा कैलकुलेटर लिखना है जो रिवर्स पोलिश नोटेशन के क्रम में दिए गए इनपुट के ऐरे का मूल्यांकन करे और स्टैक पर मौजूद अंतिम एलिमेंट को लौटाए।
अगर अंत में स्टैक में ठीक एक एलिमेंट न हो, तो None लौटाइए।
अगर किसी ऑपरेटर के पास बहुत कम ऑपरेंड हों (जैसे इनपुट 2 +), तो None लौटाइए।
शुरुआत के लिए आपको नीचे दिया गया enum और अधूरा फंक्शन मिलता है।
#[derive(Debug)]
pub enum CalculatorInput {
Add,
Subtract,
Multiply,
Divide,
Value(i32),
}
pub fn evaluate(inputs: &[CalculatorInput]) -> Option<i32> {
todo!(
"Given the inputs: {inputs:?}, evaluate them as though they were a Reverse Polish notation expression"
);
}
सीखने का अभ्यास
