はじめに
スタックは、コンピューターサイエンスでよく使われるコレクションの一種です。
スタックは、pushとpopという2つの主要な操作で定義されます。
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の評価にはスタックが必要です。このスタックは、演算子が操作する数値を保持するために使います。まず空のスタックで計算機を始め、要素を1つずつ評価していきます。
まず4が出てきたので、できたばかりのスタックにプッシュします。
4
次に8が出てきます。これもスタックにプッシュします。
4 8
今度は+です。スタックの一番上にある2つの値（4と8）をポップし、それらを足して、その合計をスタックにプッシュし直します。
12
7、5、-についても同じようにします。
12 7
12 7 5
12 2
次に/が出てきます。直前に-が出てきたとしても、スタックには2つの要素があります。その2つの要素をポップし、割って、結果をスタックにプッシュし直します。
6
最後に、スタックには要素がちょうど1つあるので、この式は6と評価されたと言えます。
3. ゴール
目標は、逆ポーランド記法の順に並んだ入力のリストを評価し、スタックの最後の要素を返す計算機を書くことです。
最後にスタックの要素がちょうど1つでない場合は、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"
);
}
学習演習
