ماشین‌حساب RPN

دستورالعمل‌ها

1. مرور کلی

نمادگذاری لهستانی معکوس (RPN) روشی برای نوشتن عبارت‌های ریاضی است. برخلاف نمادگذاری میان‌وندی سنتی، در RPN عملگرها پس از عملوندهایشان می‌آیند. برای مثال، به‌جای اینکه بنویسید:

2 + 2

می‌نویسید:

2 2 +

مزیت اصلی نمادگذاری لهستانی معکوس این است که تجزیه‌ی آن بسیار ساده‌تر از نمادگذاری میان‌وندی است. در عبارت‌های پیچیده، 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. هدف

هدف شما این است که ماشین‌حسابی بنویسید که فهرستی از ورودی‌های مرتب‌شده بر اساس نمادگذاری لهستانی معکوس را ارزیابی کند و آخرین عنصر روی پشته را برگرداند.

اگر در پایان دقیقاً یک عنصر روی پشته نباشد، 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"
    );
}