Namaran

Code daily. Without assist.

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。

  1. eval を再帰なしにしても、深い Expr を捨てるときには Box のドロップが子の Box を順にドロップしていくので、そこで呼び出しが式の深さだけ積み重なります。何十万段もの式を扱うなら、Expr の Drop も同じようにスタックを使って書きます。