2026-10-07
eval.rs
pub enum Expr {
Num(i64),
Sub(Box<Expr>, Box<Expr>),
}
pub fn eval(e: &Expr) -> i64 {
}
Expr は、整数と引き算からなる式の木です。Num(n) の値は n、Sub(a, b) の値は a の値から b の値を引いたものです。式がどれだけ深くても eval の呼び出しが深くならないように、再帰呼び出しを使わずに式の値を返す eval を書いてください。入力例は、Expr が表す式を括弧付きの数式で書いたものです。
入力例 1
10 - (4 - 1)
出力例 1
7
入力例 2
(10 - 4) - 1
出力例 2
5
入力例 3
42
出力例 3
42
Reference
pub fn eval(e: &Expr) -> i64 {
enum Task<'a> {
Visit(&'a Expr),
Sub,
}
let mut tasks = vec![Task::Visit(e)];
let mut values = Vec::new();
while let Some(task) = tasks.pop() {
match task {
Task::Visit(Expr::Num(n)) => values.push(*n),
Task::Visit(Expr::Sub(a, b)) => {
tasks.extend([Task::Sub, Task::Visit(b), Task::Visit(a)]);
}
Task::Sub => {
let r = values.pop().unwrap();
let l = values.pop().unwrap();
values.push(l - r);
}
}
}
values.pop().unwrap()
}
再帰で書けば Sub(a, b) => eval(a) - eval(b) の1行で済みます。このとき呼び出しスタックは、eval(a) から戻ったら次に eval(b) を呼び、そのあと引き算する、という残りの仕事と、計算済みの a の値を覚えています。参考実装は、この2つを tasks と values という2本の Vec に移します。
tasks に積む Task::Visit は「この部分式を計算する」、Task::Sub は「values の上2つを取り出して引き算する」という仕事です。Sub(a, b) を見たら、Task::Sub、b、a の順に積みます。スタックは後から積んだものを先に取り出すので、実際の処理は a、b、引き算の順になり、Task::Sub を取り出した時点の values は a の値の上に b の値が載った形です。だから先に取り出す r が引く数、次の l が引かれる数です。a と b の順や l と r の順を取り違えると、入力例1と入力例2の答えが入れ替わります。
Task が持つのは部分式への参照 &'a Expr なので、木を複製せずに済みます。Task::Visit(b) の b は &Box<Expr> ですが、関数の引数と同じように参照外しの型強制で &Expr になります。
掲載したのは参考実装で、唯一の正解ではありません。木を一度たどって逆ポーランド記法の列に直してから、値のスタックだけで計算する書き方もあります1。
evalを再帰なしにしても、深いExprを捨てるときにはBoxのドロップが子のBoxを順にドロップしていくので、そこで呼び出しが式の深さだけ積み重なります。何十万段もの式を扱うなら、ExprのDropも同じようにスタックを使って書きます。