ভূমিকা
স্ট্যাক হলো এক ধরনের কালেকশন, যা কম্পিউটার সায়েন্সে বহুল ব্যবহৃত হয়।
এদের পরিচয় পাওয়া যায় এদের দুটি মূল অপারেশন দিয়ে: push আর pop।
Push স্ট্যাকের উপরে একটি এলিমেন্ট যোগ করে।
Pop একেবারে উপরের এলিমেন্টটি সরিয়ে ফেলে ও রিটার্ন করে।
স্ট্যাককে প্লেটের স্তূপের মতো করে ভাবুন।
আপনি হয় স্ট্যাকের উপরে একটি প্লেট যোগ করতে পারেন, নয়তো একেবারে উপরের প্লেটটি নিতে পারেন।
তার আরও নিচের কিছুতে পৌঁছাতে হলে তার উপরের সব প্লেট সরিয়ে ফেলতে হবে।
Rust-এর ভেক্টর ইমপ্লিমেন্টেশন, std::vec::Vec, এর push() ও pop() মেথড ব্যবহার করে স্ট্যাক হিসেবে ব্যবহার করা যায়।
স্বাভাবিকভাবেই, push() একটি এলিমেন্ট Vec-এর শেষে যোগ করে এবং pop() শেষ এলিমেন্টটি সরিয়ে ফেলে ও রিটার্ন করে।
এই অপারেশনগুলো খুব দ্রুত হতে পারে (বিগ ও নোটেশনে O(1)),
তাই এগুলো Vec ব্যবহারের অন্যতম ইডিয়োম্যাটিক উপায়।
নির্দিষ্ট একটি ক্রমে যেকোনো সংখ্যক এলিমেন্ট ধরে রাখতে স্ট্যাক কাজে লাগে।
যেহেতু সর্বশেষে ঢোকানো এলিমেন্টটিই প্রথমে রিটার্ন হয়,
তাই স্ট্যাককে সাধারণত LIFO বলা হয়, যার পুরো অর্থ Last-In, First-Out (অর্থাৎ শেষে ঢোকা, আগে বেরোনো)।
এই সহজাত ক্রমটি অনেক কাজে লাগে,
যেমন রিভার্স পোলিশ নোটেশন মূল্যায়ন করার সময় স্টেট ট্র্যাক করা।
নির্দেশনা
1. সংক্ষিপ্ত বিবরণ
Reverse Polish notation (RPN) হলো গাণিতিক এক্সপ্রেশন লেখার একটি পদ্ধতি।
প্রচলিত ইনফিক্স নোটেশনের বিপরীতে, RPN-এ অপারেটররা তাদের অপারেন্ডের পরে আসে।
উদাহরণস্বরূপ, এভাবে লেখার বদলে:
2 + 2
আপনি লিখবেন:
2 2 +
Reverse Polish notation-এর সবচেয়ে বড় সুবিধা হলো, এটি ইনফিক্স নোটেশনের তুলনায় পার্স করা অনেক সহজ।
জটিল এক্সপ্রেশনে অপারেশনের ক্রম বা বন্ধনীর প্রয়োজন RPN দূর করে দেয়।
উদাহরণস্বরূপ:
(4 + 8) / (7 - 5)
এভাবে লেখা যায়
4 8 + 7 5 - /
দুই ক্ষেত্রেই এক্সপ্রেশনটি মূল্যায়ন করলে ৬ হয়।
2. উদাহরণ
চলুন ওই জটিল এক্সপ্রেশনটি হাতে-কলমে মূল্যায়ন করি।
পরিচিতিতে আমরা যেমন শিখেছি, RPN মূল্যায়ন করতে একটি স্ট্যাক দরকার।
এই স্ট্যাকটি সেই সাংখ্যিক মানগুলো ধরে রাখতে ব্যবহৃত হয়, যেগুলোর উপর অপারেটররা কাজ করে।
আমরা আমাদের ক্যালকুলেটর শুরু করি একটি খালি স্ট্যাক দিয়ে, তারপর এক এক করে প্রতিটি এলিমেন্ট মূল্যায়ন করি।
প্রথমে আমরা একটি 4 দেখতে পাই,
তাই সেটি আমাদের সদ্য তৈরি স্ট্যাকের উপরে পুশ করি।
4
এরপর আমরা একটি 8 দেখতে পাই।
এটিও স্ট্যাকের উপরে পুশ করি।
4 8
এখন আমরা একটি + দেখতে পাই।
আমরা উপরের দুটি মান (৪ আর ৮) পপ করি,
সেগুলো যোগ করি,
এবং যোগফলটি আবার স্ট্যাকের উপরে পুশ করি।
12
7, 5 আর --এর ক্ষেত্রেও আমরা একইভাবে করি:
12 7
12 7 5
12 2
এখন আমরা একটি / দেখতে পাই।
যদিও সর্বশেষ আমরা একটি - দেখেছিলাম,
তবুও স্ট্যাকে দুটি এলিমেন্ট আছে।
আমরা দুটি এলিমেন্ট পপ করি,
সেগুলো ভাগ করি,
এবং ফলাফলটি আবার স্ট্যাকের উপরে পুশ করি।
6
শেষে, যেহেতু স্ট্যাকে ঠিক একটি এলিমেন্ট আছে,
আমরা বলতে পারি এক্সপ্রেশনটি মূল্যায়ন করলে ৬ হয়েছিল।
3. লক্ষ্য
আপনার লক্ষ্য হলো এমন একটি ক্যালকুলেটর লেখা, যা Reverse Polish notation অনুসারে সাজানো ইনপুটের একটি তালিকা মূল্যায়ন করে স্ট্যাকের শেষ এলিমেন্টটি রিটার্ন করবে।
শেষে স্ট্যাকে যদি ঠিক একটি এলিমেন্ট না থাকে, তবে 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"
);
}
লার্নিং অনুশীলনী
