Вступ
Стеки - це різновид колекції, який часто використовують в інформатиці.
Їх визначають дві ключові операції: push і pop.
Push додає елемент на верхівку стека.
Pop вилучає верхній елемент і повертає його.
Уявімо стек як стос тарілок.
Можна або покласти тарілку на верхівку стоса, або зняти верхню тарілку.
Щоб дістатися до чогось нижче, доведеться зняти всі тарілки, що лежать вище.
Реалізацію вектора в Rust, std::vec::Vec, можна використати як стек, скориставшись її методами push() і pop().
Звісно, push() додає елемент у кінець Vec, а pop() вилучає останній елемент і повертає його.
Ці операції можуть бути дуже швидкими (O(1) у нотації Big O),
тож вони - один із найідіоматичніших способів використання Vec.
Стеки зручні для зберігання довільної кількості елементів у певному порядку.
Оскільки останній доданий елемент повертається першим,
стеки часто називають LIFO (останній увійшов, перший вийшов).
Цю властиву їм упорядкованість можна застосувати для багатьох речей,
зокрема для відстеження стану під час обчислення виразів у зворотному польському записі.
Вказівки
1. Огляд
Зворотний польський запис (ЗПЗ) - це спосіб запису математичних виразів.
На відміну від традиційного інфіксного запису, в ЗПЗ оператори стоять після своїх операндів.
Наприклад, замість того щоб писати:
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.
Мета цієї вправи - написати калькулятор, який обчислює список вхідних даних, упорядкованих за зворотним польським записом, і повертає останній елемент зі стеку.
Якщо в результаті в стеку не рівно один елемент, поверніть 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"
);
}
Навчальна вправа
