From da297e692c4131eac3631b8440561c8dbc78f480 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Thu, 30 May 2024 22:30:31 -0700 Subject: Replace recursive evaluation with stacks. I think recursion is undefined behavior in Rust. --- src/expr.rs | 37 +++++++++++++++++++++++++++++++++---- 1 file changed, 33 insertions(+), 4 deletions(-) diff --git a/src/expr.rs b/src/expr.rs index 1022de4..bb6bb35 100644 --- a/src/expr.rs +++ b/src/expr.rs @@ -97,10 +97,39 @@ impl UnOp { impl Expr { pub fn eval(&self) -> Num { - match self { - Expr::Num(n) => *n, - Expr::UnOp { op, x } => op.eval(x.eval()), - Expr::BinOp { op, x, y } => op.eval(x.eval(), y.eval()), + enum Ex<'a> { + Expr(&'a Expr), + Un(UnOp), + Bin(BinOp), + } + + let mut exprs = Vec::new(); + let mut nums = Vec::new(); + + exprs.push(Ex::Expr(self)); + while let Some(e) = exprs.pop() { + match e { + Ex::Expr(Expr::Num(n)) => nums.push(*n), + Ex::Expr(Expr::UnOp { op, x }) => { + exprs.push(Ex::Un(*op)); + exprs.push(Ex::Expr(x)); + } + Ex::Expr(Expr::BinOp { op, x, y }) => { + exprs.push(Ex::Bin(*op)); + exprs.push(Ex::Expr(y)); + exprs.push(Ex::Expr(x)); + } + Ex::Un(op) => { + let n = nums.pop().unwrap(); + nums.push(op.eval(n)); + } + Ex::Bin(op) => { + let n2 = nums.pop().unwrap(); + let n1 = nums.pop().unwrap(); + nums.push(op.eval(n1, n2)); + } + } } + nums[0] } } -- cgit v1.3.1