مقدمة
المكدّسات نوع من المجموعات شائع الاستخدام في علم الحاسوب.
وتُعرَّف بعمليتين أساسيتين: push وpop.
فـpush تُضيف عنصرًا إلى أعلى المكدّس.
أما pop فتزيل العنصر الأعلى وتُرجعه.
تخيّل المكدّس ككدسة من الأطباق.
يمكنك إمّا إضافة طبق إلى أعلى الكدسة، وإمّا أخذ الطبق الأعلى.
وللوصول إلى شيء أبعد في الأسفل، عليك إزالة كل الأطباق التي تعلوه.
يمكن استخدام تنفيذ المتجهات في Rust، std::vec::Vec، كمكدّس عبر طريقتي push() وpop().
وبطبيعة الحال، تُضيف push() عنصرًا إلى نهاية Vec وتُزيل pop() العنصر الأخير وتُرجعه.
وقد تكون هاتان العمليتان سريعتين جدًا (O(1) في ترميز O الكبير)، لذا فهما من أكثر الأساليب ملاءمةً لاستخدام Vec.
تفيد المكدّسات في حفظ أي عدد من العناصر بترتيب محدّد.
ولأن آخر عنصر يُضاف هو أول عنصر يُرجَع، يُشار إلى المكدّسات عادةً بالاختصار LIFO (Last-In, First-Out)، أي أن آخر ما يدخل هو أول ما يخرج.
ويمكن استخدام هذا الترتيب الملازم لأمور كثيرة، منها تتبّع الحالة عند تقييم الترميز البولندي المعكوس.
التعليمات
1. نظرة عامة
الترميز البولندي العكسي (RPN) هو أسلوب لكتابة التعبيرات الرياضية.
على عكس الترميز البيني المعتاد، فإن العوامل في RPN تتبع القيم التي تعمل عليها.
فعلى سبيل المثال، بدلًا من كتابة:
2 + 2
تكتب:
2 2 +
الميزة الكبرى للترميز البولندي العكسي أنه أسهل كثيرًا في التحليل من الترميز البيني.
فالترميز البولندي العكسي يلغي الحاجة إلى ترتيب العمليات أو الأقواس الهلالية في التعبيرات المركّبة.
على سبيل المثال:
(4 + 8) / (7 - 5)
يمكن كتابته هكذا:
4 8 + 7 5 - /
في كلتا الحالتين، يُقيَّم التعبير إلى 6.
2. مثال
لنُقيِّم ذلك التعبير المركّب يدويًا.
كما تعلّمنا في المقدمة، يتطلب تقييم الترميز البولندي العكسي مكدّسًا.
يُستخدم هذا المكدّس لحفظ القيم العددية التي تعمل عليها العوامل.
نبدأ الآلة الحاسبة بمكدّس فارغ، ثم نُقيّم كل عنصر على حدة.
أولًا، نصادف العدد 4،
فندفعه إلى المكدّس الذي أنشأناه للتو.
4
بعد ذلك، نصادف العدد 8.
وندفعه أيضًا إلى المكدّس.
4 8
الآن، نصادف +.
نسحب القيمتين العلويتين (4 و8)،
ونجمعهما معًا،
ثم ندفع الناتج مرة أخرى إلى المكدّس.
12
نفعل شيئًا مشابهًا مع 7 و5 و-:
12 7
12 7 5
12 2
الآن نصادف /.
رغم أن آخر ما صادفناه هو -،
فإن هناك عنصرين على المكدّس.
نسحب العنصرين،
ونقسم أحدهما على الآخر،
وندفع الناتج مرة أخرى إلى المكدّس.
6
أخيرًا، بما أنه يوجد عنصر واحد بالضبط على المكدّس،
يمكننا القول إن التعبير يُقيَّم إلى 6.
3. الهدف
هدفك هو كتابة آلة حاسبة لتقييم قائمة من المدخلات مرتّبة وفق الترميز البولندي العكسي، وإرجاع العنصر الأخير على المكدّس.
إذا لم يوجد عنصر واحد بالضبط في المكدّس في النهاية، فأرجع None.
إذا كان هناك عامل لديه قيم قليلة جدًا يعمل عليها (مثل المدخل 2 +)، فأرجع None.
لديك التعداد التالي والدالة المبدئية كنقطة بداية.
#[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"
);
}
تمرين تعلّمي
